Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Theory of Computing Systems
Erschienen in: Theory of Computing Systems 4/2013

01.05.2013

Collusion in Atomic Splittable Routing Games

verfasst von: Chien-Chung Huang

Erschienen in: Theory of Computing Systems | Ausgabe 4/2013

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

We study how collusion affects the social cost in atomic splittable routing games. Suppose that players form coalitions and each coalition behaves as if it were a single player controlling all the flows of its participants. We investigate the following question: under what conditions would the social cost of the post-collusion equilibrium be bounded by the social cost of the pre-collusion equilibrium?
We show that if (i) the network is “well-designed” (satisfying a natural condition), and (ii) the delay functions are affine, then collusion is always beneficial for the social cost in the equilibrium flows. On the other hand, if either of the above conditions is unsatisfied, collusion can worsen the social cost.
Our main technique is a novel flow-augmenting algorithm to build equilibrium flows. Our positive result for collusion is obtained by applying this algorithm simultaneously to two different flow value profiles of players and observing the difference in the derivatives of their social costs. Moreover, for a non-trivial subclass of selfish routing games, this algorithm finds the exact equilibrium flows in polynomial time.
Vorheriger Artikel Built-in Coloring for Highly-Concurrent Doubly-Linked Lists

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren
Anhänge
Nur mit Berechtigung zugänglich
Fußnoten
1
More precisely, the examples in [12, 16] show that the social cost in the post-collusion equilibrium can be higher than in the pre-collusion Wardrop equilibrium. See the discussion in the related work for details.
 
2
Even though the result for affine delays as stated in [9] is only for series-parallel networks, the technique of [9] indeed also works for well-designed networks. This is because a well-designed network always satisfies the nesting property (see Sect. 3.3 for definition). A minor contribution of this paper is to identify a larger class of networks for this result of [9] to hold.
 
3
The proof proceeds as follows. Let σ′ be the profile of k players, each with the same amount of flow. Let σ be the profile of the post-collusion equilibrium flow. Observe that σ dominates σ′. It is established in [16] that the social cost of the equilibrium flow for σ′ has social cost no larger than the pre-collusion Wardrop equilibrium. Now applying Lemma 5 to compare social costs of the equilibria flows for σ′ and for σ would give the proof.
 
4
A Wardrop equilibrium f has the following characterization [40, 48]: if p and q are directed paths between the same pair of vertices and f uses p, ∑ e∈p l e (f e )≤∑ e∈q l e (f e ).
 
5
This follows from the fact that in an equilibrium flow of symmetric players, the flows of all players are identical [16].
 
6
To simplify our presentation, we slightly abuse notation by writing a value that goes to infinity as a fixed value t x .
 
7
Since we increase the flow by an infinitesimal amount ϵ, this algorithm, along with the main algorithm in the next section, do not run in polynomial time. But they can be easily modified to run in polynomial time. We choose to present in this manner since we consider it as simpler and it makes the analysis in Sect. 3.4 go smoother.
 
8
To be precise, C(σ,t) is not differentiable in the breakpoints t i (σ). Hence the domain of \(\frac{d C(\sigma,t)}{d t}\) is [0,1]∖{t i (σ)}∀i . For our purpose, it suffices to consider the open intervals between these breakpoints, because the functions C(σ,t) and C(σ′,t) are both continuous.
 
