Nash Equilibria via Stochastic Eigendecomposition
Not on the map. Why?
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.
Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 10 of its 56 references that are in the map. First posted on arXiv 4 Nov 2024.
Builds on
10 of 56 references.
References · 10
- 2017A Unified Game-Theoretic Approach to Multiagent Reinforcement Learningcited by 265
- 2020From Poincar'e Recurrence to Convergence in Imperfect Information Games: Finding Equilibrium via Regularizationcited by 59
- 2019α-Rank: Multi-Agent Evaluation by Evolutioncited by 50
- 2020No-regret learning and mixed Nash equilibria: They do not mixcited by 49
- 2020EigenGame: PCA as a Nash Equilibriumcited by 39
- 2018Spectral Inference Networks: Unifying Deep and Spectral Learningcited by 34
- 2016First Efficient Convergence for Streaming k-PCA: a Global, Gap-Free, and Near-Optimal Ratecited by 31
- 2016LazySVD: Even Faster SVD Decomposition Yet Without Agonizing Paincited by 22
- 2021EigenGame Unloaded: When playing games is better than optimizingcited by 13
- 2023Approximating Nash Equilibria in Normal-Form Games via Stochastic Optimizationcited by 9
Built on by
Not cited yet.