  We study the randomized query complexity of approximate Nash equilibria (ANE)
in large games. We prove that, for some constant $\epsilon>0$, any randomized
oracle algorithm that computes an $\epsilon$-ANE in a binary-action, $n$-player
game must make $2^{\Omega(n/\log n)}$ payoff queries. For the stronger solution
concept of well-supported Nash equilibria (WSNE), Babichenko previously gave an
exponential $2^{\Omega(n)}$ lower bound for the randomized query complexity of
$\epsilon$-WSNE, for some constant $\epsilon>0$; the same lower bound was shown
to hold for $\epsilon$-ANE, but only when $\epsilon=O(1/n)$.
  Our result answers an open problem posed by Hart and Nisan and Babichenko and
is very close to the trivial upper bound of $2^n$. Our proof relies on a
generic reduction from the problem of finding an $\epsilon$-WSNE to the problem
of finding an $\epsilon/(4\alpha)$-ANE, in large games with $\alpha$ actions,
which might be of independent interest.
