用随机迭代方法求解博弈均衡，仅需基础线性代数工具。
Nash Equilibria via Stochastic Eigendecomposition
- 将博弈均衡转化为可调复杂度的多项式方程组求解。
- 仅通过随机奇异值分解与幂迭代即可逼近均衡点。
- 方法生物可解释性强，适合无梯度优化与理论分析场景。
本文提出一种新方法，用于近似有限型、正常形式博弈中的纳什均衡。通过构建参数化的多变量多项式方程组，实现对均衡的重新表述。该方法在博弈论与机器学习之间建立循环路径。我们证明，仅需调用随机、迭代版本的奇异值分解与幂迭代，即可逼近纳什均衡，具有生物合理性。文中提供伪代码与实验，展示仅使用常见线性代数工具即可求解一般和博弈的所有均衡点。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。