Settling the complexity of computing approximate two-player Nash equilibria

Computer Science/Discrete Mathematics Seminar II
Topic:Settling the complexity of computing approximate two-player Nash equilibria
Speaker:Aviad Rubinstein
Affiliation:University of California, Berkeley
Date:Tuesday, November 1
Time/Room:10:30am - 12:30pm/West Building Lecture Hall
Video Link:https://video.ias.edu/csdm/2016/1101-AviadRubinstein

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(1)}n}$. This matches (up to the $o(1)$ term) the algorithm of Lipton, Markakis, and Mehta [LMM03]. Our proof relies on a variety of techniques from the study of probabilistically checkable proofs (PCP); this is the first time that such ideas are used for a reduction between problems inside PPAD.