ECCC-Report TR15-093https://eccc.weizmann.ac.il/report/2015/093Comments and Revisions published for TR15-093en-usMon, 08 Jun 2015 03:48:05 +0300
Paper TR15-093
| Inapproximability of Nash Equilibrium |
Aviad Rubinstein
https://eccc.weizmann.ac.il/report/2015/093We 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.Mon, 08 Jun 2015 03:48:05 +0300https://eccc.weizmann.ac.il/report/2015/093