On approximate pure Nash equilibria in weighted congestion games with polynomial latencies

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaperJournal articleResearchpeer-review

We consider weighted congestion games with polynomial latency functions of maximum degree $d\geq 1$. For these games, we investigate the existence and efficiency of approximate pure Nash equilibria which are obtained through sequences of unilateral improvement moves by the players.

By exploiting a simple technique, we firstly show that these games admit an infinite set of $\d$-approximate potential functions. This implies that there always exists a $\d$-approximate pure Nash equilibrium which can be reached through any sequence of $\d$-approximate improvement moves by the players. As a corollary, we also obtain that, under mild assumptions on the structure of the players' strategies, these games also admit a constant approximate potential function. Secondly, using a simple potential function argument, we are able to show that a $(\d+\delta)$-approximate pure Nash equilibrium of cost at most $(\d+1)/(\d+\delta)$ times the cost of an optimal state always exists, for every $\delta\in [0,1]$.
Original languageEnglish
JournalJournal of Computer and System Sciences
Volume117
Pages (from-to)40-48
Number of pages9
ISSN0022-0000
DOIs
Publication statusPublished - May 2021

Bibliographical note

A preliminary version of the results in this paper appeared in Proceedings of the 46th International Colloquium on Automata, Languages and Programming (ICALP), pages 133:1-12, 2019.

    Research areas

  • Weighted congestion games, Approximate pure Nash equilibria, Price of stability, Potential functions

See relations at Aarhus University Citationformats

ID: 202794201