Nash Equilibria via Stochastic Eigendecomposition
This provides a method for solving all equilibria in general-sum games using linear algebra tools, with potential implications for biological plausibility.
The paper tackles approximating Nash equilibria in finite normal-form games by reformulating the problem as solving a parameterized system of multivariate polynomials, achieving this using stochastic iterative variants of singular value decomposition and power iteration.
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.