# CFGS11

### Summary

**Ioannis Caragiannis, Angelo Fanelli, Nick Gravin and Alexander Skopalik** (2011) *Efficient computation of approximate pure Nash equilibria in congestion games.* In 52th annual IEEE Symposium on Foundations of Computer Science (FOCS11). Palm Springs, CA, USA, oct. IEEE, pages 532-541. ((URL)) (PDF)

### Abstract

Congestion games constitute an important class of games in which computing an exact or even approximate pure Nash equilibrium is in general PLS-complete. We present a surprisingly simple polynomial-time algorithm that computes {$O(1)$}-approximate Nash equilibria in these games. In particular, for congestion games with linear latency functions, our algorithm computes {$(2+epsilon)$}-approximate pure Nash equilibria in time polynomial in the number of players, the number of resources and {$1/epsilon$}. It also applies to games with polynomial latency functions with constant maximum degree {$d$}; there, the approximation guarantee is {$d^{O(d)}$}. The algorithm essentially identifies a polynomially long sequence of best-response moves that lead to an approximate equilibrium, the existence of such short sequences is interesting in itself. These are the first positive algorithmic results for approximate equilibria in non-symmetric congestion games. We strengthen them further by proving that, for congestion games that deviate from our mild assumptions, computing $rho$-approximate equilibria is PLS-complete for any polynomial-time computable {$rho$}.

### Bibtex entry

`@INPROCEEDINGS { CFGS11,`

TITLE = { {Efficient computation of approximate pure Nash equilibria in congestion games} },

AUTHOR = { Ioannis Caragiannis and Angelo Fanelli and Nick Gravin and Alexander Skopalik },

BOOKTITLE = { 52th annual IEEE Symposium on Foundations of Computer Science (FOCS11) },

PAGES = { 532-541 },

ADDRESS = { Palm Springs, CA, USA },

URL = { http://dx.doi.org/10.1109/FOCS.2011.50 },

PDF = { http://arxiv.org/pdf/1104.2690.pdf },

YEAR = { 2011 },

MONTH = { oct },

PUBLISHER = { IEEE },

ABSTRACT = { Congestion games constitute an important class of games in which computing an exact or even approximate pure Nash equilibrium is in general PLS-complete. We present a surprisingly simple polynomial-time algorithm that computes {$O(1)$}-approximate Nash equilibria in these games. In particular, for congestion games with linear latency functions, our algorithm computes {$(2+epsilon)$}-approximate pure Nash equilibria in time polynomial in the number of players, the number of resources and {$1/epsilon$}. It also applies to games with polynomial latency functions with constant maximum degree {$d$}; there, the approximation guarantee is {$d^{O(d)}$}. The algorithm essentially identifies a polynomially long sequence of best-response moves that lead to an approximate equilibrium, the existence of such short sequences is interesting in itself. These are the first positive algorithmic results for approximate equilibria in non-symmetric congestion games. We strengthen them further by proving that, for congestion games that deviate from our mild assumptions, computing $rho$-approximate equilibria is PLS-complete for any polynomial-time computable {$rho$}. },

}