The Inefficiency of Nash and Subgame Perfect Equilibria for Network Routing

References

• [1] Angelucci A, Bilò V, Flammini M, Moscardelli L (2015) On the sequential price of anarchy of isolation games. J. Combin. Optim. 29(1):165–181.Crossref, Google Scholar
• [2] Anshelevich E, Dasgupta A, Kleinberg J, Tardos É, Wexler T, Roughgarden T (2008) The price of stability for network design with fair cost allocation. SIAM J. Comput. 38(4):1602–1623.Crossref, Google Scholar
• [3] Avni G, Henzinger T, Kupferman O (2016) Dynamic resource allocation games. Gairing M, Savani R, eds. Algorithmic Game Theory, Lecture Notes in Computer Science, vol. 9928 (Springer, Berlin), 153–166.Crossref, Google Scholar
• [4] Awerbuch B, Azar Y, Epstein A (2013) The price of routing unsplittable flow. SIAM J. Comput. 42(1):160–177.Crossref, Google Scholar
• [5] Bhawalkar K, Gairing M, Roughgarden T (2014) Weighted congestion games: The price of anarchy, universal worst-case examples, and tightness. Trans. Econom. Comput. 2(4):1–14.Crossref, Google Scholar
• [6] Bilò V, Flammini M, Monaco G, Moscardelli L (2015) Some anomalies of farsighted strategic behavior. Theory Comput. Systems 56(1):156–180.Crossref, Google Scholar
• [7] Christodoulou G, Koutsoupias E (2005) The price of anarchy of finite congestion games. Gabow HN, Fagin R, eds. Proc. 37th Sympos. Theory Comput. (Association for Computing Machinery, New York), 67–73.Crossref, Google Scholar
• [8] Correa J, Schulz A, Stier Moses N (2004) Selfish routing in capacitated networks. Math. Oper. Res. 29(4):961–976.Link, Google Scholar
• [9] Correa J, de Jong J, de Keijzer B, Uetz M (2015) The curse of sequentiality in routing games. Markakis E, Schäfer G, eds. Web and Internet Economics, Lecture Notes in Computer Science, vol. 9470 (Springer, Berlin), 258–271.Crossref, Google Scholar
• [10] de Jong J, Uetz M (2014) The sequential price of anarchy for atomic congestion games. Liu T, Qi Q, Ye Y, eds. Web and Internet Economics, Lecture Notes in Computer Science, vol. 8877 (Springer, Cham), 429–434.Crossref, Google Scholar
• [11] de Jong J, Uetz M, Wombacher A (2013) Decentralized throughput scheduling. Spirakis P, Serna M, eds. Algorithms and Complexity, Lecture Notes in Computer Science, vol. 7878 (Springer, Berlin), 134–145.Crossref, Google Scholar
• [12] Fabrikant A, Papadimitriou C, Talwar K (2004) The complexity of pure Nash equilibria. Babai L, ed. Proc. 36th Ann. ACM Sympos. Theory Comput. (Association for Computing Machinery, New York), 604–612.Crossref, Google Scholar
• [13] Farzad B, Olver N, Vetta A (2008) A priority-based model of routing. Chicago J. Theoret. Comput. Sci. 2008(1):Article 1.Crossref, Google Scholar
• [14] Fotakis D (2015) A selective tour through congestion games. Zaroliagis C, Pantziou G, Kontogiannis S, eds. Algorithms, Probability, Networks, and Games, Lecture Notes in Computer Science, vol. 9295 (Springer, Cham), 223–241.Crossref, Google Scholar
• [15] Graham R (1969) Bounds on multiprocessing timing anomalies. SIAM J. Appl. Math. 17(2):416–429.Crossref, Google Scholar
• [16] Groenland C, Schäfer G (2018) The curse of ties in congestion games with limited lookahead. Dastani M, Sukthankar G, André E, Koenig S, eds. Proc. 17th Internat. Conf. Autonomous Agents Multiagent Systems (International Foundation for Autonomous Agents and Multiagent Systems, Richland, SC), 1941–1943. Also: arXiv:1804.07107.Google Scholar
• [17] Haeringer G, Wooders M (2011) Decentralized job matching. Internat. J. Game Theory 40(1):1–28.Crossref, Google Scholar
• [18] Harks T, Végh LA (2007) Nonadaptive selfish routing with online demands. Janssen J, Prałat P, eds. Combinatorial and Algorithmic Aspects of Networking. CAAN 2007, Lecture Notes in Computer Science, vol. 4852 (Springer, Berlin, Heidelberg), 27–45.Crossref, Google Scholar
• [19] Harks T, Heinz S, Pfetsch ME (2009) Competitive online multicommodity routing. Theory Comput. Systems 45:533–545.Crossref, Google Scholar
• [20] Hassin R, Yovel U (2015) Sequential scheduling on identical machines. Oper. Res. Lett. 43(5):530–533.Crossref, Google Scholar
• [21] Kawase Y, Yamaguchi Y, Yokoi Y (2018) Computing a subgame perfect equilibrium of a sequential matching game. Tardos E, Elkind E, eds. Proc. 3rd Conf. Econom. Comput. (Association for Computing Machinery, New York). Also: arXiv:1804.10353.Crossref, Google Scholar
• [22] Kolev K (2016) Sequential price of anarchy for atomic congestion games with limited number of players. Master’s thesis, Universiteit Twente, Enschede, Netherlands.Google Scholar
• [23] Koutsoupias E, Papadimitriou C (2009) Worst-case equilibria. Comput. Sci. Rev. 3(2):65–69.Crossref, Google Scholar
• [24] Kuhn HW (1953) Extensive games and the problem of information. Kuhn HW, Tucker AW, eds. Contributions to the Theory of Games, vol. 2 (Princeton University Press, Princeton, NJ), 193–216.Crossref, Google Scholar
• [25] Lucier B, Singer Y, Syrgkanis V, Tardos É (2013) Equilibrium in combinatorial public projects. Chen Y, Immorlica N, eds. Web and Internet Economics, Lecture Notes in Computer Science, vol. 8289 (Springer, Berlin), 347–360.Crossref, Google Scholar
• [26] Milchtaich I (1998) Crowding games are sequentially solvable. Internat. J. Game Theory 27(4):501–509.Crossref, Google Scholar
• [27] Olver N (2006) The price of anarchy and a priority-based model of routing. Master's thesis, McGill University, Montreal.Google Scholar
• [28] Osborne M (2003) An Introduction to Game Theory (Oxford University Press, Oxford, UK).Google Scholar
• [29] Paes Leme R, Syrgkanis V, Tardos É (2012) The curse of simultaneity. Goldwasser S, ed. Proc. 3rd Conf. Innovations Theoret. Comput. Sci. (Association for Computing Machinery, New York), 60–67.Google Scholar
• [30] Rahn M, Schäfer G (2015) Efficient equilibria in polymatrix coordination games. Italiano G, Pighizzini G, Sannella D, eds. Mathematical Foundations of Computer Science, Lecture Notes in Computer Science, vol. 9235 (Springer, Berlin), 529–541.Google Scholar
• [31] Roughgarden T, Tardos T (2002) How bad is selfish routing? J. ACM 49(2):236–259.Crossref, Google Scholar
• [32] Selten R (1965) Spieltheoretische Behandlung eines Oligopolmodells mit Nachfrageträgheit: Teil 1: Bestimmung des dynamischen Preisgleichgewichts. Zeitschrift für die gesamte Staatswissenschaft 121(2):301–324.Google Scholar
• [33] Wardrop JG (1952) Some theoretical aspects of road traffic research. Proc. Institution Civil Engineers 1(3):325–362.Crossref, Google Scholar