Inapproximability of NP-complete variants of Nash equilibrium

Per Austrin, Mark Braverman, Eden Chlamtáč

Research output: Chapter in Book/Report/Conference proceedingConference contribution

5 Scopus citations

Abstract

In recent work of Hazan and Krauthgamer (SICOMP 2011), it was shown that finding an ε-approximate Nash equilibrium with near-optimal value in a two-player game is as hard as finding a hidden clique of size O(log n) in the random graph G(n, 1/2). This raises the question of whether a similar intractability holds for approximate Nash equilibrium without such constraints. We give evidence that the constraint of near-optimal value makes the problem distinctly harder: a simple algorithm finds an optimal 1/2-approximate equilibrium, while finding strictly better than 1/2-approximate equilibria is as hard as the Hidden Clique problem. This is in contrast to the unconstrained problem where more sophisticated algorithms, achieving better approximations, are known. Unlike general Nash equilibrium, which is in PPAD, optimal (maximum value) Nash equilibrium is NP-hard. We proceed to show that optimal Nash equilibrium is just one of several known NP-hard problems related to Nash equilibrium, all of which have approximate variants which are as hard as finding a planted clique. In particular, we show this for approximate variants of the following problems: finding a Nash equilibrium with value greater than η (for any η > 0, even when the best Nash equilibrium has value 1 - η), finding a second Nash equilibrium, and finding a Nash equilibrium with small support. Finally, we consider the complexity of approximate pure Bayes Nash equilibria in two-player games. Here we show that for general Bayesian games the problem is NP-hard. For the special case where the distribution over types is uniform, we give a quasi-polynomial time algorithm matched by a hardness result based on the Hidden Clique problem.

Original languageEnglish (US)
Title of host publicationApproximation, Randomization, and Combinatorial Optimization
Subtitle of host publicationAlgorithms and Techniques - 14th International Workshop, APPROX 2011 and 15th International Workshop, RANDOM 2011, Proceedings
Pages13-25
Number of pages13
DOIs
StatePublished - 2011
Externally publishedYes
Event14th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2011 and the 15th International Workshop on Randomization and Computation, RANDOM 2011 - Princeton, NJ, United States
Duration: Aug 17 2011Aug 19 2011

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume6845 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other14th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2011 and the 15th International Workshop on Randomization and Computation, RANDOM 2011
CountryUnited States
CityPrinceton, NJ
Period8/17/118/19/11

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Inapproximability of NP-complete variants of Nash equilibrium'. Together they form a unique fingerprint.

Cite this