9
Recall our earlier remark at the end of Sect. 3.1: the growing speed of the social cost using a larger set of paths \(\mathcal {P}_{h(\sigma, t^{*})}\), which is \(Y_{h(\sigma,t^{*})} t^{*} + Z_{h(\sigma,t^{*})}\), is less than the growing speed of the social cost using a smaller set of paths \(\mathcal {P}_{h(\sigma', t^{*})}\), which is \(Y_{h(\sigma',t^{*})} t^{*} + Z_{h(\sigma',t^{*})}\), under a certain condition, which is \(t^{*} > t_{h(\sigma,t^{*})-1}\) and it is proved in Lemma 22.
 
Literatur
1.
Ahuja, R., Magnanti, T., Orlin, J.: Network Flows. Prentice Hall, New York (1993) MATH
2.
Aland, S., Dumrauf, D., Gairing, M., Monien, B., Schoppmann, F.: Exact price of anarchy for polynomial congestion games. In: STACS, pp. 218–229 (2006)
3.
4.
Altman, E., Basar, T., Jimenez, T., Shimkin, N.: Competitive routing in networks with polynomial costs. IEEE Trans. Autom. Control 47, 92–96 (2002) MathSciNetCrossRef
5.
Andelman, N., Feldman, M., Mansour, Y.: Strong price of anarchy. In: SODA, pp. 189–198 (2007)
6.
Aumann, R.: Acceptable points in general cooperative n-person games. Contrib. Theory Games 4 (1959)
7.
Awerbuch, B., Azar, Y., Epstein, A.: The price of routing unsplittable flow. In: STOC, pp. 57–66 (2005)
8.
Bhaskar, U., Fleischer, L., Hoy, D., Huang, C.-C.: Equilibria of atomic flow games are not unique. In: SODA, pp. 748–757 (2009)
9.
Bhaskar, U., Fleischer, L., Huang, C.-C.: The price of collusion in series-parallel networks. In: IPCO, pp. 313–326 (2010)
10.
11.
12.
Catoni, S., Pallottino, S.: Traffic equilibrium paradoxes. Transp. Sci. 25(3), 240–244 (1991) MATHCrossRef
13.
Chien, S., Sinclair, A.: Strong and pareto price of anarchy in congestion games. In: ICALP, pp. 279–291 (2009)
14.
Christodoulou, G., Koutsoupias, E.: The price of anarchy of finite congestion games. In: STOC, pp. 67–73 (2005)
15.
Christodoulou, G., Koutsoupias, E., Spirakis, P.G.: On the performance of approximate equilibria in congestion games. Algorithmica 61(2), 116–140 (2011) MathSciNetMATHCrossRef
16.
Cominetti, R., Correa, J.R., Stier-Moses, N.E.: The impact of oligopolistic competition in networks. Oper. Res. 57(6), 1421–1437 (2009) MathSciNetMATHCrossRef
17.
Correa, J.R., Schulz, A.S., Stier-Moses, N.E.: Selfish routing in capacitated networks. Math. Oper. Res. 29(4), 961–976 (2004) MathSciNetMATHCrossRef
18.
19.
Epstein, A., Feldman, M., Mansour, Y.: Strong equilibrium in cost-sharing connection games. In: EC, pp. 84–92 (2007)
20.
Fiat, A., Levy, M., Kaplan, H., Olonetsky, S.: Strong price of anarchy for machine load balancing. In: ICALP, pp. 583–594 (2007)
21.
Fleischer, L.: Linear tolls suffice: new bounds and algorithms for tolls in single source networks. Theor. Comput. Sci. 348(2–3), 217–225 (2005) MathSciNetMATHCrossRef
22.
Fleischer, L., Jain, K., Mahdian, M.: Tolls for heterogeneous selfish users in multicommodity networks and generalized congestion games. In: FOCS, pp. 277–285 (2004)
23.
Fotakis, D., Kontogiannis, S., Koutsoupias, E., Mavronicolas, M., Spirakis, P.: The structure and complexity of Nash equilibria for a selfish routing game. In: ICALP, pp. 123–134 (2002)
24.
Fotakis, D., Kontogiannis, S., Spirakis, P.: Symmetry in network congestion games: pure equilibria and anarchy cost. In: WAOA, pp. 161–175 (2005)
25.
Fotakis, D., Kontogiannis, S.C., Spirakis, P.: Selfish unsplittable flows. Theor. Comput. Sci. 226–239 (2005)
26.
Fotakis, D., Kontogiannis, S., Spirakis, P.: Atomic congestion games among coalitions. ACM Trans. Algorithms 4, 4 (2008). The conference version appeared in ICALP 2006 MathSciNetCrossRef
27.
Hariharan, R., Kavitha, T., Mehlhorn, K.: Faster algorithms for minimum cycle basis in directed graphs. SIAM J. Comput. 38(4), 1430–1447 (2008) MathSciNetMATHCrossRef
28.
Harks, T.: Stackelberg strategies and collusion in network games with splittable flow. Theory Comput. Syst. 781–802 (2011)
29.
Harks, T., Klimm, M., Möhring, R.: Strong Nash equilibria in games with the lexicographical improvement property. In: WINE, pp. 463–470 (2009)
30.
Harks, T., Höfer, M., Klimm, M., Skopalik, A.: Computing pure Nash and strong equilibria in bottleneck congestion games. In: ESA, pp. 29–38 (2010)
31.
Hayrapetyan, A., Tardos, E., Wexler, T.: The effect of collusion in congestion games. In: STOC, pp. 89–98 (2006)
32.
Karakostas, G., Kolliopoulos, S.G.: Edge pricing of multicommodity networks for heterogeneous selfish users. In: FOCS, pp. 268–276 (2004)
33.
Koutsoupias, E., Papadimitriou, C.: Worst-case equilibria. In: STACS, pp. 404–413 (1999) CrossRef
34.
Lin, H., Roughgarden, T., Tardos, E., Walkover, A.: Stronger bounds on Braess’s paradox and the maximum latency of selfish routing. SIAM J. Discrete Math. 25(4), 1667–1686 (2011) MathSciNetMATHCrossRef
35.
36.
Nocedal, J., Wright, S.: Numerical Optimization. Springer, Berlin (2006) MATH
37.
Orda, A., Rom, R., Shimkin, N.: Competitive routing in multiuser communication networks. IEEE/ACM Trans. Netw. 1(5), 510–521 (1993) CrossRef
38.
Rosen, J.B.: Existence and uniqueness of equilibrium points for concave n-person games. Econometrica 33(3), 520–534 (1965) MathSciNetMATHCrossRef
39.
40.
Roughgarden, T.: Selfish Routing and the Price of Anarchy. MIT Press, Cambridge (2005)
41.
Roughgarden, T.: On the severity of Braess’s paradox: designing networks for selfish users is hard. J. Comput. Syst. Sci. 72(5), 922–953 (2006) MathSciNetMATHCrossRef
42.
Roughgarden, T.: Intrinsic robustness of the price of anarchy. In: STOC, pp. 513–522 (2009) CrossRef
43.
Roughgarden, T., Schoppmann, F.: Local smoothness and the price of anarchy in atomic splittable congestion game. In: SODA (2011)
44.
45.
Swamy, C.: The effectiveness of Stackelberg strategies and tolls for network congestion games. In: SODA, pp. 1133–1142 (2007)
46.
47.
48.
Wardrop, J.G.: Some theoretical aspects of road traffic research. In: Proc. Institute of Civil Engineers, Pt. II, vol. 1, pp. 325–378 (1952)
Metadaten
Titel
Collusion in Atomic Splittable Routing Games
verfasst von
Chien-Chung Huang
Publikationsdatum
01.05.2013
Verlag
Springer-Verlag
Erschienen in
Theory of Computing Systems / Ausgabe 4/2013
Print ISSN: 1432-4350
Elektronische ISSN: 1433-0490
DOI
https://doi.org/10.1007/s00224-012-9421-4

Weitere Artikel der Ausgabe 4/2013

Theory of Computing Systems 4/2013 Zur Ausgabe

OriginalPaper

Colorings with few Colors: Counting, Enumeration and Combinatorial Bounds

OriginalPaper

Partition Into Triangles on Bounded Degree Graphs

OriginalPaper

Built-in Coloring for Highly-Concurrent Doubly-Linked Lists

OriginalPaper

On Rationality of Verbal Subsets in a Group

OriginalPaper

Improved Lower Bounds on the Price of Stability of Undirected Network Design Games

OriginalPaper

Parameterized Complexity of Satisfying Almost All Linear Equations over