  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,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 $\eta$ (for any
$\eta>0$, even when the best 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 types is uniform,
we give a quasi-polynomial time algorithm matched by a hardness result based on
the Hidden Clique problem.
