  We study the problem of finding approximate Nash equilibria that satisfy
certain conditions, such as providing good social welfare. In particular, we
study the problem $\epsilon$-NE $\delta$-SW: find an $\epsilon$-approximate
Nash equilibrium ($\epsilon$-NE) that is within $\delta$ of the best social
welfare achievable by an $\epsilon$-NE. Our main result is that, if the
exponential-time hypothesis (ETH) is true, then solving $\left(\frac{1}{8} -
\mathrm{O}(\delta)\right)$-NE $\mathrm{O}(\delta)$-SW for an $n\times n$
bimatrix game requires $n^{\mathrm{\widetilde \Omega}(\log n)}$ time. Building
on this result, we show similar conditional running time lower bounds on a
number of decision problems for approximate Nash equilibria that do not involve
social welfare, including maximizing or minimizing a certain player's payoff,
or finding approximate equilibria contained in a given pair of supports. We
show quasi-polynomial lower bounds for these problems assuming that ETH holds,
where these lower bounds apply to $\epsilon$-Nash equilibria for all $\epsilon
< \frac{1}{8}$. The hardness of these other decision problems has so far only
been studied in the context of exact equilibria.
