A globally convergent algorithm to Compute All Nash Equilibria for n-person games
AbstractIn this paper an algorithm is presented to compute all Nash equilibria for games in normal form on the only premises that the number of Nash equilibria is finite. The algorithm relies on decomposing the game by means of support-sets. For each support-set, the set of totally mixed equilibria of the support-restricted game that results by restricting the players to strategies in the support-set can be characterized by a system of polynomial equations and inequalities. By solving those systems for each support-set, all equilibria are found. The algorithm belongs to the class of homotopy-methods and is implementable. Finally, several techniques to speed up computations are proposed.
Download InfoIf you experience problems downloading a file, check if you have the proper application to view it first. In case of further problems read the IDEAS help page. Note that these files are not on the IDEAS site. Please be patient as the files may be large.
Bibliographic InfoPaper provided by Maastricht University in its series Open Access publications from Maastricht University with number urn:nbn:nl:ui:27-12160.
Date of creation: 2005
Date of revision:
Publication status: Published in Annals of operations research (2005) v.137, p.349-368
Contact details of provider:
Web page: http://www.maastrichtuniversity.nl/web/Home.htm
Other versions of this item:
- Herings,Jean-Jacques & Peeters,Ronald, 2002. "A Globally Convergent Algorithm to Compute All Nash Equilibria of n-Person Games," Research Memoranda 084, Maastricht : METEOR, Maastricht Research School of Economics of Technology and Organization.
You can help add them by filling out this form.
CitEc Project, subscribe to its RSS feed for this item.
- Ruchira Datta, 2010. "Finding all Nash equilibria of a finite game using polynomial algebra," Economic Theory, Springer, vol. 42(1), pages 55-96, January.
- P. Herings & Ronald Peeters, 2010.
"Homotopy methods to compute equilibria in game theory,"
Springer, vol. 42(1), pages 119-156, January.
- Herings, P. Jean-Jacques & Peeters, Ronald, 2006. "Homotopy Methods to Compute Equilibria in Game Theory," Research Memoranda 046, Maastricht : METEOR, Maastricht Research School of Economics of Technology and Organization.
- Kolen, Antoon, 2006. "A genetic algorithm for the partial binary constraint satisfaction problem: an application to a frequency assignment problem," Research Memoranda 045, Maastricht : METEOR, Maastricht Research School of Economics of Technology and Organization.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (J.Odekerken).
If references are entirely missing, you can add them using this form.