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.