×

Collusion in atomic splittable routing games. (English) Zbl 1334.91023

Aceto, Luca (ed.) et al., Automata, languages and programming. 38th international colloquium, ICALP 2011, Zurich, Switzerland, July 4–8, 2011. Proceedings, Part II. Berlin: Springer (ISBN 978-3-642-22011-1/pbk). Lecture Notes in Computer Science 6756, 564-575 (2011).
Summary: We investigate 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. It may be tempting to conjecture that the social cost would be lower after collusion, since there would be more coordination among the players. We construct examples to show that this conjecture is not true. These examples motivates the 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 Nash equilibria. 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 Nash equilibria.
For the entire collection see [Zbl 1217.68004].

MSC:

91A43 Games involving graphs
68M10 Network design and communication in computer systems
90B10 Deterministic network models in operations research
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Altman, E., Basar, T., Jimenez, T., Shimkin, N.: Competitive routing in networks with polynomial costs. IEEE Transactions on Automatic Control 47(1), 92–96 (2002) · Zbl 1364.90077 · doi:10.1109/9.981725
[2] Andelman, N., Feldman, M., Mansour, Y.: Strong price of anarchy. In: SODA, pp. 189–198 (2007) · Zbl 1303.91017
[3] Aumann, R.: Acceptable points in geneeral cooperative n-person games. Contributions to the Theory of Games 4 (1959) · Zbl 0085.13005
[4] Bhaskar, U., Fleischer, L., Huang, C.-C.: The price of collusion in series-parallel networks. In: Eisenbrand, F., Shepherd, F.B. (eds.) IPCO 2010. LNCS, vol. 6080, pp. 313–326. Springer, Heidelberg (2010) · Zbl 1285.91022 · doi:10.1007/978-3-642-13036-6_24
[5] Cominetti, R., Correa, J., Stier-Moses, N.E.: The impact of oligopolistic competition in networks. Operations Research 57(6), 1421–1437 (2009) · Zbl 1233.90064 · doi:10.1287/opre.1080.0653
[6] Fotakis, D., Kontogiannis, S., Spirakis, P.: Atomic congestion games among coalitions. ACM Transactions on Algorithms 4(4) (2008) · Zbl 1223.91015 · doi:10.1145/1383369.1383383
[7] Harks, T.: Stackelberg strategies and collusion in network games with splittable flow. In: Bampis, E., Skutella, M. (eds.) WAOA 2008. LNCS, vol. 5426, pp. 133–146. Springer, Heidelberg (2009) · Zbl 1209.91046 · doi:10.1007/978-3-540-93980-1_11
[8] Hayrapetyan, A., Tardos, E., Wexler, T.: The effect of collusion in congestion games. In: STOC, pp. 89–98 (2006) · Zbl 1300.91006 · doi:10.1145/1132516.1132529
[9] Huang, C.-C.: The price of collusion in series-parallel networks, Technical Report 238, Humboldt-Universität zu Berlin, Institut für Informatik (2011)
[10] Koutsoupias, E., Papadimitriou, C.: Worst-case equilibria. In: Meinel, C., Tison, S. (eds.) STACS 1999. LNCS, vol. 1563, pp. 404–413. Springer, Heidelberg (1999) · Zbl 1099.91501 · doi:10.1007/3-540-49116-3_38
[11] Orda, A., Rom, R., Shimkin, N.: Competitive routing in multiuser communication networks. IEEE/ACM Transactions on Networking 1(5), 510–521 (1993) · doi:10.1109/90.251910
[12] Roughgarden, T.: Selfish routing with atomic players. In: SODA, pp. 1184–1185 (2005) · Zbl 1297.91037
[13] Roughgarden, T., Schoppmann, F.: Local smoothness and the price of anarchy in atomic splittable congestion game. In: SODA, pp. 255–267 (2011) · Zbl 1377.91018 · doi:10.1137/1.9781611973082.22
[14] Roughgarden, T., Tardos, E.: How bad is selfish routing? Journal of the ACM 49(2), 236–259 (2002) · Zbl 1323.90011 · doi:10.1145/506147.506153
[15] Wardrop, J.G.: Some theoretical aspects of road traffic research. In: Proc. Institute of Civil Engineers, Pt. II, vol. 1, pp. 325–378 (1952) · doi:10.1680/ipeds.1952.11362
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.