$\frac{\rho }{1-\epsilon }$-approximate pure Nash equilibria algorithms for weighted congestion games and their runtimes

Abstract

This paper concerns computing approximate pure Nash equilibria in weighted congestion games, which has been shown to be PLS-complete. With the help of $\hat{\Psi }$-game and approximate potential functions, we propose two algorithms based on best response dynamics, and prove that they efficiently compute $\frac{\rho }{1-\epsilon }$-approximate pure Nash equilibria for $\rho =d!$ and $\rho =\frac{2\cdot W\cdot (d+1)}{2\cdot W+d+1}\le d+1$, respectively, when the weighted congestion game has polynomial latency functions of degree at most $d\ge 1$ and players' weights are bounded from above by a constant $W\ge 1$. This improves the recent work of Feldotto et al.[2017] and Giannakopoulos et al. [2022] that showed efficient algorithms for computing $d^{d+o(d)}$-approximate pure Nash equilibria.

31 pages