×

zbMATH — the first resource for mathematics

The curse of sequentiality in routing games. (English) Zbl 1404.91047
Markakis, Evangelos (ed.) et al., Web and internet economics. 11th international conference, WINE 2015, Amsterdam, The Netherlands, December 9–12, 2015. Proceedings. Berlin: Springer (ISBN 978-3-662-48994-9/pbk; 978-3-662-48995-6/ebook). Lecture Notes in Computer Science 9470, 258-271 (2015).
Summary: In the “The curse of simultaneity” [in: Proceedings of the 3rd conference on innovations in theoretical computer science, ITCS’12. New York, NY: Association for Computing Machinery (ACM). 60–67 (2012; Zbl 1348.91014)], R. P. Leme et al. show that there are interesting classes of games for which sequential decision making and corresponding subgame perfect equilibria avoid worst case Nash equilibria, resulting in substantial improvements for the price of anarchy. This is called the sequential price of anarchy. A handful of papers have lately analysed it for various problems, yet one of the most interesting open problems was to pin down its value for linear atomic routing (also: network congestion) games, where the price of anarchy equals 5/2. The main contribution of this paper is the surprising result that the sequential price of anarchy is unbounded even for linear symmetric routing games, thereby showing that sequentiality can be arbitrarily worse than simultaneity for this class of games. Complementing this result we solve an open problem in the area by establishing that the (regular) price of anarchy for linear symmetric routing games equals 5/2. Additionally, we prove that in these games, even with two players, computing the outcome of a subgame perfect equilibrium is NP-hard.
For the entire collection see [Zbl 1326.68026].

MSC:
91A43 Games involving graphs
91A05 2-person games
91A18 Games in extensive form
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Angelucci, A., Bilò, V., Flammini, M., Moscardelli, L.: On the sequential price of anarchy of isolation games. In: Du, D.-Z., Zhang, G. (eds.) COCOON 2013. LNCS, vol. 7936, pp. 17–28. Springer, Heidelberg (2013) · Zbl 1382.91009 · doi:10.1007/978-3-642-38768-5_4
[2] Anshelevich, E., Dasgupta, A., Kleinberg, J., Tardos, É., Wexler, T., Roughgarden, T.: The price of stability for network design with fair cost allocation. In: Proceedings of the 45th FOCS, pp. 295–304. IEEE (2004) · Zbl 1173.91321 · doi:10.1109/FOCS.2004.68
[3] Awerbuch, B., Azar, Y., Epstein, A.: The price of routing unsplittable flow. In: Proceedings of the 37th STOC, pp. 57–66 (2005) · Zbl 1192.90099
[4] Bhawalkar, K., Gairing, M., Roughgarden, T.: Weighted congestion games: the price of anarchy, universal worst-case examples, and tightness. ACM Trans. Economics Comput. 2(4), Article 14 (2014) · Zbl 1287.91026
[5] Bilo, V., Flammini, M., Monaco, G., Moscardelli, L.: Some anomalies of farsighted strategic behavior. In: Proceedings of the 10th WAOA, pp. 229–241 (2013) · Zbl 1395.91008 · doi:10.1007/978-3-642-38016-7_19
[6] Christodoulou, G., Koutsoupias, E.: The price of anarchy of finite congestion games. In: Proceedings of the 37th STOC, pp. 67–73 (2005) · Zbl 1192.91039 · doi:10.1145/1060590.1060600
[7] Corréa, J., de Keijzer, B., de Jong, J., Uetz, M.: The curse of sequentiality in routing games. Technical Report CTIT, University of Twente (2015). http://eprints.eemcs.utwente.nl/26301/ · Zbl 1404.91047
[8] de Jong, J., Uetz, M., Wombacher, A.: Decentralized throughput scheduling. In: Spirakis, P.G., Serna, M. (eds.) CIAC 2013. LNCS, vol. 7878, pp. 134–145. Springer, Heidelberg (2013) · Zbl 1384.90052 · doi:10.1007/978-3-642-38233-8_12
[9] de Jong, J., Uetz, M.: The sequential price of anarchy for atomic congestion games. In: Liu, T.-Y., Qi, Q., Ye, Y. (eds.) WINE 2014. LNCS, vol. 8877, pp. 429–434. Springer, Heidelberg (2014) · Zbl 1404.91062 · doi:10.1007/978-3-319-13129-0_35
[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] Kreps, D.M., Wilson, R.B.: Sequential equilibria. Econometrica 50, 863–894 (1982) · Zbl 0483.90092 · doi:10.2307/1912767
[12] Kuhn, H.W.: Extensive games and the problem of information. Ann. Math. Stud. 28, 193–216 (1953) · Zbl 0050.14303
[13] Milchtaich, I.: Crowding games are sequentially solvable. Int. J. Game Theory 27, 501–509 (1998) · Zbl 0943.91011 · doi:10.1007/s001820050086
[14] Leme, R.P., Syrgkanis, V., Tardos, É.: The curse of simultaneity. In: Proceedings of the 3rd ITCS, pp. 60–67 (2012) · Zbl 1348.91014 · doi:10.1145/2090236.2090242
[15] Osborne, M.J.: An Introduction to Game Theory. Oxford University Press, Oxford (2003)
[16] Selten, R.: Spieltheoretische Behandlung eines Oligopolmodells mit Nachfrageträgheit: Teil 1: Bestimmung des Dynamischen Preisgleichgewichts. Zeitschrift für die gesamte Staatswissenschaft 121(2), 301–324 (1965)
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.