# Characterizing Nash Equilibria in Zero-Sum Games: A Physics-Inspired, Parallelizable Approach with a Linear Number of Gradient Queries

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 17 of its 31 references that are in the map.
- First posted on arXiv 15 Jul 2025.

## Builds on (most cited first, 17 of 17)

- [Large Scale GAN Training for High Fidelity Natural Image Synthesis](https://mlsanity.com/paper/1809.11096/) (2018)
- [Training GANs with Optimism](https://mlsanity.com/paper/1711.00141/) (2017)
- [Precomputed Real-Time Texture Synthesis with Markovian Generative Adversarial Networks](https://mlsanity.com/paper/1604.04382/) (2016)
- [Cycles in adversarial regularized learning](https://mlsanity.com/paper/1709.02738/) (2017)
- [The Limit Points of (Optimistic) Gradient Descent in Min-Max Optimization](https://mlsanity.com/paper/1807.03907/) (2018)
- [Last-Iterate Convergence: Zero-Sum Games and Constrained Min-Max Optimization](https://mlsanity.com/paper/1807.04252/) (2018)
- [Near-Optimal No-Regret Learning in General Games](https://mlsanity.com/paper/2108.06924/) (2021)
- [Accelerated Algorithms for Smooth Convex-Concave Minimax Problems with O(1/k2) Rate on Squared Gradient Norm](https://mlsanity.com/paper/2102.07922/) (2021)
- [Last Iterate is Slower than Averaged Iterate in Smooth Convex-Concave Saddle Point Problems](https://mlsanity.com/paper/2002.00057/) (2020)
- [Vox2Vox: 3D-GAN for Brain Tumour Segmentation](https://mlsanity.com/paper/2003.13653/) (2020)
- [Finite Regret and Cycles with Fixed Step-Size via Alternating Gradient Descent-Ascent](https://mlsanity.com/paper/1907.04392/) (2019)
- [Accelerated Algorithms for Constrained Nonconvex-Nonconcave Min-Max Optimization and Comonotone Inclusion](https://mlsanity.com/paper/2206.05248/) (2022)
- [Multi-agent online learning in time-varying games](https://mlsanity.com/paper/1809.03066/) (2018)
- [Multi-Agent Learning in Network Zero-Sum Games is a Hamiltonian System](https://mlsanity.com/paper/1903.01720/) (2019)
- [Bayesian Conditional GAN for MRI Brain Image Synthesis](https://mlsanity.com/paper/2005.11875/) (2020)
- [Deform-GAN:An Unsupervised Learning Model for Deformable Registration](https://mlsanity.com/paper/2002.11430/) (2020)
- [Oleft(1/Tright) Time-Average Convergence in a Generalization of Multiagent Zero-Sum Games](https://mlsanity.com/paper/2110.02482/) (2021)

## Abstract (arXiv)

We study online optimization methods for zero-sum games, a fundamental problem in adversarial learning in machine learning, economics, and many other domains. Traditional methods approximate Nash equilibria (NE) using either regret-based methods (time-average convergence) or contraction-map-based methods (last-iterate convergence). We propose a new method based on Hamiltonian dynamics in physics and prove that it can characterize the set of NE in a finite (linear) number of iterations of alternating gradient descent in the unbounded setting, modulo degeneracy, a first in online optimization. Unlike standard methods for computing NE, our proposed approach can be parallelized and works with arbitrary learning rates, both firsts in algorithmic game theory. Experimentally, we support our results by showing our approach drastically outperforms standard methods.