Computing Approximate Nash Equilibria in Polymatrix Games

Argyrios Deligkas, John Fearnley, Rahul Savani +1

In an $\epsilon$-Nash equilibrium, a player can gain at most $\epsilon$ by unilaterally changing his behaviour. For two-player (bimatrix) games with payoffs in $[0,1]$, the best-known$\epsilon$ achieva…