Finding all Nash equilibria of a finite game using polynomial algebra
综述了如何通过多项式方程组求解有限博弈的所有纳什均衡，包括构造特殊博弈、利用多面体同伦延拓和Gröbner基方法，并介绍了Gambit软件包的应用。
The set of Nash equilibria of a finite game is the set of nonnegative solutions to a system of polynomial equations. In this survey article, we describe how to construct certain special games and explain how to find all the complex roots of the corresponding polynomial systems, including all the Nash equilibria. We then explain how to find all the complex roots of the polynomial systems for arbitrary generic games, by polyhedral homotopy continuation starting from the solutions to the specially constructed games. We describe the use of Gröbner bases to solve these polynomial systems and to learn geometric information about how the solution set varies with the payoff functions. Finally, we review the use of the Gambit software package to find all Nash equilibria of a finite game.