{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,13]],"date-time":"2026-01-13T20:56:26Z","timestamp":1768337786224,"version":"3.49.0"},"reference-count":25,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2015,12,31]],"date-time":"2015-12-31T00:00:00Z","timestamp":1451520000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100000266","name":"EPSRC","doi-asserted-by":"crossref","award":["EP\/J019399\/1, EP\/K01000X\/1, EP\/L011018\/1 and EP\/M008118\/1"],"award-info":[{"award-number":["EP\/J019399\/1, EP\/K01000X\/1, EP\/L011018\/1 and EP\/M008118\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Econ. Comput."],"published-print":{"date-parts":[[2016,2,3]]},"abstract":"<jats:p>The price of anarchy (PoA) in congestion games has attracted a lot of research over the past decade. This has resulted in a thorough understanding of this concept. In contrast, the price of stability (PoS), which is an equally interesting concept, is much less understood.<\/jats:p>\n          <jats:p>\n            In this article, we consider congestion games with polynomial cost functions with nonnegative coefficients and maximum degree\n            <jats:italic>d<\/jats:italic>\n            . We give matching bounds for the PoS in such games\u2014that is, our technique provides the exact value for any degree\n            <jats:italic>d<\/jats:italic>\n            .\n          <\/jats:p>\n          <jats:p>For linear congestion games, tight bounds were previously known. Those bounds hold even for the more restricted case of dominant equilibria, which may not exist. We give a separation result showing that this is not possible for congestion games with quadratic cost functions\u2014in other words, the PoA for the subclass of games that admit a dominant strategy equilibrium is strictly smaller than the PoS for the general class.<\/jats:p>","DOI":"10.1145\/2841229","type":"journal-article","created":{"date-parts":[[2016,1,14]],"date-time":"2016-01-14T02:18:38Z","timestamp":1452737918000},"page":"1-17","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":9,"title":["Price of Stability in Polynomial Congestion Games"],"prefix":"10.1145","volume":"4","author":[{"given":"George","family":"Christodoulou","sequence":"first","affiliation":[{"name":"University of Liverpool, Liverpool, U.K"}]},{"given":"Martin","family":"Gairing","sequence":"additional","affiliation":[{"name":"University of Liverpool, Liverpool, U.K"}]}],"member":"320","published-online":{"date-parts":[[2015,12,31]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/090748986"},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201908)","author":"Albers Susanne","year":"2008","unstructured":"Susanne Albers . 2008 . On the value of coordination in network design . In Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201908) . 294--303. Susanne Albers. 2008. On the value of coordination in network design. In Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201908). 294--303."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2004.68"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060599"},{"key":"e_1_2_1_5_1","volume-title":"Algorithms\u2014ESA","author":"Bhawalkar Kshipra","year":"2010","unstructured":"Kshipra Bhawalkar , Martin Gairing , and Tim Roughgarden . 2010. Weighted congestion games: Price of anarchy, universal worst-case examples, and tightness . In Algorithms\u2014ESA 2010 . Lecture Notes in Computer Science, Vol. 6347 . Springer , 17--28. Kshipra Bhawalkar, Martin Gairing, and Tim Roughgarden. 2010. Weighted congestion games: Price of anarchy, universal worst-case examples, and tightness. In Algorithms\u2014ESA 2010. Lecture Notes in Computer Science, Vol. 6347. Springer, 17--28."},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of the 10th International Workshop on Approximation and Online Algorithms (WAOA\u201912)","author":"Bil\u00f2 Vittorio","year":"2012","unstructured":"Vittorio Bil\u00f2 . 2012 . A unifying tool for bounding the quality of non-cooperative solutions in weighted congestion games . In Proceedings of the 10th International Workshop on Approximation and Online Algorithms (WAOA\u201912) . 215--228. Vittorio Bil\u00f2. 2012. A unifying tool for bounding the quality of non-cooperative solutions in weighted congestion games. In Proceedings of the 10th International Workshop on Approximation and Online Algorithms (WAOA\u201912). 215--228."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0219265911002824"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/1929237.1929246"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.74"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-010-9427-8"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1148109.1148114"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-12450-1_8"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-39212-2_44"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/11561071_8"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060600"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-010-9449-2"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2014.10.037"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/11786986_53"},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of the 16th Annual Symposium on Theoretical Aspects of Computer Science (STACS\u201999)","author":"Koutsoupias Elias","unstructured":"Elias Koutsoupias and Christos H. Papadimitriou . 1999. Worst-case equilibria . In Proceedings of the 16th Annual Symposium on Theoretical Aspects of Computer Science (STACS\u201999) . 404--413. Elias Koutsoupias and Christos H. Papadimitriou. 1999. Worst-case equilibria. In Proceedings of the 16th Annual Symposium on Theoretical Aspects of Computer Science (STACS\u201999). 404--413."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2492002.2482562"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2009.04.015"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1006\/game.1996.0044"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01737559"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2209249.2209274"},{"key":"e_1_2_1_25_1","volume-title":"Stier-Moses","author":"Schulz Andreas S.","year":"2002","unstructured":"Andreas S. Schulz and Nic\u00f3las E . Stier-Moses . 2002 . On the performance of user equilibria in traffic networks. In Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201903). 86--87. Andreas S. Schulz and Nic\u00f3las E. Stier-Moses. 2002. On the performance of user equilibria in traffic networks. In Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201903). 86--87."}],"container-title":["ACM Transactions on Economics and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2841229","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2841229","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:53:47Z","timestamp":1750222427000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2841229"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,12,31]]},"references-count":25,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2016,2,3]]}},"alternative-id":["10.1145\/2841229"],"URL":"https:\/\/doi.org\/10.1145\/2841229","relation":{},"ISSN":["2167-8375","2167-8383"],"issn-type":[{"value":"2167-8375","type":"print"},{"value":"2167-8383","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,12,31]]},"assertion":[{"value":"2014-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-12-31","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}