Abstract
We consider nonatomic network games with one source and one destination. We examine the asymptotic behavior of the price of anarchy as the inflow increases. In accordance with some empirical observations, we show that, under suitable conditions, the price of anarchy is asymptotic to one. We show with some counterexamples that this is not always the case. The counterexamples occur in simple parallel graphs.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Attouch, H.: Variational Convergence for Functions and Operators. Pitman, Boston (1984)
Beckmann, M.J., McGuire, C., Winsten, C.B.: Studies in the Economics of Transportation. Yale University Press, New Haven (1956)
Bingham, N.H., Goldie, C.M., Teugels, J.L.: Regular Variation, Encyclopedia of Mathematics and its Applications, vol. 27. Cambridge University Press, Cambridge (1989)
Cole, R., Tao, Y.: The price of anarchy of large Walrasian auctions. Technical report, arXiv:1508.07370v4 (2015). http://arxiv.org/abs/1508.07370
Correa, J.R., Schulz, A.S., Stier-Moses, N.E.: Selfish routing in capacitated networks. Math. Oper. Res. 29(4), 961–976 (2004). http://dx.doi.org/10.1287/moor.1040.0098
Correa, J.R., Schulz, A.S., Stier-Moses, N.E.: Fast, fair, and efficient flows in networks. Oper. Res. 55(2), 215–225 (2007). http://dx.doi.org/10.1287/opre.1070.0383
Correa, J.R., Schulz, A.S., Stier-Moses, N.E.: A geometric approach to the price of anarchy in nonatomic congestion games. Games Econom. Behav. 64(2), 457–469 (2008). http://dx.doi.org/10.1016/j.geb.2008.01.001
Dumrauf, D., Gairing, M.: Price of anarchy for polynomial Wardrop games. In: Spirakis, P.G., Mavronicolas, M., Kontogiannis, S.C. (eds.) WINE 2006. LNCS, vol. 4286, pp. 319–330. Springer, Heidelberg (2006). http://dx.doi.org/10.1007/11944874_29
Englert, M., Franke, T., Olbrich, L.: Sensitivity of Wardrop equilibria. Theory Comput. Syst. 47(1), 3–14 (2010). http://dx.doi.org/10.1007/s00224-009-9196-4
Feldman, M., Immorlica, N., Lucier, B., Roughgarden, T., Syrgkanis, V.: The price of anarchy in large games. Technical report, arXiv:1503.04755 (2015)
Florian, M., Hearn, D.: Network equilibrium and pricing. In: Hall, R.W. (ed.) Handbook of Transportation Science, pp. 373–411. Springer, US, 978-0-306-48058-4 (2003). http://dx.doi.org/10.1007/0-306-48058-1_11
González Vayá, M., Grammatico, S., Andersson, G., Lygeros, J.: On the price of being selfish in large populations of plug-in electric vehicles. In: 2015 54th IEEE Conference on Decision and Control (CDC), pp. 6542–6547 (2015)
Josefsson, M., Patriksson, M.: Sensitivity analysis of separable traffic equilibrium equilibria with application to bilevel optimization in network design. Transp. Res. Part B: Methodol. 41(1), 4–31 (2007). http://dx.doi.org/10.1016/j.trb.2005.12.004
Koutsoupias, E., Papadimitriou, C.: Worst-case equilibria. In: Meinel, C., Tison, S. (eds.) STACS 1999. LNCS, vol. 1563, pp. 404–413. Springer, Heidelberg (1999). http://dx.doi.org/10.1007/3-540-49116-3_38
Law, L.M., Huang, J., Liu, M.: Price of anarchy for congestion games in cognitive radio networks. IEEE Trans. Wireless Commun. 11(10), 3778–3787 (2012)
Mas-Colell, A.: On a theorem of Schmeidler. J. Math. Econom. 13(3), 201–206 (1984). http://dx.doi.org/10.1016/0304-4068(84)90029-6
Milchtaich, I.: Generic uniqueness of equilibrium in large crowding games. Math. Oper. Res. 25(3), 349–364 (2000). http://dx.doi.org/10.1287/moor.25.3.349.12220
Milchtaich, I.: Social optimality and cooperation in nonatomic congestion games. J. Econom. Theory 114(1), 56–87 (2004). http://dx.doi.org/10.1016/S0022-0531(03)00106-6
O’Hare, S.J., Connors, R.D., Watling, D.P.: Mechanisms that govern how the price of anarchy varies with travel demand. Transp. Res. Part B: Methodol. 84, 55–80 (2016). http://dx.doi.org/10.1016/j.trb.2015.12.005
Panageas, I., Piliouras, G.: Approximating the geometry of dynamics in potential games. Technical report, arXiv:1403.3885v5 (2015). https://arxiv.org/abs/1403.3885
Papadimitriou, C.: Algorithms, games, and the Internet. In: Proceedings of the Thirty-Third Annual ACM Symposium on Theory of Computing, pp. 749–753. (2001). http://dx.doi.org/10.1145/380752.380883
Patriksson, M.: Sensitivity analysis of traffic equilibria. Transp. Sci. 38(3), 258–281 (2004). http://pubsonline.informs.org/doi/abs/10.1287/trsc.1030.0043
Pigou, A.C.: The Economics of Welfare, 1st edn. Macmillan and Co., London (1920)
Piliouras, G., Nikolova, E., Shamma, J.S.: Risk sensitivity of price of anarchy under uncertainty. In: Proceedings of the Fourteenth ACM Conference on Electronic Commerce, EC 2013, pp. 715–732. ACM, New York (2013). http://doi.acm.org/10.1145/2482540.2482578
Roughgarden, T.: The price of anarchy is independent of the network topology. J. Comput. System Sci. 67(2), 341–364 (2003). http://dx.doi.org/10.1016/S0022-0000(03)00044-8
Roughgarden, T.: Routing games. In: Algorithmic Game Theory, pp. 461–486. Cambridge Univ. Press, Cambridge (2007)
Roughgarden, T., Tardos, É.: How bad is selfish routing? J. ACM 49(2), 236–259 (2002). (electronic) http://dx.doi.org/10.1145/506147.506153
Roughgarden, T., Tardos, É.: Bounding the inefficiency of equilibria in nonatomic congestion games. Games Econom. Behav. 47(2), 389–403 (2004). http://dx.doi.org/10.1016/j.geb.2003.06.004
Roughgarden, T., Tardos, É.: Introduction to the inefficiency of equilibria. In: Algorithmic Game Theory, pp. 443–459. Cambridge Univ. Press, Cambridge (2007)
Schmeidler, D.: Equilibrium points of nonatomic games. J. Statist. Phys. 7, 295–300 (1973)
Wardrop, J.G.: Some theoretical aspects of road traffic research. In: Proceedings of the Institute of Civil Engineers, Pt. II, vol. 1, pp. 325–378 (1952). http://dx.doi.org/10.1680/ipeds.1952.11362
Youn, H., Gastner, M.T., Jeong, H.: Price of anarchy in transportation networks: efficiency and optimality control. Phys. Rev. Lett. 101, 128701 (2008). http://dx.doi.org/10.1103/PhysRevLett.101.128701
Acknowledgments
Riccardo Colini-Baldeschi is a member of GNCS-INdAM. Roberto Cominetti gratefully acknowledges the support and hospitality of LUISS during a visit in which this research was initiated. His research is also supported by Núcleo Milenio Información y Coordinación en Redes ICM/FIC P10-024F. Marco Scarsini is a member of GNAMPA-INdAM. His work is partially supported by PRIN and MOE2013-T2-1-158.
The authors thank three referees for their insightful comments.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2016 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Colini-Baldeschi, R., Cominetti, R., Scarsini, M. (2016). On the Price of Anarchy of Highly Congested Nonatomic Network Games. In: Gairing, M., Savani, R. (eds) Algorithmic Game Theory. SAGT 2016. Lecture Notes in Computer Science(), vol 9928. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-53354-3_10
Download citation
DOI: https://doi.org/10.1007/978-3-662-53354-3_10
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-53353-6
Online ISBN: 978-3-662-53354-3
eBook Packages: Computer ScienceComputer Science (R0)