Volume 9 (2013) Article 3 pp. 117-142
Inapproximability of NP-Complete Variants of Nash Equilibrium
by
Received: October 13, 2011
Revised: January 6, 2013
Published: January 28, 2013
[PDF (323K)]    [PS (1328K)]    [PS.GZ (357K)]
[Source ZIP]
Keywords: Nash equilibrium, hidden clique
ACM Classification: F.2
AMS Classification: 68Q17, 68W25, 91A05

Abstract: [Plain Text Version]

$\newcommand{\eps}{\varepsilon}$

In recent work of Hazan and Krauthgamer (SICOMP 2011), it was shown that finding an $\eps$-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,\frac12)$. This raises the question of whether a similar intractability holds for approximate Nash equilibrium without side constraints such as high value. We give evidence that asking for near-optimal value makes the problem distinctly harder: a simple algorithm finds a $\frac{1}{2}$-approximate equilibrium of optimal value, but getting below $\frac{1}{2}$ is as hard as the Hidden Clique problem. This is in contrast to the basic problem (finding a Nash equilibrium with no optimization criteria) where more sophisticated algorithms, achieving better approximations, are known.

Unlike basic 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 $\eta$ (for any fixed $\eta>0$, even when the optimal Nash equilibrium has value $1-\eta$), 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 players' types is uniform, we give a quasi-polynomial time algorithm matched by a hardness result based on the Hidden Clique problem.

A preliminary version of this work appeared in the Proceedings of APPROX 2011.