We prove that there exists a constant $\epsilon > 0$ such that,
assuming the Exponential Time Hypothesis for PPAD, computing an
$\epsilon$-approximate Nash equilibrium in a two-player ($n \times
n$) game requires quasi-polynomial time, $n^{\log^{1-o...
Read More