Combinatorics Seminar
When: Sunday, March 13, 10am
Where: Schreiber 309
Speaker: Eden Chlamtac, Tel Aviv U.
Title: Inapproximability of NP-Complete variants of Nash
equilibrium
Abstract:
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 hidden 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 Hidden Clique hard.
2. We show that, unlike for arbitrary Nash, we cannot improve upon
a
simple 1/2-equilibrium algorithm for these problems (assuming
hardness
of Hidden Clique).
Finally, if time permits, I will discuss the complexity of finding
approximate pure equilibria in Bayesian games.
Based on joint work with Per Austrin and Mark Braverman.