Settling the Complexity of Computing Approximate Two-Player Nash Equilibria

Abstract

In our recent paper [Rubinstein 2016] we rule out a PTAS for the 2-Player Nash Equilibrium Problem. More precisely, we prove that there exists a constant ϵ > 0 such that, assuming the Exponential Time Hypothesis for PPAD, computing an ϵ-approximate Nash equilibrium in a two-player n × n game requires time n log 1−o(1) n . This matches (up to the o (1) term) the algorithm of Lipton, Markakis, and Mehta [Lipton et al. 2003].