INAPPROXIMABILITY OF NASH EQUILIBRIUM

Rubinstein, A

Rubinstein, A (reprint author), Univ Calif Berkeley, EECS, Berkeley, CA 94720 USA.

SIAM JOURNAL ON COMPUTING, 2018; 47 (3): 917

Abstract

We prove that finding an epsilon-approximate Nash equilibrium is PPAD-complete for constant epsilon and a particularly simple class of games: polymatr......

Full Text Link