ECCC-Report TR14-092https://eccc.weizmann.ac.il/report/2014/092Comments and Revisions published for TR14-092en-usTue, 22 Jul 2014 23:50:46 +0300
Paper TR14-092
| Approximating the best Nash Equilibrium in $n^{o(\log n)}$-time breaks the Exponential Time Hypothesis |
Omri Weinstein,
Mark Braverman,
Young Kun Ko
https://eccc.weizmann.ac.il/report/2014/092The celebrated PPAD hardness result for finding an exact Nash equilibrium in a two-player game
initiated a quest for finding \emph{approximate} Nash equilibria efficiently, and is one of the major open questions in algorithmic game theory.
We study the computational complexity of finding an $\eps$-approximate Nash equilibrium with good social welfare. Hazan and Krauthgamer and subsequent improvements showed that finding an $\eps$-approximate Nash equilibrium with good social welfare in a two player game and many variants of this problem is at least as hard as finding a planted clique of size $O(\log n)$ in the random graph $\mathcal{G}(n,1/2)$.
We show that any polynomial time algorithm that finds an $\eps$-approximate Nash equilibrium with good social welfare refutes (the worst-case) Exponential Time Hypothesis by Impagliazzo and Paturi. Specifically, it would imply a $2^{\tilde{O}(n^{1/2})}$ algorithm for SAT.
Our lower bound matches the quasi-polynomial time algorithm by Lipton, Markakis and Mehta for solving the problem.
Our key tool is a reduction from the PCP machinery to finding Nash equilibrium via free games, the framework introduced in the recent work by Aaronson, Impagliazzo and Moshkovitz. Techniques developed in the process may be useful for replacing planted clique hardness with ETH-hardness in other applications.
Tue, 22 Jul 2014 23:50:46 +0300https://eccc.weizmann.ac.il/report/2014/092