Home | Quick Search | Advanced Search | Bibliography submission | Bibliography submission using bibtex | Bibliography submission using bibtex file | Links | Help | Internal


TitleFinding all Nash equilibria of a finite game using polynomial algebra.
Author(s) Ruchira S. Datta
TypeArticle in Journal
AbstractThe 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.
KeywordsNash equilibrium, Normal form game, Algebraic variety
ISSN0938-2259; 1432-0479/e
URL http://link.springer.com/article/10.1007%2Fs00199-009-0447-z
JournalEcon. Theory
PublisherSpringer, Berlin/Heidelberg
Translation No
Refereed No