Abstract
The complexity of computing pure Nash equilibria in congestion games was recently shown to be PLS-complete. In this paper, we therefore study the complexity of computing approximate equilibria in congestion games. An α-approximate equilibrium, for α > 1, is a state of the game in which none of the players can make an α-greedy step, i.e.. an unilateral strategy change that decreases the player's cost by a factor of at least α. Our main result shows that finding an α-approximate equilibrium of a given congestion game is PLS-complete, for any polynomial-time computable α > 1. Our analysis is based on a gap introducing PLS-reduction horn FLIP, i.e., the problem of finding a local optimum of a function encoded by an arbitrary circuit. As this reduction is "tight" it additionally implies that computing an α-approximate equilibrium reachable from a given initial state by a sequence of α-greedy steps is PSPACE-complete. Our results are in sharp contrast to a recent result showing that every local search problem in PLS admits a fully polynomial time approximation scheme. In addition, we show that there exist congestion games with states such that any sequence of α-greedy steps leading from one of these states to an α-approximate Nash equilibrium has exponential length, even if the delay functions satisfy a bounded-jump condition. This result shows that a recent result about polynomial time convergence for α-greedy steps in congestion games satisfying the bounded-jump condition is restricted to symmetric games only.
Original language | English |
---|---|
Title of host publication | STOC'08 |
Subtitle of host publication | Proceedings of the fortieth annual ACM symposium on Theory of computing |
Pages | 355-364 |
Number of pages | 10 |
DOIs | |
Publication status | Published - 8 Dec 2008 |
Externally published | Yes |
Event | 40th Annual ACM Symposium on Theory of Computing, STOC 2008 - Victoria, Canada Duration: 17 May 2008 → 20 May 2008 Conference number: 40 http://acm-stoc.org/stoc2008/ |
Conference
Conference | 40th Annual ACM Symposium on Theory of Computing, STOC 2008 |
---|---|
Abbreviated title | STOC 2008 |
Country/Territory | Canada |
City | Victoria |
Period | 17/05/08 → 20/05/08 |
Internet address |
Keywords
- Approximation
- Congestion games
- Local search