Nash Equilibria in Perturbation Resilient Games

Understand

Motivated by the fact that in many game-theoretic settings, the game analyzed is only an approximation to the game being played, in this work we analyze equilibrium computation for the broad and natural class of bimatrix games that are stable to perturbations.

• We specifically focus on games with the property that small changes in the payoff matrices do not cause the Nash equilibria of the game to fluctuate wildly.
• For such games we show how one can compute approximate Nash equilibria more efficiently than the general result of Lipton et al.
• \cite{LMM03}, by an amount that depends on the degree of stability of the game and that reduces to their bound in the worst case.