Aviad Rubinstein: Inapproximability of Nash Equilibrium

Tuesday, November 25, 2014 - 4:00pm to 5:00pm
Location: 
32-G575
Speaker: 
Aviad Rubinstein
Biography: 
UC Berkeley

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 market equilibrium in a non-monotone market, for the generalized circuit problem defined by Chen, Deng, and Tang, and for approximate competitive equilibrium from equal incomes with indivisible goods.

http://arxiv.org/abs/1405.3322