2026-07-21T20:21:15Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10709 2024-03-06T10:46:31Z ddc:004 open_access

On Approximate Pure Nash Equilibria in Weighted Congestion Games with Polynomial Latencies Caragiannis, Ioannis Fanelli, Angelo Congestion games approximate pure Nash equilibrium potential functions approximate price of stability We consider the problem of the existence of natural improvement dynamics leading to approximate pure Nash equilibria, with a reasonable small approximation, and the problem of bounding the efficiency of such equilibria in the fundamental framework of weighted congestion game with polynomial latencies of degree at most d >= 1. In this work, by exploiting a simple technique, we firstly show that the game always admits a d-approximate potential function. This implies that every sequence of d-approximate improvement moves by the players always leads the game to a d-approximate pure Nash equilibrium. As a corollary, we also obtain that, under mild assumptions on the structure of the players' strategies, the game always admits a constant approximate potential function. Secondly, by using a simple potential function argument, we are able to show that in the game there always exists a (d+delta)-approximate pure Nash equilibrium, with delta in [0,1], whose cost is 2/(1+delta) times the cost of an optimal state. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ioannis Caragiannis and Angelo Fanelli 2019 Is Part Of LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2019.133 urn:nbn:de:0030-drops-107095 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.133 eng https://creativecommons.org/licenses/by/3.0/legalcode