mlsanityData to 7 Oct 2026

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

arXiv 1901.00838 ↗First posted 3 Jan 2019cs.LG math.OC stat.MLcited by 35

Not on the map. Why?

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

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 9; 2022: 12; 2023: 7; 2024: 1; 2025: 4; 2026: 2.

35 papers.

Sort:

By area:

  1. 2022COLA: Consistent Learning with Opponent-Learning Awarenesscited by 38
  2. 2022Modeling Content Creator Incentives on Algorithm-Curated Platformscited by 35
  3. 2022Environment Generation for Zero-Shot Compositional Reinforcement Learningcited by 32
  4. 2022Accelerated Single-Call Methods for Constrained Min-Max Optimizationcited by 31
  5. 2023Escaping limit cycles: Global convergence for constrained nonconvex-nonconcave minimax problemscited by 21
  6. 2022General Intelligence Requires Rethinking Explorationcited by 20
  7. 2021Fast Distributionally Robust Learning with Variance Reduced Min-Max Optimizationcited by 19
  8. 2022Efficiently Escaping Saddle Points in Bilevel Optimizationcited by 19
  9. 2021On the Convergence of Stochastic Extragradient for Bilinear Games using Restarted Iteration Averagingcited by 18
  10. 2021Discretization Drift in Two-Player Gamescited by 14
  11. 2021Adversarial Environment Generation for Learning to Navigate the Webcited by 13
  12. 2022Riemannian Hamiltonian methods for min-max optimization on manifoldscited by 12
23 more
  1. 2022Sion's Minimax Theorem in Geodesic Metric Spaces and a Riemannian Extragradient Algorithmcited by 9
  2. 2021Minimax Optimization with Smooth Algorithmic Adversariescited by 8
  3. 2021Nonconvex-Nonconcave Min-Max Optimization with a Small Maximization Domaincited by 8
  4. 2023Stability and Generalization of the Decentralized Stochastic Gradient Descent Ascent Algorithmcited by 8
  5. 2021A Game-Theoretic Approach to Multi-Agent Trust Region Optimizationcited by 7
  6. 2021On Characterizing GAN Convergence Through Proximal Duality Gapcited by 3
  7. 2023Adaptive Consensus Optimization Method for GANscited by 3
  8. 2022Simultaneous Transport Evolution for Minimax Equilibria on Measurescited by 2
  9. 2022Robust Forecasting for Robotic Control: A Game-Theoretic Approachcited by 2
  10. 2023Last-Iterate Convergence of Adaptive Riemannian Gradient Descent for Equilibrium Computationcited by 2
  11. 2024Exploring the Precise Dynamics of Single-Layer GAN Models: Leveraging Multi-Feature Discriminators for High-Dimensional Subspace Learningcited by 2
  12. 2025Policy Design for Two-sided Platforms with Participation Dynamicscited by 2
  13. 2025A Framework for Finding Local Saddle Points in Two-Player Zero-Sum Black-Box Gamescited by 1
  14. 2025Efficient compression of neural networks and datasetscited by 1
  15. 2025Two-Player Zero-Sum Games with Bandit Feedbackcited by 1
  16. 2021GDA-AM: On the effectiveness of solving minimax optimization via Anderson Accelerationcited by 0
  17. 2022On the Nash equilibrium of moment-matching GANs for stationary Gaussian processescited by 0
  18. 2022Finding mixed-strategy equilibria of continuous-action games without gradients using randomized policy networkscited by 0
  19. 2023ApproxED: Approximate exploitability descent via learned best responsescited by 0
  20. 2023Uncoupled Learning of Differential Stackelberg Equilibria with Commitmentscited by 0
  21. 2023A Gentle Introduction to Gradient-Based Optimization and Variational Inequalities for Machine Learningcited by 0
  22. 2026Local exponential stability of mean-field Langevin descent-ascent and associated particle systemcited by 0
  23. 2026LLM Active Alignment: A Nash Equilibrium Perspectivecited by 0