Inapproximability of pure Nash equilibria

Alexander Skopalik*, Berthold Vöcking

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

75 Citations (Scopus)
30 Downloads (Pure)

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 languageEnglish
Title of host publicationSTOC'08
Subtitle of host publicationProceedings of the fortieth annual ACM symposium on Theory of computing
Pages355-364
Number of pages10
DOIs
Publication statusPublished - 8 Dec 2008
Externally publishedYes
Event40th Annual ACM Symposium on Theory of Computing, STOC 2008 - Victoria, Canada
Duration: 17 May 200820 May 2008
Conference number: 40
http://acm-stoc.org/stoc2008/

Conference

Conference40th Annual ACM Symposium on Theory of Computing, STOC 2008
Abbreviated titleSTOC 2008
CountryCanada
CityVictoria
Period17/05/0820/05/08
Internet address

    Fingerprint

Keywords

  • Approximation
  • Congestion games
  • Local search

Cite this

Skopalik, A., & Vöcking, B. (2008). Inapproximability of pure Nash equilibria. In STOC'08: Proceedings of the fortieth annual ACM symposium on Theory of computing (pp. 355-364) https://doi.org/10.1145/1374376.1374428