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

2019/01/03 by Eric Mazumdar, Michael I. Jordan, Mazumdar, Eric V. +3 · 19 citations
Decision Sciences · Medicine · #Advanced Bandit Algorithms Research #FOS: Computer and information sciences #FOS: Mathematics #Game Theory and Applications #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Mathematical and Theoretical Epidemiology and Ecology Models #Optimization and Control (math.OC)

paper · pdf · doi:10.48550/arxiv.1901.00838

openalex publication_date 2019/01/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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

Citations

• Stochastic Approximation: A Dynamical Systems Viewpoint
• Generative Adversarial Networks
• The Complexity of Computing a Nash Equilibrium

Cited by

• The Complexity of Min-Max Optimization with Product Constraints
• Convergence Analysis of Gradient-Based Learning with Non-Uniform Learning Rates in Non-Cooperative Multi-Agent Settings
• A Unified Analysis of First-Order Methods for Smooth Games via Integral Quadratic Constraints
• Fast Distributionally Robust Learning with Variance Reduced Min-Max Optimization
• What is Local Optimality in Nonconvex-Nonconcave Minimax Optimization?
• Game-Theoretic Multiagent Reinforcement Learning
• On the Suboptimality of Negative Momentum for Minimax Optimization
• Solving Zero-Sum Games through Alternating Projections
• Towards Better Understanding of Adaptive Gradient Algorithms in\n Generative Adversarial Nets
• A Solvable High-Dimensional Model of GAN
• Adversarial Environment Generation for Learning to Navigate the Web
• Gradient Descent-Ascent Provably Converges to Strict Local Minmax Equilibria with a Finite Timescale Separation
• Implicit competitive regularization in GANs
• Nonconvex-Nonconcave Min-Max Optimization with a Small Maximization Domain
• The Monge optimal transport barycenter problem
• The Confluence of Networks, Games and Learning
• Policy-Gradient Algorithms Have No Guarantees of Convergence in Linear Quadratic Games
• Policy Optimization Provably Converges to Nash Equilibria in Zero-Sum Linear Quadratic Games
• Two-Player Zero-Sum Games with Bandit Feedback
• Minimax Optimization with Smooth Algorithmic Adversaries

Related

• Second-Order Algorithms for Finding Local Nash Equilibria in Zero-Sum Games
• Local Nash Equilibria are Isolated, Strict Local Nash Equilibria in `Almost All' Zero-Sum Continuous Games
• Computing Nash Equilibria of Action-Graph Games
• A Parallelizable Approach for Characterizing NE in Zero-Sum Games After a Linear Number of Iterations of Gradient Descent
• A Descent-based method on the Duality Gap for solving zero-sum games