Abstract
We investigate traffic routing both from the perspective of real world data as well as theory. First, we reveal through data analytics a natural but previously uncaptured regularity of real world routing behavior. Agents only consider, in their strategy sets, paths whose free-flow costs (informally their lengths) are within a small multiplicative \((1+\theta )\) constant of the optimal free-flow cost path connecting their source and destination where \(\theta \ge 0\). In the case of Singapore, \(\theta =1\) is a good estimate of agents’ route (pre)selection mechanism. In contrast, in Pigou networks the ratio of the free-flow costs of the routes and thus \(\theta \) is infinite, so although such worst case networks are mathematically simple they correspond to artificial routing scenarios with little resemblance to real world conditions, opening the possibility of proving much stronger Price of Anarchy guarantees by explicitly studying their dependency on \(\theta \). We provide an exhaustive analysis of this question by providing provably tight bounds on PoA(\(\theta \)) for arbitrary classes of cost functions both in the case of general congestion/routing games as well as in the special case of path-disjoint networks. For example, in the case of the standard Bureau of Public Roads (BPR) cost model, \(c_e(x)= a_e x^4+b_e\) and more generally quartic cost functions, the standard PoA bound for \(\theta =\infty \) is 2.1505 [21] and it is tight both for general networks as well as path-disjoint and even parallel-edge networks. In comparison, in the case of \(\theta =1\), the PoA in the case of general networks is only 1.6994, whereas for path-disjoint/parallel-edge networks is even smaller (1.3652), showing that both the route geometries as captured by the parameter \(\theta \) as well as the network topology have significant effects on PoA (Fig. 1).
Full paper can be found at https://arxiv.org/abs/2009.12871. F. Benita would like to acknowledge Ministry of Education, Singapore Grant SGPCTRS1804. B. Monnot acknowledges the SUTD Presidential Graduate Fellowship. G. Piliouras gratefully acknowledges AcRF Tier 2 grant 2016-T2-1-170, grant PIE-SGP-AI-2020-01, NRF2019-NRF-ANR095 ALIAS grant and NRF 2018 Fellowship NRF-NRFF2018-07. C. Vinci would like to acknowledge the Italian MIUR PRIN 2017 Project ALGADIMAR “Algorithms, Games, and Digital Markets”.
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
Benita, F., Bilò, V., Monnot, B., Piliouras, G., Vinci, C.: Data-driven models of selfish routing: why price of anarchy does depend on network topology. arXiv preprint arXiv:2009.12871 (2020)
Bilò, V.: A unifying tool for bounding the quality of non-cooperative solutions in weighted congestion games. Theory Comput. Syst. 62(5), 1288–1317 (2018)
Bilò, V., Vinci, C.: On the impact of singleton strategies in congestion games. In: 25th Annual European Symposium on Algorithms (ESA 2017). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2017)
Bilò, V., Vinci, C.: The price of anarchy of affine congestion games with similar strategies. Theor. Comput. Sci. 806, 641–654 (2020)
Bureau of Public Roads: Traffic assignment manual. US Department of Commerce (1964)
Christodoulou, G., Koutsoupias, E.: The price of anarchy of finite congestion games. In: Proceedings of the Thirty-seventh Annual ACM Symposium on Theory of Computing, pp. 67–73. ACM (2005)
Colini-Baldeschi, R., Cominetti, R., Mertikopoulos, P., Scarsini, M.: The asymptotic behavior of the price of anarchy. In: Devanur, N.R., Lu, P. (eds.) WINE 2017. LNCS, vol. 10660, pp. 133–145. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-71924-5_10
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
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
Fotakis, D.: Congestion games with linearly independent paths: convergence time and price of anarchy. Theory Comput. Syst. 47(1), 113–136 (2010)
Gemici, K., Koutsoupias, E., Monnot, B., Papadimitriou, C.H., Piliouras, G.: Wealth inequality and the price of anarchy. In: 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2019)
Jahn, O., Möhring, R.H., Schulz, A.S., Moses, N.E.S.: System-optimal routing of traffic flows with user constraints in networks with congestion. Oper. Res. 53(4), 600–616 (2005)
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
Kulkarni, J., Mirrokni, V.S.: Robust price of anarchy bounds via LP and fenchel duality. In: Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2015), pp. 1030–1049. SIAM (2015)
Lu, P.Y., Yu, C.Y.: Worst-case Nash equilibria in restricted routing. J. Comput. Sci. Technol. 27(4), 710–717 (2012)
Monnot, B., Benita, F., Piliouras, G.: Routing games in the wild: efficiency, equilibration and regret. In: Devanur, N.R., Lu, P. (eds.) WINE 2017. LNCS, vol. 10660, pp. 340–353. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-71924-5_24
Monnot, B., et al.: Inferring activities and optimal trips: lessons from Singapore’s national science experiment. In: Cardin, M.-A., Fong, S.H., Krob, D., Lui, P.C., Tan, Y.H. (eds.) Complex Systems Design & Management Asia. AISC, vol. 426, pp. 247–264. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-29643-2_19
Nadav, U., Roughgarden, T.: The limits of smoothness: a primal-dual framework for price of anarchy bounds. In: Saberi, A. (ed.) WINE 2010. LNCS, vol. 6484, pp. 319–326. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-17572-5_26
Nagurney, A., Qiang, Q.: A relative total cost index for the evaluation of transportation network robustness in the presence of degradable links and alternative travel behavior. Int. Trans. Oper. Res. 16(1), 49–67 (2009)
Papadimitriou, C.: Algorithms, games, and the internet. In: Proceedings of the Thirty-third Annual ACM Symposium on Theory of Computing, pp. 749–753. ACM (2001)
Roughgarden, T.: The price of anarchy is independent of the network topology. J. Comput. Syst. Sci. 67(2), 341–364 (2003)
Roughgarden, T.: Intrinsic robustness of the price of anarchy. J. ACM (JACM) 62(5), 32 (2015)
Roughgarden, T., Tardos, É.: How bad is selfish routing? J. ACM (JACM) 49(2), 236–259 (2002)
Thang, N.K.: Game efficiency through linear programming duality. In: Proceedings of the 10th Innovations in Theoretical Computer Science Conference (ITCS 2019), vol. LIPIcs 124, pp. 66:1–66:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
Tobin, R.L., Friesz, T.L.: Sensitivity analysis for equilibrium network flow. Transp. Sci. 22(4), 242–250 (1988)
Wardrop, J.: Some Theoretical Aspects of Road Traffic Research. Road paper, Institution of Civil Engineers (1952). https://books.google.it/books?id=9zEpAQAAMAAJ
Zhang, J., Pourazarm, S., Cassandras, C.G., Paschalidis, I.C.: The price of anarchy in transportation networks: data-driven evaluation and reduction strategies. Proc. IEEE 106(4), 538–553 (2018)
Zhou, Y., Wang, J., Shi, P., Dahlmeier, D., Tippenhauer, N., Wilhelm, E.: Power-saving transportation mode identification for large-scale applications. arXiv preprint arXiv:1701.05768 (2017)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2020 Springer Nature Switzerland AG
About this paper
Cite this paper
Benita, F., Bilò, V., Monnot, B., Piliouras, G., Vinci, C. (2020). Data-Driven Models of Selfish Routing: Why Price of Anarchy Does Depend on Network Topology. In: Chen, X., Gravin, N., Hoefer, M., Mehta, R. (eds) Web and Internet Economics. WINE 2020. Lecture Notes in Computer Science(), vol 12495. Springer, Cham. https://doi.org/10.1007/978-3-030-64946-3_18
Download citation
DOI: https://doi.org/10.1007/978-3-030-64946-3_18
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-64945-6
Online ISBN: 978-3-030-64946-3
eBook Packages: Computer ScienceComputer Science (R0)