{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,8,21]],"date-time":"2024-08-21T23:34:21Z","timestamp":1724283261103},"reference-count":41,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2021,9,8]],"date-time":"2021-09-08T00:00:00Z","timestamp":1631059200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,9,8]],"date-time":"2021-09-08T00:00:00Z","timestamp":1631059200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100003407","name":"Ministero dell\u2019Istruzione, dell\u2019Universit\u00e0 e della Ricerca","doi-asserted-by":"publisher","award":["ALGADIMAR"],"id":[{"id":"10.13039\/501100003407","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100012740","name":"Gruppo Nazionale per l\u2019Analisi Matematica, la Probabilit\u00e0 e le loro Applicazioni","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100012740","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002847","name":"Ministerio de Educaci\u00f3n, Gobierno de Chile","doi-asserted-by":"publisher","award":["FONDECYT 1171501","ANID\/PIA\/ACT192094"],"id":[{"id":"10.13039\/501100002847","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000921","name":"European Cooperation in Science and Technology","doi-asserted-by":"publisher","award":["GAMENET"],"id":[{"id":"10.13039\/501100000921","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2024,1]]},"abstract":"Abstract<\/jats:title>The price of anarchy has become a standard measure of the efficiency of equilibria in games. Most of the literature in this area has focused on establishing worst-case bounds for specific classes of games, such as routing games or more general congestion games. Recently, the price of anarchy in routing games has been studied as a function of the traffic demand, providing asymptotic results in light and heavy traffic. The aim of this paper is to study the price of anarchy in nonatomic routing games in the intermediate region of the demand. To achieve this goal, we begin by establishing some smoothness properties of Wardrop equilibria and social optima for general smooth costs. In the case of affine costs we show that the equilibrium is piecewise linear, with break points at the demand levels at which the set of active paths changes. We prove that the number of such break points is finite, although it can be exponential in the size of the network. Exploiting a scaling law between the equilibrium and the social optimum, we derive a similar behavior for the optimal flows. We then prove that in any interval between break points the price of anarchy is smooth and it is either monotone (decreasing or increasing) over the full interval, or it decreases up to a certain minimum point in the interior of the interval and increases afterwards. We deduce that for affine costs the maximum of the price of anarchy can only occur at the break points. For general costs we provide counterexamples showing that the set of break points is not always finite.<\/jats:p>","DOI":"10.1007\/s10107-021-01701-7","type":"journal-article","created":{"date-parts":[[2021,9,8]],"date-time":"2021-09-08T14:19:43Z","timestamp":1631110783000},"page":"531-558","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["The price of anarchy in routing games as a function of the demand"],"prefix":"10.1007","volume":"203","author":[{"ORCID":"http:\/\/orcid.org\/0000-0001-9442-344X","authenticated-orcid":false,"given":"Roberto","family":"Cominetti","sequence":"first","affiliation":[]},{"ORCID":"http:\/\/orcid.org\/0000-0002-8186-0023","authenticated-orcid":false,"given":"Valerio","family":"Dose","sequence":"additional","affiliation":[]},{"ORCID":"http:\/\/orcid.org\/0000-0001-6473-794X","authenticated-orcid":false,"given":"Marco","family":"Scarsini","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,9,8]]},"reference":[{"key":"1701_CR1","volume-title":"Infinite Dimensional Analysis","author":"CD Aliprantis","year":"2006","unstructured":"Aliprantis, C.D., Border, K.C.: Infinite Dimensional Analysis, 3rd edn. Springer, Berlin (2006)","edition":"3"},{"key":"1701_CR2","volume-title":"Studies in the Economics of Transportation","author":"MJ Beckmann","year":"1956","unstructured":"Beckmann, M.J., McGuire, C., Winsten, C.B.: Studies in the Economics of Transportation. Yale University Press, New Haven (1956)"},{"issue":"2","key":"1701_CR3","doi-asserted-by":"publisher","first-page":"411","DOI":"10.1287\/opre.2019.1894","volume":"68","author":"R Colini-Baldeschi","year":"2020","unstructured":"Colini-Baldeschi, R., Cominetti, R., Mertikopoulos, P., Scarsini, M.: When is selfish routing bad? The price of anarchy in light and heavy traffic. Oper. Res. 68(2), 411\u2013434 (2020). https:\/\/doi.org\/10.1287\/opre.2019.1894","journal-title":"Oper. Res."},{"issue":"1","key":"1701_CR4","doi-asserted-by":"publisher","first-page":"90","DOI":"10.1007\/s00224-017-9834-1","volume":"63","author":"R Colini-Baldeschi","year":"2019","unstructured":"Colini-Baldeschi, R., Cominetti, R., Scarsini, M.: Price of anarchy for highly congested routing games in parallel networks. Theory Comput. Syst. 63(1), 90\u2013113 (2019). https:\/\/doi.org\/10.1007\/s00224-017-9834-1","journal-title":"Theory Comput. Syst."},{"key":"1701_CR5","doi-asserted-by":"publisher","unstructured":"Colini-Baldeschi, R., Klimm, M., Scarsini, M.: Demand-independent optimal tolls. In: 45th International Colloquium on Automata, Languages, and Programming, LIPIcs. Leibniz Int. Proc. Inform., vol. 107, pp. Art. No. 151, 14. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern (2018). https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2018.151","DOI":"10.4230\/LIPIcs.ICALP.2018.151"},{"key":"1701_CR6","doi-asserted-by":"publisher","unstructured":"Cominetti, R., Scarsini, M., Schr\u00f6der, M., Stier-Moses, N.: Price of anarchy in stochastic atomic congestion games with affine costs. In: Proceedings of The Twentieth ACM Conference on Economics and Computation (ACM EC \u201919) (2019). https:\/\/doi.org\/10.1145\/3328526.3329579","DOI":"10.1145\/3328526.3329579"},{"issue":"4","key":"1701_CR7","doi-asserted-by":"publisher","first-page":"961","DOI":"10.1287\/moor.1040.0098","volume":"29","author":"JR Correa","year":"2004","unstructured":"Correa, J.R., Schulz, A.S., Stier-Moses, N.E.: Selfish routing in capacitated networks. Math. Oper. Res. 29(4), 961\u2013976 (2004). https:\/\/doi.org\/10.1287\/moor.1040.0098","journal-title":"Math. Oper. Res."},{"issue":"2","key":"1701_CR8","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1287\/opre.1070.0383","volume":"55","author":"JR Correa","year":"2007","unstructured":"Correa, J.R., Schulz, A.S., Stier-Moses, N.E.: Fast, fair, and efficient flows in networks. Oper. Res. 55(2), 215\u2013225 (2007). https:\/\/doi.org\/10.1287\/opre.1070.0383","journal-title":"Oper. Res."},{"issue":"2","key":"1701_CR9","doi-asserted-by":"publisher","first-page":"457","DOI":"10.1016\/j.geb.2008.01.001","volume":"64","author":"JR Correa","year":"2008","unstructured":"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\u2013469 (2008). https:\/\/doi.org\/10.1016\/j.geb.2008.01.001","journal-title":"Games Econom. Behav."},{"key":"1701_CR10","doi-asserted-by":"publisher","DOI":"10.1002\/9780470400531.eorms0962","volume-title":"Encyclopedia of Operations Research and Management Science","author":"JR Correa","year":"2011","unstructured":"Correa, J.R., Stier-Moses, N.E.: Wardrop equilibria. In: Cochran, J.J. (ed.) Encyclopedia of Operations Research and Management Science. Wiley, New York (2011). https:\/\/doi.org\/10.1002\/9780470400531.eorms0962"},{"issue":"2","key":"1701_CR11","doi-asserted-by":"publisher","first-page":"174","DOI":"10.1007\/BF02612357","volume":"28","author":"S Dafermos","year":"1984","unstructured":"Dafermos, S., Nagurney, A.: Sensitivity analysis for the asymmetric network equilibrium problem. Math. Program. 28(2), 174\u2013184 (1984). https:\/\/doi.org\/10.1007\/BF02612357","journal-title":"Math. Program."},{"key":"1701_CR12","doi-asserted-by":"publisher","first-page":"91","DOI":"10.6028\/jres.073B.010","volume":"73B","author":"SC Dafermos","year":"1969","unstructured":"Dafermos, S.C., Sparrow, F.T.: The traffic assignment problem for a general network. J. Res. Nat. Bur. Standards Sect. B 73B, 91\u2013118 (1969)","journal-title":"J. Res. Nat. Bur. Standards Sect. B"},{"key":"1701_CR13","doi-asserted-by":"publisher","unstructured":"Dumrauf, D., Gairing, M.: Price of anarchy for polynomial Wardrop games. In: WINE \u201906: Proceedings of the 2nd Conference on Web and Internet Economics, pp. 319\u2013330. Springer, Berlin (2006). https:\/\/doi.org\/10.1007\/11944874_29","DOI":"10.1007\/11944874_29"},{"issue":"1","key":"1701_CR14","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/s00224-009-9196-4","volume":"47","author":"M Englert","year":"2010","unstructured":"Englert, M., Franke, T., Olbrich, L.: Sensitivity of Wardrop equilibria. Theory Comput. Syst. 47(1), 3\u201314 (2010). https:\/\/doi.org\/10.1007\/s00224-009-9196-4","journal-title":"Theory Comput. Syst."},{"issue":"4","key":"1701_CR15","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1016\/0191-2615(79)90023-7","volume":"13","author":"C Fisk","year":"1979","unstructured":"Fisk, C.: More paradoxes in the equilibrium assignment problem. Transport. Res. Part B 13(4), 305\u2013309 (1979). https:\/\/doi.org\/10.1016\/0191-2615(79)90023-7","journal-title":"Transport. Res. Part B"},{"key":"1701_CR16","doi-asserted-by":"crossref","unstructured":"Florian, M., Hearn, D.: Network equilibrium models and algorithms. In: M.H. et\u00a0al (ed.) Handbooks in Operation Research and Management Science, vol.\u00a08. North Holland, Amsterdam (1995)","DOI":"10.1016\/S0927-0507(05)80110-0"},{"issue":"3","key":"1701_CR17","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1016\/0191-2615(84)90034-1","volume":"18","author":"M Fukushima","year":"1984","unstructured":"Fukushima, M.: On the dual approach to the traffic assignment problem. Transport. Res. Part B 18(3), 235\u2013245 (1984). https:\/\/doi.org\/10.1016\/0191-2615(84)90034-1","journal-title":"Transport. Res. Part B"},{"key":"1701_CR18","doi-asserted-by":"publisher","unstructured":"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. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern (2019). https:\/\/doi.org\/10.4230\/LIPIcs.STACS.2019.31","DOI":"10.4230\/LIPIcs.STACS.2019.31"},{"issue":"3","key":"1701_CR19","doi-asserted-by":"publisher","first-page":"208","DOI":"10.1287\/trsc.12.3.208","volume":"12","author":"MA Hall","year":"1978","unstructured":"Hall, M.A.: Properties of the equilibrium state in transportation networks. Transport. Sci. 12(3), 208\u2013216 (1978). https:\/\/doi.org\/10.1287\/trsc.12.3.208","journal-title":"Transport. Sci."},{"issue":"1","key":"1701_CR20","doi-asserted-by":"publisher","first-page":"4","DOI":"10.1016\/j.trb.2005.12.004","volume":"41","author":"M Josefsson","year":"2007","unstructured":"Josefsson, M., Patriksson, M.: Sensitivity analysis of separable traffic equilibrium equilibria with application to bilevel optimization in network design. Transport. Res. Part B 41(1), 4\u201331 (2007). https:\/\/doi.org\/10.1016\/j.trb.2005.12.004","journal-title":"Transport. Res. Part B"},{"key":"1701_CR21","doi-asserted-by":"publisher","unstructured":"Klimm, M., Warode, P.: Computing all Wardrop equilibria parametrized by the flow demand. In: Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 917\u2013934. SIAM, Philadelphia (2019). https:\/\/doi.org\/10.1137\/1.9781611975482.56","DOI":"10.1137\/1.9781611975482.56"},{"key":"1701_CR22","doi-asserted-by":"crossref","unstructured":"Klimm, M., Warode, P.: Parametric computation of minimum-cost flows with piecewise quadratic costs. Math. Oper. Res. (forthcoming) (2021)","DOI":"10.1287\/moor.2021.1151"},{"key":"1701_CR23","doi-asserted-by":"publisher","unstructured":"Koutsoupias, E., Papadimitriou, C.: Worst-case equilibria. In: STACS 99 (Trier), Lecture Notes in Comput. Sci., vol. 1563, pp. 404\u2013413. Springer, Berlin (1999). https:\/\/doi.org\/10.1007\/3-540-49116-3_38","DOI":"10.1007\/3-540-49116-3_38"},{"issue":"2","key":"1701_CR24","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1016\/j.geb.2005.09.005","volume":"57","author":"I Milchtaich","year":"2006","unstructured":"Milchtaich, I.: Network topology and the efficiency of equilibrium. Games Econom. Behav. 57(2), 321\u2013346 (2006). https:\/\/doi.org\/10.1016\/j.geb.2005.09.005","journal-title":"Games Econom. Behav."},{"key":"1701_CR25","doi-asserted-by":"publisher","first-page":"340","DOI":"10.1007\/978-3-319-71924-5_24","volume-title":"Web and Internet Economics","author":"B Monnot","year":"2017","unstructured":"Monnot, B., Benita, F., Piliouras, G.: Routing games in the wild: efficiency, equilibration and regret. In: Devanur, N.R., Lu, P. (eds.) Web and Internet Economics, pp. 340\u2013353. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-71924-5_24"},{"key":"1701_CR26","doi-asserted-by":"publisher","unstructured":"O\u2019Hare, S.J., Connors, R.D., Watling, D.P.: Mechanisms that govern how the price of anarchy varies with travel demand. Transport. Res. Part B 84, 55\u201380 (2016). https:\/\/doi.org\/10.1016\/j.trb.2015.12.005","DOI":"10.1016\/j.trb.2015.12.005"},{"key":"1701_CR27","doi-asserted-by":"publisher","unstructured":"Papadimitriou, C.: Algorithms, games, and the internet. In: Proceedings of the Thirty-Third Annual ACM Symposium on Theory of Computing, pp. 749\u2013753. ACM, New York (2001). https:\/\/doi.org\/10.1145\/380752.380883","DOI":"10.1145\/380752.380883"},{"issue":"3","key":"1701_CR28","doi-asserted-by":"publisher","first-page":"258","DOI":"10.1287\/trsc.1030.0043","volume":"38","author":"M Patriksson","year":"2004","unstructured":"Patriksson, M.: Sensitivity analysis of traffic equilibria. Transport. Sci. 38(3), 258\u2013281 (2004). https:\/\/doi.org\/10.1287\/trsc.1030.0043","journal-title":"Transport. Sci."},{"key":"1701_CR29","volume-title":"The Economics of Welfare","author":"AC Pigou","year":"1920","unstructured":"Pigou, A.C.: The Economics of Welfare, 1st edn. Macmillan and Co., London (1920)","edition":"1"},{"key":"1701_CR30","unstructured":"Rockafellar, R.T.: Convex Analysis. Princeton Landmarks in Mathematics. Princeton University Press, Princeton (1997). (Reprint of the 1970 original)"},{"issue":"2","key":"1701_CR31","doi-asserted-by":"publisher","first-page":"341","DOI":"10.1016\/S0022-0000(03)00044-8","volume":"67","author":"T Roughgarden","year":"2003","unstructured":"Roughgarden, T.: The price of anarchy is independent of the network topology. J. Comput. Syst. Sci. 67(2), 341\u2013364 (2003). https:\/\/doi.org\/10.1016\/S0022-0000(03)00044-8","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"1701_CR32","doi-asserted-by":"publisher","first-page":"236","DOI":"10.1145\/506147.506153","volume":"49","author":"T Roughgarden","year":"2002","unstructured":"Roughgarden, T., Tardos, E.: How bad is selfish routing? J. ACM 49(2), 236\u2013259 (2002). https:\/\/doi.org\/10.1145\/506147.506153","journal-title":"J. ACM"},{"issue":"2","key":"1701_CR33","doi-asserted-by":"publisher","first-page":"389","DOI":"10.1016\/j.geb.2003.06.004","volume":"47","author":"T Roughgarden","year":"2004","unstructured":"Roughgarden, T., Tardos, E.: Bounding the inefficiency of equilibria in nonatomic congestion games. Games Econ. Behav. 47(2), 389\u2013403 (2004). https:\/\/doi.org\/10.1016\/j.geb.2003.06.004","journal-title":"Games Econ. Behav."},{"issue":"3","key":"1701_CR34","doi-asserted-by":"publisher","first-page":"628","DOI":"10.1137\/0326037","volume":"26","author":"A Shapiro","year":"1988","unstructured":"Shapiro, A.: Sensitivity analysis of nonlinear programs and differentiability properties of metric projections. SIAM J. Control. Optim. 26(3), 628\u2013645 (1988). https:\/\/doi.org\/10.1137\/0326037","journal-title":"SIAM J. Control. Optim."},{"issue":"3","key":"1701_CR35","doi-asserted-by":"publisher","first-page":"781","DOI":"10.1007\/s11590-020-01552-9","volume":"14","author":"M Takalloo","year":"2020","unstructured":"Takalloo, M., Kwon, C.: Sensitivity of Wardrop equilibria: revisited. Optim. Lett. 14(3), 781\u2013796 (2020). https:\/\/doi.org\/10.1007\/s11590-020-01552-9","journal-title":"Optim. Lett."},{"issue":"1","key":"1701_CR36","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1287\/opre.14.1.45","volume":"14","author":"JA Tomlin","year":"1966","unstructured":"Tomlin, J.A.: Minimum-cost multicommodity network flows. Oper. Res. 14(1), 45\u201351 (1966). https:\/\/doi.org\/10.1287\/opre.14.1.45","journal-title":"Oper. Res."},{"key":"1701_CR37","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1680\/ipeds.1952.11259","volume":"1","author":"JG Wardrop","year":"1952","unstructured":"Wardrop, J.G.: Some theoretical aspects of road traffic research. Proc. Inst. Civil Eng. Part II 1, 325\u2013378 (1952). https:\/\/doi.org\/10.1680\/ipeds.1952.11259","journal-title":"Proc. Inst. Civil Eng. Part II"},{"key":"1701_CR38","unstructured":"Wu, Z., M\u00f6hring, R.: A sensitivity analysis for the price of anarchy in non-atomic congestion games. arXiv:2007.13979"},{"issue":"2","key":"1701_CR39","doi-asserted-by":"publisher","first-page":"410","DOI":"10.1287\/opre.2020.2036","volume":"69","author":"Z Wu","year":"2021","unstructured":"Wu, Z., M\u00f6hring, R.H., Chen, Y., Xu, D.: Selfishness need not be bad. Oper. Res. 69(2), 410\u2013435 (2021). https:\/\/doi.org\/10.1287\/opre.2020.2036","journal-title":"Oper. Res."},{"issue":"12","key":"1701_CR40","doi-asserted-by":"publisher","first-page":"128701","DOI":"10.1103\/PhysRevLett.101.128701","volume":"101","author":"H Youn","year":"2008","unstructured":"Youn, H., Gastner, M.T., Jeong, H.: Price of anarchy in transportation networks: efficiency and optimality control. Phys. Rev. Lett. 101(12), 128701 (2008)","journal-title":"Phys. Rev. Lett."},{"key":"1701_CR41","doi-asserted-by":"publisher","first-page":"049905","DOI":"10.1103\/PhysRevLett.102.049905","volume":"102","author":"H Youn","year":"2009","unstructured":"Youn, H., Gastner, M.T., Jeong, H.: Erratum: Price of anarchy in transportation networks: Efficiency and optimality control. Phys. Rev. Lett. 102, 049905 (2009). https:\/\/doi.org\/10.1103\/PhysRevLett.102.049905","journal-title":"Phys. Rev. Lett."}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-021-01701-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-021-01701-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-021-01701-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,2,9]],"date-time":"2024-02-09T18:05:43Z","timestamp":1707501943000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-021-01701-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,9,8]]},"references-count":41,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2024,1]]}},"alternative-id":["1701"],"URL":"https:\/\/doi.org\/10.1007\/s10107-021-01701-7","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,9,8]]},"assertion":[{"value":"16 July 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 July 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 September 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}
