## 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

### DOI

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 language English Journal of Computer and System Sciences 117 40-48 9 0022-0000 https://doi.org/10.1016/j.jcss.2020.10.007 Published - 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

Citationformats

ID: 202794201