When Is Selfish Routing Bad? The Price of Anarchy in Light and Heavy Traffic

References

• Attouch H (1984) Variational Convergence for Functions and Operators (Pitman, Boston).Google Scholar
• Beckmann MJ, McGuire C, Winsten CB (1956) Studies in the Economics of Transportation (Yale University Press, New Haven, CT).Google Scholar
• Bertsekas DP, Gallager R (1992) Data Networks, 2nd ed. (Prentice Hall, Englewood Cliffs, NJ).Google Scholar
• Bingham NH, Goldie CM, Teugels JL (1989) Regular Variation (Cambridge University Press, Cambridge, UK).Google Scholar
• Braess D (1968) Über ein Paradoxon aus der Verkehrsplanung. Unternehmensforschung 12(1):258–268.Google Scholar
• Cole R, Tao Y (2016) Large market games with near optimal efficiency. Conitzer V, Bergemann D, Chen Y, eds. Proc. 2016 ACM Conf. Econom. Comput. (Association for Computing Machinery, New York), 791–808.Google Scholar
• Colini-Baldeschi R, Cominetti R, Scarsini M (2016) On the price of anarchy of highly congested nonatomic network games. Gairing M, Savani R, eds. Algorithmic Game Theory, Lecture Notes in Computer Science, vol. 9928 (Springer, Berlin), 117–128.Crossref, Google Scholar
• Colini-Baldeschi R, Cominetti R, Scarsini M (2019) Price of anarchy for highly congested routing games in parallel networks. Theory Comput. Systems 63(1):90–113.Crossref, Google Scholar
• Colini-Baldeschi R, Cominetti R, Mertikopoulos P, Scarsini M (2017a) The asymptotic behavior of the price of anarchy. Devanur RN, Lu P, eds. Web and Internet Economics, Lecture Notes in Computer Science, vol. 10660 (Springer, Cham), 133–145.Google Scholar
• Colini-Baldeschi R, Cominetti R, Mertikopoulos P, Scarsini M (2017b) When is selfish routing bad? The price of anarchy in light and heavy traffic. Preprint, submitted March 2, https://arxiv.org/abs/1703.00927.Google Scholar
• Correa JR, Schulz AS, Stier-Moses NE (2004) Selfish routing in capacitated networks. Math. Oper. Res. 29(4):961–976.Link, Google Scholar
• Correa JR, Schulz AS, Stier-Moses NE (2007) Fast, fair, and efficient flows in networks. Oper. Res. 55(2):215–225.Link, Google Scholar
• Correa JR, Schulz AS, Stier-Moses NE (2008) A geometric approach to the price of anarchy in nonatomic congestion games. Games Econom. Behav. 64(2):457–469.Crossref, Google Scholar
• de Haan L, Ferreira A (2006) Extreme Value Theory (Springer, New York).Crossref, Google Scholar
• Dumrauf D, Gairing M (2006) Price of anarchy for polynomial Wardrop games. Spirakis P, Mavronicolas M, Kontogiannis S, eds. Proc. 2nd Conf. Web Internet Econom. (Springer, Berlin), 319–330.Google Scholar
• Feldman M, Immorlica N, Lucier B, Roughgarden T, Syrgkanis V (2016) The price of anarchy in large games. Wichs D, Mansour Y, eds. Proc. 48th Annual ACM SIGACT Sympos. Theory Comput. (Association for Computing Machinery, New York), 963–976.Google Scholar
• González Vayá M, Grammatico S, Andersson G, Lygeros J (2015) On the price of being selfish in large populations of plug-in electric vehicles. Ohta Y, Sampei, M, eds. Proc. 53rd IEEE Annual Conf. Decision Control (Institute of Electrical and Electronics Engineers, Piscataway, NJ), 6542–6547.Google Scholar
• Jessen AH, Mikosch T (2006) Regularly varying functions. Publications de l'Institut Mathématique 80(94):171–192.Google Scholar
• Karamata J (1930) Sur un mode de croissance régulière des fonctions. Mathematica (Cluj) 4:38–53.Google Scholar
• Karamata J (1933) Sur un mode de croissance régulière. Théorèmes fondamentaux. Bull. Soc. Math. France 61:55–62.Crossref, Google Scholar
• Koutsoupias E, Papadimitriou CH (1999) Worst-case equilibria. Meinel C, Tison S, eds. Proc. 16th Annual Sympos. Theoret. Aspects Comput. Sci. (Springer-Verlag, Berlin), 404–413.Google Scholar
• LeBlanc LJ, Morlok EK, Pierskalla WP (1975) An efficient approach to solving the road network equilibrium traffic assignment problem. Transportation Res. 9(5):309–318.Crossref, Google Scholar
• Monnot B, Benita F, Piliouras G (2017) Routing games in the wild: Efficiency, equilibration and regret large-scale field experiments in Singapore. Preprint, submitted August 14, https://arxiv.org/abs/1708.04081.Google Scholar
• O’Hare SJ, Connors RD, Watling DP (2016) Mechanisms that govern how the price of anarchy varies with travel demand. Transportation Res. Part B: Methodological 84(February):55–80.Crossref, Google Scholar
• Papadimitriou CH (2001) Algorithms, games, and the Internet. Vitter JS, Spirakis P, Yannakakis M, eds. Proc. 33rd Annual ACM Sympos. Theory Comput (Association for Computing Machinery, New York), 749–753.Google Scholar
• Pigou AC (1920) The Economics of Welfare, 1st ed. (Macmillan and Co., London).Google Scholar
• Resnick SI (2007) Heavy-Tail Phenomena. (Springer, New York).Google Scholar
• Roughgarden T (2003) The price of anarchy is independent of the network topology. J. Comput. System Sci. 67(2):341–364.Crossref, Google Scholar
• Roughgarden T (2007) Routing games. Algorithmic Game Theory (Cambridge University Press, Cambridge, UK), 461–486.Crossref, Google Scholar
• Roughgarden T, Tardos E (2002) How bad is selfish routing? J. ACM 49(2):236–259.Crossref, Google Scholar
• Roughgarden T, Tardos E (2004) Bounding the inefficiency of equilibria in nonatomic congestion games. Games Econom. Behav. 47(2):389–403.Crossref, Google Scholar
• Stidham S (2014) The price of anarchy for a network of queues in heavy traffic. Pulat PS, Sarin SC, Uzsoy R, eds. Essays in Production, Project Planning and Scheduling: A Festschrift in Honor of Salah Elmaghraby (Springer, Boston), 91–121.Crossref, Google Scholar
• Wardrop JG (1952) Some theoretical aspects of road traffic research. Proc. Institute Civil Engineers 1(5):325–362.Google Scholar
• Wu Z, Möhring RH, Chen Y (2017) Selfishness need not be bad. Preprint, submitted December 20, https://arxiv.org/abs/1712.07464.Google Scholar
• Wu Z, Möhring RH, Xu D (2018) Selfishness need not be bad: A general proof. Preprint, submitted May 20, https://arxiv.org/abs/1805.07762.Google Scholar
• Youn H, Gastner MT, Jeong H (2008) Price of anarchy in transportation networks: Efficiency and optimality control. Physical Rev. Lett. 101(12):128701.Crossref, Google Scholar