Finding all Nash equilibria of a finite game using polynomial algebra
By Ruchira S. Datta. 2006
75 citations recorded by the source corpus.
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.
Subfields: Artificial Intelligence, Computational Theory and Mathematics, Geometry and Topology
View Paper: https://www.semanticscholar.org/paper/19b3ec64da39d18ffb15bc72be013a25f2ebe325
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
In Computational Theory and Mathematics
In Geometry and Topology
Citations in the corpus
- Perturbation Methods for Markov-Switching DSGE Models (2014, methodology): “2For the theory of Gröbner bases and its application to economics, see Kubler and Schmedders (2010a) and Kubler and Schmedders (2010b) for finding multiple equilibria in general equilibrium models and Datta (2010) for finding all Nash equilibria.”