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

Abstract

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).

References in corpus (1)

• GANs Trained by a Two Time-Scale Update Rule Converge to a Local Nash Equilibrium

Cited by in corpus (9)

• GANs May Have No Nash Equilibria
• On Solving Minimax Optimization Locally: A Follow-the-Ridge Approach
• Generative Minimization Networks: Training GANs Without Competition
• Gradient Descent-Ascent Provably Converges to Strict Local Minmax Equilibria with a Finite Timescale Separation
• Adversarial Environment Generation for Learning to Navigate the Web
• On Characterizing GAN Convergence Through Proximal Duality Gap
• A Game-Theoretic Approach to Multi-Agent Trust Region Optimization
• Minimax Optimization with Smooth Algorithmic Adversaries
• Distributed stochastic subgradient-free algorithm for Nash equilibrium seeking in two-network zero-sum games