Revised: January 6, 2013
Published: January 28, 2013
Abstract: [Plain Text Version]
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.
Licensed under a Creative Commons Attribution License (CC-BY)