{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,15]],"date-time":"2026-01-15T13:12:41Z","timestamp":1768482761032,"version":"3.49.0"},"reference-count":30,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2015,3,27]],"date-time":"2015-03-27T00:00:00Z","timestamp":1427414400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100000780","name":"European Union","doi-asserted-by":"crossref","award":["317532 MULTIPLEX, FP7-ICT-258307 EULER"],"award-info":[{"award-number":["317532 MULTIPLEX, FP7-ICT-258307 EULER"]}],"id":[{"id":"10.13039\/501100000780","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Greek research funding program THALES"},{"name":"Collaborative Research Centre \u201cOn-The-Fly Computing\u201d"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Econ. Comput."],"published-print":{"date-parts":[[2015,3,27]]},"abstract":"<jats:p>\n            We consider structural and algorithmic questions related to the Nash dynamics of weighted congestion games. In weighted congestion games with linear latency functions, the existence of pure Nash equilibria is guaranteed by a potential function argument. Unfortunately, this proof of existence is inefficient and computing pure Nash equilibria in such games is a PLS-hard problem even when all players have unit weights. The situation gets worse when superlinear (e.g., quadratic) latency functions come into play; in this case, the Nash dynamics of the game may contain cycles and pure Nash equilibria may not even exist. Given these obstacles, we consider approximate pure Nash equilibria as alternative solution concepts. A\n            <jats:italic>\u03c1<\/jats:italic>\n            --approximate pure Nash equilibrium is a state of a (weighted congestion) game from which no player has any incentive to deviate in order to improve her cost by a multiplicative factor higher than\n            <jats:italic>\u03c1<\/jats:italic>\n            . Do such equilibria exist for small values of\n            <jats:italic>\u03c1<\/jats:italic>\n            ? And if so, can we compute them efficiently?\n          <\/jats:p>\n          <jats:p>\n            We provide positive answers to both questions for weighted congestion games with polynomial latency functions by exploiting an \u201capproximation\u201d of such games by a new class of potential games that we call\n            <jats:italic>\u03a8<\/jats:italic>\n            -games. This allows us to show that these games have d!-approximate pure Nash equilibria, where\n            <jats:italic>d<\/jats:italic>\n            is the maximum degree of the latency functions. Our main technical contribution is an efficient algorithm for computing O(1)-approximate pure Nash equilibria when\n            <jats:italic>d<\/jats:italic>\n            is a constant. For games with linear latency functions, the approximation guarantee is 3+\u221a5\/2 + O\n            <jats:italic>\u03b3<\/jats:italic>\n            for arbitrarily small\n            <jats:italic>\u03b3<\/jats:italic>\n            &gt; 0; for latency functions with maximum degree\n            <jats:italic>d<\/jats:italic>\n            \u2265 2, it is\n            <jats:italic>d<\/jats:italic>\n            2\n            <jats:italic>d<\/jats:italic>\n            +\n            <jats:italic>o<\/jats:italic>\n            (\n            <jats:italic>d<\/jats:italic>\n            ). The running time is polynomial in the number of bits in the representation of the game and 1\/\n            <jats:italic>\u03b3<\/jats:italic>\n            . As a byproduct of our techniques, we also show the following interesting structural statement for weighted congestion games with polynomial latency functions of maximum degree\n            <jats:italic>d<\/jats:italic>\n            \u2265 2: polynomially-long sequences of best-response moves from any initial state to a\n            <jats:italic>dO<\/jats:italic>\n            (\n            <jats:italic>d<\/jats:italic>\n            2)-approximate pure Nash equilibrium exist and can be efficiently identified in such games as long as\n            <jats:italic>d<\/jats:italic>\n            is a constant.\n          <\/jats:p>\n          <jats:p>\n            To the best of our knowledge, these are the first positive algorithmic results for approximate pure Nash equilibria in weighted congestion games. Our techniques significantly extend our recent work on unweighted congestion games through the use of\n            <jats:italic>\u03a8<\/jats:italic>\n            -games. The concept of approximating nonpotential games by potential ones is interesting in itself and might have further applications.\n          <\/jats:p>","DOI":"10.1145\/2614687","type":"journal-article","created":{"date-parts":[[2015,4,1]],"date-time":"2015-04-01T14:59:12Z","timestamp":1427900352000},"page":"1-32","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":26,"title":["Approximate Pure Nash Equilibria in Weighted Congestion Games"],"prefix":"10.1145","volume":"3","author":[{"given":"Ioannis","family":"Caragiannis","sequence":"first","affiliation":[{"name":"University of Patras &amp; CTI \u201cDiophantus\u201d"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Angelo","family":"Fanelli","sequence":"additional","affiliation":[{"name":"CNRS"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nick","family":"Gravin","sequence":"additional","affiliation":[{"name":"Microsoft Research New England"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alexander","family":"Skopalik","sequence":"additional","affiliation":[{"name":"University of Paderborn"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2015,3,27]]},"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.1016\/j.tcs.2008.12.035"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-04128-0_21"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1386790.1386832"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807342.1807353"},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of the 50th IEEE Conference on Decision and Control and European Control Conference. 2428--2433","author":"Candogan O.","unstructured":"Candogan , O. , Ozdaglar , A. E. , and Parrilo , P. A . 2011. Learning in near-potential games . In Proceedings of the 50th IEEE Conference on Decision and Control and European Control Conference. 2428--2433 . Candogan, O., Ozdaglar, A. E., and Parrilo, P. A. 2011. Learning in near-potential games. In Proceedings of the 50th IEEE Conference on Decision and Control and European Control Conference. 2428--2433."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2013.07.001"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-012-9650-6"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.50"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2010.02.005"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1378533.1378544"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/JSAC.2007.070813"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2009.05.004"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1016527.1016536"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2012.02.033"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2007.19"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1080.0322"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1273340.1273348"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.09.024"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007445"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-011-0145-5"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2005.68"},{"key":"e_1_2_1_23_1","doi-asserted-by":"crossref","unstructured":"Harks T.\n     and \n      Klimm M\n  . \n  2010\n  . On the existence of pure Nash equilibria in weighted congestion games. In Proceedings of the 37th International Colloquium on Automata Languages and Programming. Part 1 Lecture Notes in Computer Science vol. \n  6198 Springer 79--89.   Harks T. and Klimm M. 2010. On the existence of pure Nash equilibria in weighted congestion games. In Proceedings of the 37th International Colloquium on Automata Languages and Programming . Part 1 Lecture Notes in Computer Science vol. 6198 Springer 79--89.","DOI":"10.1007\/978-3-642-14165-2_8"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(88)90046-3"},{"key":"e_1_2_1_25_1","doi-asserted-by":"crossref","unstructured":"Kollias K.\n     and \n      Roughgarden T\n  . \n  2011\n  . Restoring pure equilibria to weighted congestion games. In Proceedings of the 38th International Colloquium on Automata Languages and Programming. Part II Lecture Notes in Computer Science vol. \n  6756 Springer 539--551.   Kollias K. and Roughgarden T. 2011. Restoring pure equilibria to weighted congestion games. In Proceedings of the 38th International Colloquium on Automata Languages and Programming . Part II Lecture Notes in Computer Science vol. 6756 Springer 539--551.","DOI":"10.1007\/978-3-642-22012-8_43"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-27821-4_17"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-10841-9_16"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1187436.1216584"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01737559"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374428"}],"container-title":["ACM Transactions on Economics and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2614687","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2614687","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T07:19:32Z","timestamp":1750231172000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2614687"}},"subtitle":["Existence, Efficient Computation, and Structure"],"short-title":[],"issued":{"date-parts":[[2015,3,27]]},"references-count":30,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2015,3,27]]}},"alternative-id":["10.1145\/2614687"],"URL":"https:\/\/doi.org\/10.1145\/2614687","relation":{},"ISSN":["2167-8375","2167-8383"],"issn-type":[{"value":"2167-8375","type":"print"},{"value":"2167-8383","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,3,27]]},"assertion":[{"value":"2013-03-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-03-27","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}