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

arXiv: https://arxiv.org/abs/1901.00838 · HTML: https://mlsanity.com/paper/1901.00838/

## Key facts

- Cited by 35 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Jan 2019.

## Built on by (most cited first, 30 of 35)

- [COLA: Consistent Learning with Opponent-Learning Awareness](https://mlsanity.com/paper/2203.04098/) (2022)
- [Modeling Content Creator Incentives on Algorithm-Curated Platforms](https://mlsanity.com/paper/2206.13102/) (2022)
- [Environment Generation for Zero-Shot Compositional Reinforcement Learning](https://mlsanity.com/paper/2201.08896/) (2022)
- [Accelerated Single-Call Methods for Constrained Min-Max Optimization](https://mlsanity.com/paper/2210.03096/) (2022)
- [Escaping limit cycles: Global convergence for constrained nonconvex-nonconcave minimax problems](https://mlsanity.com/paper/2302.09831/) (2023)
- [General Intelligence Requires Rethinking Exploration](https://mlsanity.com/paper/2211.07819/) (2022)
- [Fast Distributionally Robust Learning with Variance Reduced Min-Max Optimization](https://mlsanity.com/paper/2104.13326/) (2021)
- [Efficiently Escaping Saddle Points in Bilevel Optimization](https://mlsanity.com/paper/2202.03684/) (2022)
- [On the Convergence of Stochastic Extragradient for Bilinear Games using Restarted Iteration Averaging](https://mlsanity.com/paper/2107.00464/) (2021)
- [Discretization Drift in Two-Player Games](https://mlsanity.com/paper/2105.13922/) (2021)
- [Adversarial Environment Generation for Learning to Navigate the Web](https://mlsanity.com/paper/2103.01991/) (2021)
- [Riemannian Hamiltonian methods for min-max optimization on manifolds](https://mlsanity.com/paper/2204.11418/) (2022)
- [Sion's Minimax Theorem in Geodesic Metric Spaces and a Riemannian Extragradient Algorithm](https://mlsanity.com/paper/2202.06950/) (2022)
- [Stability and Generalization of the Decentralized Stochastic Gradient Descent Ascent Algorithm](https://mlsanity.com/paper/2310.20369/) (2023)
- [Minimax Optimization with Smooth Algorithmic Adversaries](https://mlsanity.com/paper/2106.01488/) (2021)
- [Nonconvex-Nonconcave Min-Max Optimization with a Small Maximization Domain](https://mlsanity.com/paper/2110.03950/) (2021)
- [A Game-Theoretic Approach to Multi-Agent Trust Region Optimization](https://mlsanity.com/paper/2106.06828/) (2021)
- [On Characterizing GAN Convergence Through Proximal Duality Gap](https://mlsanity.com/paper/2105.04801/) (2021)
- [Adaptive Consensus Optimization Method for GANs](https://mlsanity.com/paper/2304.10317/) (2023)
- [Simultaneous Transport Evolution for Minimax Equilibria on Measures](https://mlsanity.com/paper/2202.06460/) (2022)
- [Robust Forecasting for Robotic Control: A Game-Theoretic Approach](https://mlsanity.com/paper/2209.10802/) (2022)
- [Last-Iterate Convergence of Adaptive Riemannian Gradient Descent for Equilibrium Computation](https://mlsanity.com/paper/2306.16617/) (2023)
- [Exploring the Precise Dynamics of Single-Layer GAN Models: Leveraging Multi-Feature Discriminators for High-Dimensional Subspace Learning](https://mlsanity.com/paper/2411.00498/) (2024)
- [Policy Design for Two-sided Platforms with Participation Dynamics](https://mlsanity.com/paper/2502.01792/) (2025)
- [Finding mixed-strategy equilibria of continuous-action games without gradients using randomized policy networks](https://mlsanity.com/paper/2211.15936/) (2022)
- [ApproxED: Approximate exploitability descent via learned best responses](https://mlsanity.com/paper/2301.08830/) (2023)
- [A Framework for Finding Local Saddle Points in Two-Player Zero-Sum Black-Box Games](https://mlsanity.com/paper/2503.18224/) (2025)
- [Efficient compression of neural networks and datasets](https://mlsanity.com/paper/2505.17469/) (2025)
- [Two-Player Zero-Sum Games with Bandit Feedback](https://mlsanity.com/paper/2506.14518/) (2025)
- [GDA-AM: On the effectiveness of solving minimax optimization via Anderson Acceleration](https://mlsanity.com/paper/2110.02457/) (2021)

## Abstract (arXiv)

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