{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,16]],"date-time":"2026-01-16T08:41:51Z","timestamp":1768552911567,"version":"3.49.0"},"reference-count":51,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2022,11,23]],"date-time":"2022-11-23T00:00:00Z","timestamp":1669161600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,11,23]],"date-time":"2022-11-23T00:00:00Z","timestamp":1669161600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["OR Spectrum"],"published-print":{"date-parts":[[2023,3]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The price of anarchy is the most well-known measure for quantifying the inefficiency of equilibrium flows in traffic networks and routing games. In this work, we give unifying price of anarchy bounds for atomic and non-atomic parallel link routing games with polynomial cost functions under various cost objectives including the arithmetic mean, geometric mean and worst-case cost objective. We do this through the study of the generalized <jats:italic>p<\/jats:italic>-mean as cost objective, and obtain upper bounds on the price of anarchy in terms of this parameter <jats:italic>p<\/jats:italic>. Our bounds unify existing results from the literature, and, in particular, give alternative proofs for price of anarchy results in parallel link routing games with polynomial cost functions under the geometric mean objective obtained by Vinci et al. (ACM Trans Econ Comput 10(2):41, 2022). We recover those simply as a limiting case. To the best of our knowledge, these are the first price of anarchy bounds that capture multiple cost objectives simultaneously in a closed-form expression.<\/jats:p>","DOI":"10.1007\/s00291-022-00696-7","type":"journal-article","created":{"date-parts":[[2022,11,24]],"date-time":"2022-11-24T19:41:24Z","timestamp":1669318884000},"page":"27-55","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Price of anarchy for parallel link networks with generalized mean objective"],"prefix":"10.1007","volume":"45","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4304-7282","authenticated-orcid":false,"given":"Pieter","family":"Kleer","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,11,23]]},"reference":[{"issue":"5","key":"696_CR1","doi-asserted-by":"publisher","first-page":"1211","DOI":"10.1137\/090748986","volume":"40","author":"S Aland","year":"2011","unstructured":"Aland S, Dumrauf D, Gairing M, Monien B, Schoppmann F (2011) Exact price of anarchy for polynomial congestion games. SIAM J Comput 40(5):1211\u20131233","journal-title":"SIAM J Comput"},{"issue":"4","key":"696_CR2","doi-asserted-by":"publisher","first-page":"1602","DOI":"10.1137\/070680096","volume":"38","author":"E Anshelevich","year":"2008","unstructured":"Anshelevich E, Dasgupta A, Kleinberg J, Tardos \u00c9, Wexler T, Roughgarden T (2008) The price of stability for network design with fair cost allocation. SIAM J Comput 38(4):1602\u20131623","journal-title":"SIAM J Comput"},{"key":"696_CR3","doi-asserted-by":"crossref","unstructured":"Awerbuch B, Azar Y, Grove EF, Kao M-Y, Krishnan P, Vitter JS (1995) Load balancing in the l\/sub p\/norm. In: Proceedings of IEEE 36th annual foundations of computer science. IEEE, pp 383\u2013391","DOI":"10.1109\/SFCS.1995.492494"},{"issue":"4","key":"696_CR5","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2629666","volume":"2","author":"K Bhawalkar","year":"2014","unstructured":"Bhawalkar K, Gairing M, Roughgarden T (2014) Weighted congestion games: the price of anarchy, universal worst-case examples, and tightness. ACM Trans Econ Comput 2(4):1\u201323","journal-title":"ACM Trans Econ Comput"},{"key":"696_CR8","unstructured":"Bil\u00f2 V, Vinci C (2017) On the impact of singleton strategies in congestion games. In: 25th annual European symposium on algorithms. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik"},{"issue":"3","key":"696_CR6","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3355946","volume":"7","author":"V Bil\u00f2","year":"2019","unstructured":"Bil\u00f2 V, Vinci C (2019) Dynamic taxes for polynomial congestion games. ACM Trans Econ Comput 7(3):1\u201336","journal-title":"ACM Trans Econ Comput"},{"key":"696_CR9","doi-asserted-by":"crossref","unstructured":"Bonifaci V, Salek M, Sch\u00e4fer G (2011) Efficiency of restricted tolls in non-atomic network routing games. In: International symposium on algorithmic game theory. Springer, pp 302\u2212313","DOI":"10.1007\/978-3-642-24829-0_27"},{"issue":"4","key":"696_CR10","doi-asserted-by":"publisher","first-page":"446","DOI":"10.1287\/trsc.1050.0127","volume":"39","author":"D Braess","year":"2005","unstructured":"Braess D, Nagurney A, Wakolbinger T (2005) On a paradox of traffic planning. Transp Sci 39(4):446\u2013450","journal-title":"Transp Sci"},{"key":"696_CR11","unstructured":"Caragiannis I (2008) Better bounds for online load balancing on unrelated machines. In: Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, pp 972\u2013981"},{"issue":"1","key":"696_CR12","doi-asserted-by":"publisher","first-page":"13:1","DOI":"10.1145\/1868237.1868251","volume":"7","author":"I Caragiannis","year":"2010","unstructured":"Caragiannis I, Kaklamanis C, Kanellopoulos P (2010) Taxes for linear atomic congestion games. ACM Trans Algorithms 7(1):13:1-13:31","journal-title":"ACM Trans Algorithms"},{"issue":"3","key":"696_CR13","doi-asserted-by":"publisher","first-page":"606","DOI":"10.1007\/s00453-010-9427-8","volume":"61","author":"I Caragiannis","year":"2011","unstructured":"Caragiannis I, Flammini M, Kaklamanis C, Kanellopoulos P, Moscardelli L (2011) Tight bounds for selfish and greedy load balancing. Algorithmica 61(3):606\u2013637","journal-title":"Algorithmica"},{"issue":"4","key":"696_CR14","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1145\/2597893","volume":"2","author":"P-A Chen","year":"2014","unstructured":"Chen P-A, de Keijzer B, Kempe D, Sch\u00e4fer G (2014) Altruism and its impact on the price of anarchy. ACM Trans Econ Comput 2(4):171\u20131745","journal-title":"ACM Trans Econ Comput"},{"issue":"2","key":"696_CR15","first-page":"1","volume":"4","author":"G Christodoulou","year":"2015","unstructured":"Christodoulou G, Gairing M (2015) Price of stability in polynomial congestion games. ACM Trans Econ Comput 4(2):1\u201317","journal-title":"ACM Trans Econ Comput (TEAC)"},{"key":"696_CR18","doi-asserted-by":"crossref","unstructured":"Christodoulou G, Koutsoupias E (2005) The price of anarchy of finite congestion games. In: Proceedings of the thirty-seventh annual ACM symposium on theory of computing, pp 67\u201373","DOI":"10.1145\/1060590.1060600"},{"issue":"1","key":"696_CR16","doi-asserted-by":"publisher","first-page":"116","DOI":"10.1007\/s00453-010-9449-2","volume":"61","author":"G Christodoulou","year":"2011","unstructured":"Christodoulou G, Koutsoupias E, Spirakis PG (2011) On the performance of approximate equilibria in congestion games. Algorithmica 61(1):116\u2013140","journal-title":"Algorithmica"},{"issue":"5","key":"696_CR17","doi-asserted-by":"publisher","first-page":"1544","DOI":"10.1137\/18M1207880","volume":"48","author":"G Christodoulou","year":"2019","unstructured":"Christodoulou G, Gairing M, Giannakopoulos Y, Spirakis PG (2019) The price of stability of weighted congestion games. SIAM J Comput 48(5):1544\u20131582","journal-title":"SIAM J Comput"},{"issue":"1","key":"696_CR19","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 (2019) Price of anarchy for highly congested routing games in parallel networks. Theory Comput Syst 63(1):90\u2013113","journal-title":"Theory Comput Syst"},{"key":"696_CR20","doi-asserted-by":"crossref","unstructured":"Cominetti R, Scarsini M, Schr\u00f6der M, Stier-Moses NE (2019) Price of anarchy in stochastic atomic congestion games with affine costs. In: Proceedings of the 2019 ACM conference on economics and computation, pp 579\u2013580","DOI":"10.1145\/3328526.3329579"},{"issue":"4","key":"696_CR21","doi-asserted-by":"publisher","first-page":"961","DOI":"10.1287\/moor.1040.0098","volume":"29","author":"JR Correa","year":"2004","unstructured":"Correa JR, Schulz AS, Stier-Moses NE (2004) Selfish routing in capacitated networks. Math Oper Res 29(4):961\u2013976","journal-title":"Math Oper Res"},{"key":"696_CR22","doi-asserted-by":"crossref","unstructured":"Czumaj A, V\u00f6cking B (2007) Tight bounds for worst-case equilibria. ACM Trans Algorithms 3(1):1\u201317","DOI":"10.1145\/1186810.1186814"},{"issue":"1","key":"696_CR23","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1287\/moor.11.1.1","volume":"11","author":"P Dubey","year":"1986","unstructured":"Dubey P (1986) Inefficiency of nash equilibria. Math Oper Res 11(1):1\u20138","journal-title":"Math Oper Res"},{"issue":"1","key":"696_CR24","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1007\/s00224-009-9205-7","volume":"47","author":"D Fotakis","year":"2010","unstructured":"Fotakis D (2010) Congestion games with linearly independent paths: convergence time and price of anarchy. Theory Comput Syst 47(1):113\u2013136","journal-title":"Theory Comput Syst"},{"key":"696_CR25","doi-asserted-by":"crossref","unstructured":"Fotakis D, Kalimeris D, Lianeas T (2015) Improving selfish routing for risk-averse players. In: International conference on web and internet economics. Springer, pp 328\u2013342","DOI":"10.1007\/978-3-662-48995-6_24"},{"issue":"1\u20133","key":"696_CR26","doi-asserted-by":"publisher","first-page":"116","DOI":"10.1016\/j.tcs.2006.07.055","volume":"369","author":"M Gairing","year":"2006","unstructured":"Gairing M, L\u00fccking T, Mavronicolas M, Monien B (2006) The price of anarchy for polynomial social cost. Theoret Comput Sci 369(1\u20133):116\u2013135","journal-title":"Theoret Comput Sci"},{"issue":"7","key":"696_CR27","doi-asserted-by":"publisher","first-page":"1199","DOI":"10.1016\/j.jcss.2008.07.001","volume":"74","author":"M Gairing","year":"2008","unstructured":"Gairing M, L\u00fccking T, Mavronicolas M, Monien B, Rode M (2008) Nash equilibria in discrete routing games with convex latency functions. J Comput Syst Sci 74(7):1199\u20131225","journal-title":"J Comput Syst Sci"},{"key":"696_CR28","doi-asserted-by":"crossref","unstructured":"Gairing M, Schoppmann F (2007) Total latency in singleton congestion games. In: International workshop on web and internet economics. Springer, pp 381\u2013387","DOI":"10.1007\/978-3-540-77105-0_42"},{"issue":"3","key":"696_CR29","doi-asserted-by":"publisher","first-page":"947","DOI":"10.1016\/j.ejor.2019.01.059","volume":"276","author":"T Harks","year":"2019","unstructured":"Harks T, Schr\u00f6der M, Vermeulen D (2019) Toll caps in privatized road networks. Eur J Oper Res 276(3):947\u2013956","journal-title":"Eur J Oper Res"},{"issue":"2","key":"696_CR30","doi-asserted-by":"publisher","first-page":"155","DOI":"10.2307\/1907266","volume":"18","author":"F John","year":"1950","unstructured":"John F (1950) Nash. The bargaining problem. Econometrica 18(2):155\u2013162","journal-title":"Econometrica"},{"key":"696_CR34","doi-asserted-by":"crossref","unstructured":"Kleer P, Sch\u00e4fer G (2017) Path deviations outperform approximate stability in heterogeneous congestion games. In: International symposium on algorithmic game theory. Springer, pp 212\u2013224","DOI":"10.1007\/978-3-319-66700-3_17"},{"issue":"1","key":"696_CR31","doi-asserted-by":"publisher","first-page":"54","DOI":"10.1007\/s00224-017-9829-y","volume":"63","author":"P Kleer","year":"2019","unstructured":"Kleer P, Sch\u00e4fer G (2019a) The impact of worst-case deviations in non-atomic network routing games. Theory Comput Syst 63(1):54\u201389","journal-title":"Theory Comput Syst"},{"key":"696_CR32","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1016\/j.tcs.2018.04.025","volume":"754","author":"P Kleer","year":"2019","unstructured":"Kleer P, Sch\u00e4fer G (2019b) Tight inefficiency bounds for perception-parameterized affine congestion games. Theoret Comput Sci 754:65\u201387","journal-title":"Theoret Comput Sci"},{"issue":"1","key":"696_CR33","doi-asserted-by":"publisher","first-page":"523","DOI":"10.1007\/s10107-020-01546-6","volume":"190","author":"P Kleer","year":"2021","unstructured":"Kleer P, Sch\u00e4fer G (2021) Computation and efficiency of potential function minimizers of combinatorial congestion games. Math Program 190(1):523\u2013560","journal-title":"Math Program"},{"key":"696_CR35","doi-asserted-by":"crossref","unstructured":"Klimm M, Schmand D, T\u00f6nnis A (2019) The online best reply algorithm for resource allocation problems. In: International symposium on algorithmic game theory. Springer, pp 200\u2013215","DOI":"10.1007\/978-3-030-30473-7_14"},{"issue":"2","key":"696_CR36","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1016\/j.cosrev.2009.04.003","volume":"3","author":"E Koutsoupias","year":"2009","unstructured":"Koutsoupias E, Papadimitriou C (2009) Worst-case equilibria. Comput Sci Rev 3(2):65\u201369","journal-title":"Comput Sci Rev"},{"key":"696_CR37","doi-asserted-by":"crossref","unstructured":"Koutsoupias E, Papadimitriou C (1999) Worst-case equilibria. In: Proceedings of the 16th annual conference on theoretical aspects of computer science, pp 404\u2013413","DOI":"10.1007\/3-540-49116-3_38"},{"issue":"1","key":"696_CR38","first-page":"38","volume":"44","author":"T Lianeas","year":"2019","unstructured":"Lianeas T, Nikolova E, Stier-Moses NE (2019) Risk-averse selfish routing. Math Oper Res 44(1):38\u201357","journal-title":"Math Oper Res"},{"key":"696_CR39","doi-asserted-by":"crossref","unstructured":"Monnot B, Benita F, Piliouras G (2017) Routing games in the wild: efficiency, equilibration and regret. In: International conference on web and internet economics. Springer, pp 340\u2013353","DOI":"10.1007\/978-3-319-71924-5_24"},{"issue":"2","key":"696_CR40","doi-asserted-by":"publisher","first-page":"366","DOI":"10.1287\/opre.2013.1246","volume":"62","author":"E Nikolova","year":"2014","unstructured":"Nikolova E, Stier-Moses NE (2014) A mean-risk model for the traffic assignment problem with stochastic travel times. Oper Res 62(2):366\u2013382","journal-title":"Oper Res"},{"key":"696_CR41","volume-title":"The economics of welfare","author":"AC Pigou","year":"1920","unstructured":"Pigou AC (1920) The economics of welfare. Macmillan, New York"},{"issue":"1","key":"696_CR42","first-page":"51","volume":"5","author":"G Piliouras","year":"2016","unstructured":"Piliouras G, Nikolova E, Shamma JS (2016) Risk sensitivity of price of anarchy under uncertainty. ACM Trans Econ Comput 5(1):51\u2013527","journal-title":"ACM Trans Econ Comput"},{"key":"696_CR43","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1007\/BF01737559","volume":"2","author":"RW Rosenthal","year":"1973","unstructured":"Rosenthal RW (1973) A class of games possessing pure-strategy Nash equilibria. Int J Game Theory 2:65\u201367","journal-title":"Int J Game Theory"},{"issue":"2","key":"696_CR44","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 (2003) The price of anarchy is independent of the network topology. J Comput Syst Sci 67(2):341\u2013364","journal-title":"J Comput Syst Sci"},{"key":"696_CR45","volume-title":"Selfish routing and the price of anarchy","author":"T Roughgarden","year":"2005","unstructured":"Roughgarden T (2005) Selfish routing and the price of anarchy. MIT Press, Cambridge"},{"issue":"5","key":"696_CR46","doi-asserted-by":"publisher","first-page":"32","DOI":"10.1145\/2806883","volume":"62","author":"T Roughgarden","year":"2015","unstructured":"Roughgarden T (2015) Intrinsic robustness of the price of anarchy. J ACM 62(5):32","journal-title":"J ACM"},{"issue":"2","key":"696_CR47","doi-asserted-by":"publisher","first-page":"236","DOI":"10.1145\/506147.506153","volume":"49","author":"T Roughgarden","year":"2002","unstructured":"Roughgarden T, Tardos \u00c9 (2002) How bad is selfish routing? J ACM 49(2):236\u2013259","journal-title":"J ACM"},{"key":"696_CR48","doi-asserted-by":"crossref","unstructured":"Schr\u00f6der M (2020) Price of anarchy in congestion games with altruistic\/spiteful players. In: International symposium on algorithmic game theory. Springer, pp 146\u2212159","DOI":"10.1007\/978-3-030-57980-7_10"},{"issue":"6","key":"696_CR49","doi-asserted-by":"publisher","first-page":"1555","DOI":"10.1287\/trsc.2020.0973","volume":"54","author":"M Takalloo","year":"2020","unstructured":"Takalloo M, Kwon C (2020) On the price of satisficing in network user equilibria. Transp Sci 54(6):1555\u20131570","journal-title":"Transp Sci"},{"key":"696_CR50","unstructured":"United States. Bureau of\u00a0Public\u00a0Roads (1964) Traffic assignment manual for application with a large, high speed computer, vol\u00a037. US Department of Commerce, Bureau of Public Roads (1964)"},{"key":"696_CR4","doi-asserted-by":"crossref","unstructured":"Vinci C, Bil\u00f2 V, Monaco G, Moscardelli L (2022) Nash social welfare in selfish and online load balancing. ACM Trans Econ Comput 10(2):41. https:\/\/dl.acm.org\/doi\/full\/10.1145\/3544978","DOI":"10.1145\/3544978"},{"key":"696_CR51","first-page":"325","volume":"1","author":"JG Wardrop","year":"1952","unstructured":"Wardrop JG (1952) Some theoretical aspects of road traffic research. Proc Inst Civ Eng 1:325\u2013378","journal-title":"Proc Inst Civ Eng"},{"issue":"4","key":"696_CR52","doi-asserted-by":"publisher","first-page":"538","DOI":"10.1109\/JPROC.2018.2790405","volume":"106","author":"J Zhang","year":"2018","unstructured":"Zhang J, Pourazarm S, Cassandras CG, Paschalidis IC (2018) The price of anarchy in transportation networks: data-driven evaluation and reduction strategies. Proc IEEE 106(4):538\u2013553","journal-title":"Proc IEEE"}],"container-title":["OR Spectrum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00291-022-00696-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00291-022-00696-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00291-022-00696-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,13]],"date-time":"2023-02-13T16:18:08Z","timestamp":1676305088000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00291-022-00696-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,11,23]]},"references-count":51,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,3]]}},"alternative-id":["696"],"URL":"https:\/\/doi.org\/10.1007\/s00291-022-00696-7","relation":{},"ISSN":["0171-6468","1436-6304"],"issn-type":[{"value":"0171-6468","type":"print"},{"value":"1436-6304","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,11,23]]},"assertion":[{"value":"15 October 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 September 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 November 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}