Theory of Computing
-------------------
Title     : Inapproximability of NP-Complete Variants of Nash Equilibrium
Authors   : Per Austrin, Mark Braverman, and Eden Chlamtac
Volume    : 9
Number    : 3
Pages     : 117-142
URL       : https://theoryofcomputing.org/articles/v009a003

Abstract
--------

In recent work of Hazan and Krauthgamer (SICOMP 2011), it was shown
that finding an $\epsilon$-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.