Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR15-093 | 5th June 2015 22:23

Inapproximability of Nash Equilibrium

RSS-Feed




TR15-093
Authors: Aviad Rubinstein
Publication: 8th June 2015 03:48
Downloads: 529
Keywords: 


Abstract:

We prove that finding an $\epsilon$-approximate Nash equilibrium is PPAD-complete for constant $\epsilon$ and a particularly simple class of games: polymatrix, degree 3 graphical games, in which each player has only two actions.

As corollaries, we also prove similar inapproximability results for Bayesian Nash equilibrium in a two-player incomplete information game with a constant number of actions, for relative $\epsilon$-Nash equilibrium in a two-player game, for market equilibrium in a non-monotone market, for the generalized circuit problem defined by Chen et al. [CDT'09], and for approximate competitive equilibrium from equal incomes with indivisible goods.



ISSN 1433-8092 | Imprint