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$}. },
}