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

84 Citations (Scopus)
67 Downloads (Pure)


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
Number of pages10
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


Conference40th Annual ACM Symposium on Theory of Computing, STOC 2008
Abbreviated titleSTOC 2008
Internet address


  • Approximation
  • Congestion games
  • Local search


Dive into the research topics of 'Inapproximability of pure Nash equilibria'. Together they form a unique fingerprint.

Cite this