On Finding Local Nash Equilibria (and only Local Nash Equilibria) in Zero-Sum Games
Top Cited Papers
Open Access
- 30 June 2025
- journal article
- Published by Association for Computing Machinery (ACM) in ACM / IMS Journal of Data Science
- Vol. 2 (2) , 1-26
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. Further, we show that the algorithm exhibits no oscillatory behavior in neighborhoods of equilibria and that it has the same per-iteration complexity as other recently proposed algorithms. Furthermore, we give convergence rates in structured classes of zero-sum games. 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).Keywords
Funding Information
- National Sleep Foundation (2240110)
This publication has 21 references indexed in Scilit:
- Local Nash Equilibria are Isolated, Strict Local Nash Equilibria in ‘Almost All’ Zero-Sum Continuous Games2019
- Multiple equilibria and limit cycles in evolutionary games with Logit DynamicsGames and Economic Behavior, 2012
- Robust Stochastic Approximation Approach to Stochastic ProgrammingSIAM Journal on Optimization, 2009
- The Complexity of Computing a Nash EquilibriumSIAM Journal on Computing, 2009
- Stochastic Approximation2008
- Algorithmic Game Theory2007
- Prediction, Learning, and Games2006
- Mixed Equilibria and Dynamical Systems Arising from Fictitious Play in Perturbed GamesGames and Economic Behavior, 1999
- Dynamics of Morse-Smale urn processesErgodic Theory and Dynamical Systems, 1995
- Monotone Operators and the Proximal Point AlgorithmSIAM Journal on Control and Optimization, 1976