Title: How hard is it to approximate the best Nash equilibrium?
Speaker: Robert Krauthgamer
Abstract: The quest for a PTAS for Nash equilibrium in a two-player game has emerged as a major open question in Algorithmic Game Theory, due to the PPAD-completeness of finding an exact Nash equilibrium. A related problem of special interest is its optimization version -- finding an equilibrium maximizing a certain objective, such as the social welfare, and this problem was shown to be NP-hard by Gilboa and Zemel [Games and Economic Behavior, 1989]. However, this NP-hardness is unlikely to extend to approximate equilibria, since the latter admits a quasi-polynomial time algorithm, as (essentially) proved by Lipton, Markakis and Mehta [EC, 2003].
I will show that this latter optimization problem, namely, finding in a two-player game an approximate equilibrium achieving large social welfare is unlikely to have a polynomial time algorithm. One interpretation of this result is that the quest for a PTAS for Nash equilibrium should NOT extend to a PTAS for finding the best Nash equilibrium, which stands in contrast to certain algorithmic techniques used so far (e.g. sampling and enumeration). Technically, the result follows via a connection to a notoriously difficult problem in modern Combinatorics, of finding a planted clique in an otherwise random graph $G(n,1/2)$.
[Joint work with Elad Hazan.]