{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,30]],"date-time":"2026-05-30T00:02:29Z","timestamp":1780099349990,"version":"3.54.0"},"reference-count":110,"publisher":"Association for Computing Machinery (ACM)","issue":"5","license":[{"start":{"date-parts":[[2015,11,2]],"date-time":"2015-11-02T00:00:00Z","timestamp":1446422400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"AFOSR MURI"},{"name":"Alfred P. Sloan Fellowship"},{"name":"ONR PECASE Award"},{"name":"NSF","award":["CCF-0448664 and CCF-1016885"],"award-info":[{"award-number":["CCF-0448664 and CCF-1016885"]}]},{"name":"ONR Young Investigator Award"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2015,11,2]]},"abstract":"<jats:p>The price of anarchy, defined as the ratio of the worst-case objective function value of a Nash equilibrium of a game and that of an optimal outcome, quantifies the inefficiency of selfish behavior. Remarkably good bounds on this measure are known for a wide range of application domains. However, such bounds are meaningful only if a game's participants successfully reach a Nash equilibrium. This drawback motivates inefficiency bounds that apply more generally to weaker notions of equilibria, such as mixed Nash equilibria and correlated equilibria, and to sequences of outcomes generated by natural experimentation strategies, such as successive best responses and simultaneous regret-minimization.<\/jats:p>\n          <jats:p>\n            We establish a general and fundamental connection between the price of anarchy and its seemingly more general relatives. First, we identify a \u201ccanonical sufficient condition\u201d for an upper bound on the price of anarchy of pure Nash equilibria, which we call a\n            <jats:italic>smoothness argument<\/jats:italic>\n            . Second, we prove an \u201cextension theorem\u201d: every bound on the price of anarchy that is derived via a smoothness argument\n            <jats:italic>extends automatically<\/jats:italic>\n            , with no quantitative degradation in the bound, to mixed Nash equilibria, correlated equilibria, and the average objective function value of every outcome sequence generated by no-regret learners. Smoothness arguments also have automatic implications for the inefficiency of approximate equilibria, for bicriteria bounds, and, under additional assumptions, for polynomial-length best-response sequences. Third, we prove that in congestion games, smoothness arguments are \u201ccomplete\u201d in a proof-theoretic sense: despite their automatic generality, they are guaranteed to produce optimal worst-case upper bounds on the price of anarchy.\n          <\/jats:p>","DOI":"10.1145\/2806883","type":"journal-article","created":{"date-parts":[[2015,11,2]],"date-time":"2015-11-02T17:09:35Z","timestamp":1446484175000},"page":"1-42","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":132,"title":["Intrinsic Robustness of the Price of Anarchy"],"prefix":"10.1145","volume":"62","author":[{"given":"Tim","family":"Roughgarden","sequence":"first","affiliation":[{"name":"Stanford University, Stanford, CA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2015,11,2]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1455248.1455249"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/090748986"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2560767"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/090771478"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2008.03.005"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/070680096"},{"key":"e_1_2_1_7_1","unstructured":"E. Anshelevich J. Postl and T. Wexler. 2013. Assignment games with conflicts: Price of total anarchy and convergence results via semi-smoothness. arXiv:1304.5149.  E. Anshelevich J. Postl and T. Wexler. 2013. Assignment games with conflicts: Price of total anarchy and convergence results via semi-smoothness. arXiv:1304.5149."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/1622698.1622714"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-4068(74)90037-8"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1386790.1386832"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060599"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2009.04.017"},{"key":"e_1_2_1_13_1","volume-title":"Proceedings of the 7th International Symposium on Algorithmic Game Theory (SAGT). 218--230","author":"Bachrach Y."},{"key":"e_1_2_1_14_1","unstructured":"M. J. Beckmann C. B. McGuire and C. B. Winsten. 1956. Studies in the Economics of Transportation. Yale University Press.  M. J. Beckmann C. B. McGuire and C. B. Winsten. 1956. Studies in the Economics of Transportation. Yale University Press."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2629666"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488615"},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 700--709","author":"Bhawalkar K."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-010-9309-0"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.43"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2010.v006a008"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374430"},{"key":"e_1_2_1_22_1","doi-asserted-by":"crossref","unstructured":"A. Blum and Y. Mansour. 2007. Learning regret minimization and equilibria. In Algorithmic Game Theory Chapter 4 Cambridge University Press 79--101.  A. Blum and Y. Mansour. 2007. Learning regret minimization and equilibria. In Algorithmic Game Theory Chapter 4 Cambridge University Press 79--101.","DOI":"10.1017\/CBO9780511800481.006"},{"key":"e_1_2_1_23_1","first-page":"31","article-title":"On the price of mediation","volume":"16","author":"Bradonji\u0107 M.","year":"2014","journal-title":"Discrete Math. Theor. Comput. Sci."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-010-9427-8"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993574.1993588"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jet.2014.04.010"},{"key":"e_1_2_1_27_1","doi-asserted-by":"crossref","unstructured":"N. Cesa-Bianchi and G. Lugosi. 2006. Prediction Learning and Games. Cambridge University Press.   N. Cesa-Bianchi and G. Lugosi. 2006. Prediction Learning and Games. Cambridge University Press.","DOI":"10.1017\/CBO9780511546921"},{"key":"e_1_2_1_28_1","unstructured":"D. Chakrabarty. 2004. Improved bicriteria results for the selfish routing problem. Unpublished manuscript.  D. Chakrabarty. 2004. Improved bicriteria results for the selfish routing problem. Unpublished manuscript."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/2597893"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1516512.1516516"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02927-1_24"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2009.05.004"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-39212-2_44"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/11561071_8"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060600"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2009.01.005"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-010-9449-2"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-70575-8_67"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-35311-6_26"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2013.03.011"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1040.0098"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2008.01.001"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/1186810.1186814"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1137\/070699652"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1007\/11944874_29"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2008.07.002"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1137\/080720826"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/872035.872088"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007445"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-32589-2_33"},{"key":"e_1_2_1_51_1","doi-asserted-by":"crossref","unstructured":"B. Farzad N. Olver and A. Vetta. 2008. A priority-based model of routing. Chicago J. Theor. Comput. Sci. (2008) Article 1.  B. Farzad N. Olver and A. Vetta. 2008. A priority-based model of routing. Chicago J. Theor. Comput. Sci. (2008) Article 1.","DOI":"10.4086\/cjtcs.2008.001"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1006\/game.1997.0595"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-009-9205-7"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-008-9152-8"},{"key":"e_1_2_1_55_1","unstructured":"M. Gairing. 2006. Selfish Routing in Networks. Ph.D. Dissertation. Universit\u00e4t Paderborn.  M. Gairing. 2006. Selfish Routing in Networks. Ph.D. Dissertation. Universit\u00e4t Paderborn."},{"key":"e_1_2_1_56_1","volume-title":"Proceedings of the 6th International Workshop on Approximation and Online Algorithms (WAOA). 119--132","author":"Gairing M.","year":"2008"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-007-9015-8"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/1978782.1978786"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0129626409000122"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1016\/0899-8256(89)90006-7"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1109\/JSAC.2006.872884"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2005.68"},{"key":"e_1_2_1_63_1","first-page":"97","article-title":"Approximation to Bayes risk in repeated play","volume":"3","author":"Hannan J.","year":"1957","journal-title":"Contrib. Theor. Games"},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-010-9269-4"},{"key":"e_1_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-011-9315-x"},{"key":"e_1_2_1_66_1","volume-title":"Proceedings of the 4th Workshop on Combinatorial and Algorithmic Aspects of Networking (CAAN). 27--45","author":"Harks T."},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1111\/1468-0262.00153"},{"key":"e_1_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993574.1993619"},{"key":"e_1_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1937-5956.2007.tb00271.x"},{"key":"e_1_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-29116-6_22"},{"key":"e_1_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.1006\/game.1997.0592"},{"key":"e_1_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-006-0015-2"},{"key":"e_1_2_1_73_1","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536487"},{"key":"e_1_2_1_74_1","doi-asserted-by":"publisher","DOI":"10.1145\/2781678"},{"key":"e_1_2_1_75_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-003-1131-5"},{"key":"e_1_2_1_76_1","volume-title":"Proceedings of the 16th Annual Symposium on Theoretical Aspects of Computer Science (STACS). 404--413","author":"Koutsoupias E."},{"key":"e_1_2_1_77_1","volume-title":"Proceedings of the 1st Conference on Innovations in Computer Science. 166--177","author":"Lucier B.","year":"2010"},{"key":"e_1_2_1_78_1","volume-title":"Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 537--553","author":"Lucier B."},{"key":"e_1_2_1_79_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993574.1993587"},{"key":"e_1_2_1_80_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.06.045"},{"key":"e_1_2_1_81_1","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.2014.2301613"},{"key":"e_1_2_1_82_1","volume-title":"Proceedings of the 7th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX). 183--194","author":"Mirrokni V. S."},{"key":"e_1_2_1_83_1","doi-asserted-by":"publisher","DOI":"10.1006\/game.1996.0044"},{"key":"e_1_2_1_84_1","doi-asserted-by":"publisher","DOI":"10.1145\/1146381.1146391"},{"key":"e_1_2_1_85_1","doi-asserted-by":"crossref","unstructured":"R. Motwani and P. Raghavan. 1996. Randomized Algorithms. Cambridge University Press.   R. Motwani and P. Raghavan. 1996. Randomized Algorithms. Cambridge University Press.","DOI":"10.1017\/CBO9780511814075"},{"key":"e_1_2_1_86_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01769190"},{"key":"e_1_2_1_87_1","volume-title":"Proceedings of the 6th International Workshop on Internet and Network Economics (WINE). 319--326","author":"Nadav U."},{"key":"e_1_2_1_88_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.36.1.48"},{"key":"e_1_2_1_89_1","doi-asserted-by":"crossref","unstructured":"N. Nisan T. Roughgarden \u00c9. Tardos and V. Vazirani (Eds.). 2007. Algorithmic Game Theory. Cambridge University Press.   N. Nisan T. Roughgarden \u00c9. Tardos and V. Vazirani (Eds.). 2007. Algorithmic Game Theory. Cambridge University Press.","DOI":"10.1017\/CBO9780511800481"},{"key":"e_1_2_1_90_1","unstructured":"N. Olver. 2006. The Price of Anarchy and a Priority-Based Model of Routing. M.S. Thesis. McGill University.  N. Olver. 2006. The Price of Anarchy and a Priority-Based Model of Routing. M.S. Thesis. McGill University."},{"key":"e_1_2_1_91_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.75"},{"key":"e_1_2_1_92_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1070.0258"},{"key":"e_1_2_1_93_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01737559"},{"key":"e_1_2_1_94_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-92185-1_20"},{"key":"e_1_2_1_95_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(03)00044-8"},{"key":"e_1_2_1_96_1","volume-title":"Algorithmic Game Theory","author":"Roughgarden T."},{"key":"e_1_2_1_97_1","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536485"},{"key":"e_1_2_1_98_1","doi-asserted-by":"publisher","DOI":"10.1145\/2737816"},{"key":"e_1_2_1_99_1","doi-asserted-by":"crossref","unstructured":"T. Roughgarden and F. Schoppmann. 2015. Local smoothness and the price of anarchy in atomic splittable congestion games. J. Econ. Theor. 156 C (2015) 317--342.  T. Roughgarden and F. Schoppmann. 2015. Local smoothness and the price of anarchy in atomic splittable congestion games. J. Econ. Theor. 156 C (2015) 317--342.","DOI":"10.1016\/j.jet.2014.04.005"},{"key":"e_1_2_1_100_1","doi-asserted-by":"publisher","DOI":"10.1145\/506147.506153"},{"key":"e_1_2_1_101_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2003.06.004"},{"key":"e_1_2_1_102_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374428"},{"key":"e_1_2_1_103_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-006-1211-4"},{"key":"e_1_2_1_104_1","unstructured":"V. Syrgkanis. 2012. Bayesian games and the smoothness framework. arXiv.cs.GT:1203.5155v1.  V. Syrgkanis. 2012. Bayesian games and the smoothness framework. arXiv.cs.GT:1203.5155v1."},{"key":"e_1_2_1_105_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488635"},{"key":"e_1_2_1_106_1","doi-asserted-by":"crossref","unstructured":"\u00c9. Tardos and T. Wexler. 2007. Network formation games and the potential function method. In Algorithmic Game Theory Chapter 19. Cambridge University Press 487--516.  \u00c9. Tardos and T. Wexler. 2007. Network formation games and the potential function method. In Algorithmic Game Theory Chapter 19. Cambridge University Press 487--516.","DOI":"10.1017\/CBO9780511800481.021"},{"key":"e_1_2_1_107_1","doi-asserted-by":"publisher","DOI":"10.5555\/645413.652124"},{"key":"e_1_2_1_108_1","doi-asserted-by":"crossref","volume-title":"Algorithmic Game Theory","author":"V\u00f6cking B.","DOI":"10.1007\/978-3-642-41392-6"},{"key":"e_1_2_1_109_1","first-page":"325","article-title":"Some theoretical aspects of road traffic research. In Proceedings of the Institute of Civil Engineers","volume":"1","author":"Wardrop J. G.","year":"1952","journal-title":"Pt. II"},{"key":"e_1_2_1_110_1","unstructured":"D. Weitz. 2001. The price of anarchy. Manuscript.  D. Weitz. 2001. The price of anarchy. Manuscript."}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2806883","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2806883","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T05:07:22Z","timestamp":1750223242000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2806883"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,11,2]]},"references-count":110,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2015,11,2]]}},"alternative-id":["10.1145\/2806883"],"URL":"https:\/\/doi.org\/10.1145\/2806883","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,11,2]]},"assertion":[{"value":"2013-07-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-07-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-11-02","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}