Abstract
This paper examines the behavior of the price of anarchy as a function of the traffic inflow in nonatomic congestion games with multiple origin-destination (O/D) pairs. Empirical studies in real-world networks show that the price of anarchy is close to 1 in both light and heavy traffic, thus raising the question: can these observations be justified theoretically? We first show that this is not always the case: the price of anarchy may remain bounded away from 1 for all values of the traffic inflow, even in simple three-link networks with a single O/D pair and smooth, convex costs. On the other hand, for a large class of cost functions (including all polynomials), the price of anarchy does converge to 1 in both heavy and light traffic conditions, and irrespective of the network topology and the number of O/D pairs in the network.
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
Notes
- 1.
Regular variation means here that \(\lim _{t\rightarrow \infty } c(tx)/c(t)\in (0,\infty )\) for all \(x>0\) (cf. Sect. 4.2).
- 2.
As an example, if all the network’s cost functions are polynomials of degree \(d\), all edges, paths and O/D pairs are tight with respect to the benchmark function \(c(x) = x^{d}\).
- 3.
To be clear, we do not assume here that \(\mathcal {P}^{i}\) is the set of all paths joining \(o^{i}\) to \(d^{i}\), but only some subset thereof. This distinction is important for packet-switched networks where only paths with a low hop count are used.
- 4.
For simplicity, when there is a single O/D pair, we will drop \(\mathcal {I}\) and the index \(i\) altogether.
- 5.
Since an unused edge always has a cost of zero, all paths are used at equilibrium.
References
Beckmann, M.J., McGuire, C., Winsten, C.B.: Studies in the Economics of Transportation. Yale University Press, New Haven, CT (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)
Braess, D.: Über ein Paradoxon aus der Verkehrsplanung. Unternehmensforschung 12, 258–268 (1968)
Cole, R. and Tao, Y.: Large market games with near optimal efficiency. In: Proceedings of the 2016 ACM Conference on Economics and Computation, pp. 791–808. ACM (2016)
Colini-Baldeschi, R., Cominetti, R., Scarsini, M.: On the price of anarchy of highly congested nonatomic network games. In: Gairing, M., Savani, R. (eds.) SAGT 2016. LNCS, vol. 9928, pp. 117–128. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53354-3_10
Correa, J.R., Schulz, A.S., Stier-Moses, N.E.: Selfish routing in capacitated networks. Math. Oper. Res. 29(4), 961–976 (2004)
Correa, J.R., Schulz, A.S., Stier-Moses, N.E.: A geometric approach to the price of anarchy in nonatomic congestion games. Games Econ. Behav. 64(2), 457–469 (2008)
de Haan, L., Ferreira, A.: Extreme Value Theory: An Introduction. Operations Research and Financial Engineering. Springer, New York (2006). https://doi.org/10.1007/0-387-34471-3
Dumrauf, D., Gairing, M.: Price of anarchy for polynomial wardrop games. In: Spirakis, P., Mavronicolas, M., Kontogiannis, S. (eds.) WINE 2006. LNCS, vol. 4286, pp. 319–330. Springer, Heidelberg (2006). https://doi.org/10.1007/11944874_29
Feldman, M., Immorlica, N., Lucier, B., Roughgarden, T., and Syrgkanis, V.: The price of anarchy in large games. In: Proceedings of the 48th Annual ACM Symposium on the Theory of Computing, STOC 2016 (2016)
González Vayá, M., Grammatico, S., Andersson, G., and Lygeros, J.: On the price of being selfish in large populations of plug-in electric vehicles. In: Proceedings of the 53rd IEEE Annual Conference on Decision and Control, CDC 2015, pp. 6542–6547. IEEE (2015)
Jessen, A.H., Mikosch, T.: Regularly varying functions. Publ. Inst. Math. (Beograd) (N.S.) 80(94), 171–192 (2006)
Karamata, J.: Sur un mode de croissance régulière. Théorèmes fondamentaux. Bull. Soc. Math. France 61, 55–62 (1933)
Koutsoupias, E., Papadimitriou, C.: Worst-case equilibria. In: Meinel, C., Tison, S. (eds.) STACS 1999. LNCS, vol. 1563, pp. 404–413. Springer, Heidelberg (1999). https://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)
Monnot, B., Benita, F., and Piliouras, G.: How bad is selfish routing in practice? Technical report (2017). arXiv:1703.01599v2
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)
Papadimitriou, C.H.: Algorithms, games, and the internet. In: Proceedings of the 33rd Annual ACM Symposium on the Theory of Computing, STOC 2001 (2001)
Pigou, A.C.: The Economics of Welfare, 1st edn. Macmillan and Co., London (1920)
Resnick, S.I.: Heavy-Tail Phenomena. Operations Research and Financial Engineering. Springer, New York (2007). https://doi.org/10.1007/978-0-387-45024-7. Probabilistic and statistical modeling
Roughgarden, T.: The price of anarchy is independent of the network topology. J. Comput. System Sci. 67(2), 341–364 (2003)
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)
Roughgarden, T., Tardos, É.: Bounding the inefficiency of equilibria in nonatomic congestion games. Games Econ Behav. 47(2), 389–403 (2004)
Wardrop, J.G.: Some theoretical aspects of road traffic research. Proc. Inst. Civil Eng. Part II 1, 325–378 (1952)
Youn, H., Gastner, M.T., Jeong, H.: Price of anarchy in transportation networks: efficiency and optimality control. Phys. Rev. Lett. 101(12), 128701 (2008)
Acknowledgments
R. Colini-Baldeschi and M. Scarsini are members of GNAMPA-INdAM. R. Cominetti and P. Mertikopoulos gratefully acknowledge the support and hospitality of LUISS during a visit in which this research was initiated. R. Cominetti’s research is also supported by FONDECYT 1130564 and Núcleo Milenio ICM/FIC RC130003 “Información y Coordinación en Redes”. P. Mertikopoulos was partially supported by the French National Research Agency (ANR) project ORACLESS (ANR– 16– CE33–0004– 01) and the ECOS/CONICYT Grant C15E03. He gratefully acknowledges the support and hospitality of FONDECYT 1130564 and Núcleo Milenio “Información y Coordinación en Redes”. The authors also gratefully acknowledge financial support from the PGMO grant HEAVY.NET.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2017 Springer International Publishing AG
About this paper
Cite this paper
Colini-Baldeschi, R., Cominetti, R., Mertikopoulos, P., Scarsini, M. (2017). The Asymptotic Behavior of the Price of Anarchy. In: R. Devanur, N., Lu, P. (eds) Web and Internet Economics. WINE 2017. Lecture Notes in Computer Science(), vol 10660. Springer, Cham. https://doi.org/10.1007/978-3-319-71924-5_10
Download citation
DOI: https://doi.org/10.1007/978-3-319-71924-5_10
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-71923-8
Online ISBN: 978-3-319-71924-5
eBook Packages: Computer ScienceComputer Science (R0)