Approximating the best Nash Equilibrium in no (1ogn)-time breaks the exponential time hypothesis

Mark Braverman, Young Kun Ko, Omri Weinstein

Research output: Chapter in Book/Report/Conference proceedingConference contribution

25 Scopus citations

Abstract

The celebrated PPAD hardness result for finding an exact Nash equilibrium in a two-player game initiated a quest for finding approximate Nash equilibria efficiently, and is one of the major open questions in algorithmic game theory. We study the computational complexity of finding an ε-approximate Nash equilibrium with good social welfare. Hazan and Krauthgamer and subsequent improvements showed that finding an e-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 (1ogn) in the random graph Q (n, 1/2). We show that any polynomial time algorithm that finds an ε-approximate Nash equilibrium with good social welfare refutes (the worst-case) Exponential Time Hypothesis by Impagliazzo and Paturi, confirming the recent conjecture by Aaronson, Impagliazzo and Moshkovitz. Specifically, it would imply a 2O (n1/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.

Original languageEnglish (US)
Title of host publicationProceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015
PublisherAssociation for Computing Machinery
Pages970-982
Number of pages13
EditionJanuary
ISBN (Electronic)9781611973747
StatePublished - Jan 1 2015
Event26th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015 - San Diego, United States
Duration: Jan 4 2015Jan 6 2015

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
NumberJanuary
Volume2015-January

Other

Other26th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015
CountryUnited States
CitySan Diego
Period1/4/151/6/15

All Science Journal Classification (ASJC) codes

  • Software
  • Mathematics(all)

Fingerprint Dive into the research topics of 'Approximating the best Nash Equilibrium in n<sup>o (1ogn)</sup>-time breaks the exponential time hypothesis'. Together they form a unique fingerprint.

  • Cite this

    Braverman, M., Ko, Y. K., & Weinstein, O. (2015). Approximating the best Nash Equilibrium in no (1ogn)-time breaks the exponential time hypothesis. In Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015 (January ed., pp. 970-982). (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms; Vol. 2015-January, No. January). Association for Computing Machinery.