On the Complexity of Approximating a Nash Equilibrium

We show that computing a relatively (i.e., multiplicatively as opposed to additively) approximate Nash equilibrium in two-player games is PPAD-complete, even for constant values of the approximation. Our result is the first constant inapproximability result for Nash equilibrium, since the original results on the computational complexity of the problem [Daskalakis et al. 2006a; Chen and Deng 2006]. Moreover, it provides an apparent-assuming that PPAD is not contained in TIME(n(O(log n)))-dichotomy between the complexities of additive and relative approximations, as for constant values of additive approximation a quasi-polynomial-time algorithm is known [Lipton et al. 2003]. Such a dichotomy does not exist for values of the approximation that scale inverse-polynomially with the size of the game, where both relative and additive approximations are PPAD-complete [Chen et al. 2006]. As a byproduct, our proof shows that (unconditionally) the sparse-support lemma [Lipton et al. 2003] cannot be extended to relative notions of constant approximation.