On Finding Local Nash Equilibria (and Only Local Nash Equilibria) in Zero-Sum Games

By Eric V. Mazumdar, Michael I. Jordan, S. Sastry. 2019

112 citations recorded by the source corpus.

We propose local symplectic surgery, a two-timescale procedure for finding local Nash equilibria in two-player zero-sum games. We first show that previous gradient-based algorithms cannot guarantee convergence to local Nash equilibria due to the existence of non-Nash stationary points. By taking advantage of the differential structure of the game, we construct an algorithm for which the local Nash equilibria are the only attracting fixed points. We also show that the algorithm exhibits no oscillatory behaviors in neighborhoods of equilibria and show that it has the same per-iteration complexity as other recently proposed algorithms. We conclude by validating the algorithm on two numerical examples: a toy example with multiple Nash equilibria and a non-Nash equilibrium, and the training of a small generative adversarial network (GAN).

Subfields: Management Science and Operations Research, Public Health, Environmental and Occupational Health, Reinforcement Learning

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Management Science and Operations Research

In Public Health, Environmental and Occupational Health

In Reinforcement Learning

Citations in the corpus

A Tight and Unified Analysis of Extragradient for a Whole Spectrum of Differentiable Games (2019, background): “However, as shown by Adolphs et al. (2019); Mazumdar et al. (2019), stationary points are not necessarily Nash equilibria in general but if v is monotone, these two notions are equivalent.”
Convergence of Learning Dynamics in Stackelberg Games (2019, background): “[27] propose schemes to avoid such attractors because they have been classified or viewed as being undesirable.”
Adversarial Environment Generation for Learning to Navigate the Web (2021, background): “However, in practice gradient-based multi-agent RL has no convergence guarantees, is highly non-stationary, and will often fail to converge (Mazumdar et al., 2019a;b).”
On the convergence of single-call stochastic extra-gradient methods (2019, background): “[28] proposed a class of algorithms that eliminate stationary points which are not local Nash equilibria.”
Accelerating Smooth Games by Manipulating Spectral Shapes (2020, background): “…2014; Pfau and Vinyals, 2016) have caused a surge of interest in the theoretical understanding of ﬁrst-order methods for the solution of diﬀerentiable multi-player games (Pala-niappan and Bach, 2016; Gidel et al., 2019a; Balduzzi et al., 2018; Mescheder et al., 2017, 2018; Mazumdar et al., 2019).”
A Tight and Unified Analysis of Gradient-Based Methods for a Whole Spectrum of Differentiable Games (2020, background): “Indeed, Mescheder et al. (2017) showed that eigenvalues of the Jacobian of the vector field with small real parts and large imaginary parts could be at the origin of these problems.”
On Solving Minimax Optimization Locally: A Follow-the-Ridge Approach (2019, unknown): “As noted by Mescheder et al. (2017); Gidel et al.”