SPEAKER: Per Austrin
Department of Computer Science
University of Toronto
TITLE: Inapproximability of NP-Complete variants of Nash equilibrium
In recent work of Hazan and Krauthgamer it was shown that finding an epsilon-approximate Nash equilibrium with near-optimal value is as hard as finding a planted clique of size O(log n) in the random graph G(n,1/2). This raises the question of whether a similar intractability holds for finding an arbitrary approximate equilibrium. We give evidence that adding constraints such as near-optimal value makes the problem distinctly harder. This evidence comes in two forms:
1. We show that maximum value Nash is only one of several NP-hard problems related to Nash equilibrium which have approximate variants which are as hard as planted clique.
2. We show that, unlike for arbitrary Nash, we cannot improve upon a simple 1/2-equilibrium algorithm for these problems (again assuming hardness of planted clique).
This is joint work with Mark Braverman and Eden Chlamtac.