# Nash Equilibria via Stochastic Eigendecomposition

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 10 of its 56 references that are in the map.
- First posted on arXiv 4 Nov 2024.

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

- [A Unified Game-Theoretic Approach to Multiagent Reinforcement Learning](https://mlsanity.com/paper/1711.00832/) (2017)
- [From Poincar'e Recurrence to Convergence in Imperfect Information Games: Finding Equilibrium via Regularization](https://mlsanity.com/paper/2002.08456/) (2020)
- [α-Rank: Multi-Agent Evaluation by Evolution](https://mlsanity.com/paper/1903.01373/) (2019)
- [No-regret learning and mixed Nash equilibria: They do not mix](https://mlsanity.com/paper/2010.09514/) (2020)
- [EigenGame: PCA as a Nash Equilibrium](https://mlsanity.com/paper/2010.00554/) (2020)
- [Spectral Inference Networks: Unifying Deep and Spectral Learning](https://mlsanity.com/paper/1806.02215/) (2018)
- [First Efficient Convergence for Streaming k-PCA: a Global, Gap-Free, and Near-Optimal Rate](https://mlsanity.com/paper/1607.07837/) (2016)
- [LazySVD: Even Faster SVD Decomposition Yet Without Agonizing Pain](https://mlsanity.com/paper/1607.03463/) (2016)
- [EigenGame Unloaded: When playing games is better than optimizing](https://mlsanity.com/paper/2102.04152/) (2021)
- [Approximating Nash Equilibria in Normal-Form Games via Stochastic Optimization](https://mlsanity.com/paper/2310.06689/) (2023)

## Abstract (arXiv)

This work proposes a novel set of techniques for approximating a Nash equilibrium in a finite, normal-form game. It achieves this by constructing a new reformulation as solving a parameterized system of multivariate polynomials with tunable complexity. In doing so, it forges an itinerant loop from game theory to machine learning and back. We show a Nash equilibrium can be approximated with purely calls to stochastic, iterative variants of singular value decomposition and power iteration, with implications for biological plausibility. We provide pseudocode and experiments demonstrating solving for all equilibria of a general-sum game using only these readily available linear algebra tools.