How hard is it to approximate the best nash equilibrium?

Elad Hazan, Robert Krauthgamer

Research output: Contribution to journalArticle

52 Scopus citations

Abstract

The quest for a polynomial-time approximation scheme (PTAS) for Nash equilibrium in a two-player game, which emerged as a major open question in algorithmic game theory, seeks to circumvent the PPAD-completeness of finding an (exact) Nash equilibrium by finding an approximate equilibrium. The closely related problem of finding an equilibrium maximizing a certain objective, such as social welfare, was shown to be NP-hard [Gilboa and Zemel, Games Econom. Behav., 1 (1989), pp. 80-93]. However, this NP-hardness is unlikely to extend to approximate equilibria, since the latter admits a quasi-polynomial time algorithm [Lipton, Markakis, and Mehta, in Proceedings of the 4th ACM Conference on Electronic Commerce, ACM, New York, 2003, pp. 36-41]. We show that this optimization problem, namely, finding in a two-player game an approximate equilibrium achieving a large social welfare, is unlikely to have a polynomial-time algorithm. One interpretation of our results is that a PTAS for Nash equilibrium (if it exists) should not extend to a PTAS for finding the best Nash equilibrium. Technically, our result is a reduction from the notoriously difficult problem in modern combinatorics, of finding a planted (but hidden) clique in a random graph G(n, 1/2). Our reduction starts from an instance with planted clique size O(log n). For comparison, the currently known algorithms are effective only for a much larger clique size ω(√n).

Original languageEnglish (US)
Pages (from-to)79-91
Number of pages13
JournalSIAM Journal on Computing
Volume40
Issue number1
DOIs
StatePublished - Mar 28 2011
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Mathematics(all)

Keywords

  • Game theory
  • Hidden clique
  • Logarithmically-restricted NP
  • Nash equilibrium

Fingerprint Dive into the research topics of 'How hard is it to approximate the best nash equilibrium?'. Together they form a unique fingerprint.

  • Cite this