Homotopy methods to compute equilibria in game theory
AbstractThis paper presents a complete survey of the use of homotopy methods in game theory.Homotopies allow for a robust computation of game-theoretic equilibria and their refinements. Homotopies are also suitable to compute equilibria that are selected by variousselection theories. We present all relevant techniques underlying homotopy algorithms.We give detailed expositions of the Lemke-Howson algorithm and the Van den Elzen-Talman algorithm to compute Nash equilibria in 2-person games, and the Herings-Vanden Elzen, Herings-Peeters, and McKelvey-Palfrey algorithms to compute Nash equilibriain general n-person games.
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.
As the access to this document is restricted, you may want to look for a different version under "Related research" (further below) or search for a different version of it.
Bibliographic InfoArticle provided by Springer in its journal Economic Theory.
Volume (Year): 42 (2010)
Issue (Month): 1 (January)
Contact details of provider:
Web page: http://link.springer.de/link/service/journals/00199/index.htm
Other versions of this item:
- Herings, P. Jean-Jacques & Peeters, Ronald, 2006. "Homotopy Methods to Compute Equilibria in Game Theory," Research Memorandum 046, Maastricht University, Maastricht Research School of Economics of Technology and Organization (METEOR).
- C62 - Mathematical and Quantitative Methods - - Mathematical Methods; Programming Models; Mathematical and Simulation Modeling - - - Existence and Stability Conditions of Equilibrium
- C63 - Mathematical and Quantitative Methods - - Mathematical Methods; Programming Models; Mathematical and Simulation Modeling - - - Computational Techniques
- C72 - Mathematical and Quantitative Methods - - Game Theory and Bargaining Theory - - - Noncooperative Games
- C73 - Mathematical and Quantitative Methods - - Game Theory and Bargaining Theory - - - Stochastic and Dynamic Games; Evolutionary Games
Please report citation or reference errors to , or , if you are the registered author of the cited work, log in to your RePEc Author Service profile, click on "citations" and make appropriate adjustments.:
- Voorneveld, Mark, 2003.
"Probabilistic choice in games: properties of Rosenthal's t-solutions,"
Working Paper Series in Economics and Finance
542, Stockholm School of Economics, revised 31 Oct 2003.
- Mark Voorneveld, 2006. "Probabilistic Choice in Games: Properties of Rosenthal’s t-Solutions," International Journal of Game Theory, Springer, vol. 34(1), pages 105-121, April.
- Richard Mckelvey & Thomas Palfrey, 1998. "Quantal Response Equilibria for Extensive Form Games," Experimental Economics, Springer, vol. 1(1), pages 9-41, June.
- van den Elzen, Antoon & Talman, Dolf, 1999. "An Algorithmic Approach toward the Tracing Procedure for Bi-matrix Games," Games and Economic Behavior, Elsevier, vol. 28(1), pages 130-145, July.
- Koller, Daphne & Megiddo, Nimrod & von Stengel, Bernhard, 1996. "Efficient Computation of Equilibria for Extensive Two-Person Games," Games and Economic Behavior, Elsevier, vol. 14(2), pages 247-259, June.
- Wilson, Robert, 1992. "Computing Simply Stable Equilibria," Econometrica, Econometric Society, vol. 60(5), pages 1039-70, September.
- Jean-Jacques Herings, P., 1997.
"A globally and universally stable price adjustment process,"
Journal of Mathematical Economics,
Elsevier, vol. 27(2), pages 163-193, March.
- Herings, P.J.J., 1994. "A globally and universally stable price adjustment process," Discussion Paper 1994-52, Tilburg University, Center for Economic Research.
- McLennan, A., 1999.
"The Expected Number of Nash Equilibria of a Normal Form Game,"
306, Minnesota - Center for Economic Research.
- Andrew McLennan, 2005. "The Expected Number of Nash Equilibria of a Normal Form Game," Econometrica, Econometric Society, vol. 73(1), pages 141-174, 01.
- Joseph T. Howson, Jr. & Robert W. Rosenthal, 1974. "Bayesian Equilibria of Finite Two-Person Games with Incomplete Information," Management Science, INFORMS, vol. 21(3), pages 313-315, November.
- E. Kohlberg & J.-F. Mertens, 1998.
"On the Strategic Stability of Equilibria,"
Levine's Working Paper Archive
445, David K. Levine.
- Gilboa, Itzhak & Zemel, Eitan, 1989.
"Nash and correlated equilibria: Some complexity considerations,"
Games and Economic Behavior,
Elsevier, vol. 1(1), pages 80-93, March.
- Itzhak Gilboa & Eitan Zemel, 1988. "Nash and Correlated Equilibria: Some Complexity Considerations," Discussion Papers 777, Northwestern University, Center for Mathematical Studies in Economics and Management Science.
- Robert Wilson, 2010. "Computing Equilibria of n-person Games," Levine's Working Paper Archive 402, David K. Levine.
- Kenneth L. Judd, 1997.
"Computational Economics and Economic Theory: Substitutes or Complements,"
NBER Technical Working Papers
0208, National Bureau of Economic Research, Inc.
- Judd, Kenneth L., 1997. "Computational economics and economic theory: Substitutes or complements?," Journal of Economic Dynamics and Control, Elsevier, vol. 21(6), pages 907-942, June.
- Turocy, Theodore L., 2005. "A dynamic homotopy interpretation of the logistic quantal response equilibrium correspondence," Games and Economic Behavior, Elsevier, vol. 51(2), pages 243-263, May.
- Talman, A.J.J. & Elzen , A.H. van den, 1991.
"A procedure for finding Nash equilibria in bi-matrix games,"
Open Access publications from Tilburg University
urn:nbn:nl:ui:12-153117, Tilburg University.
- Elzen, A.H. van den & Talman, A.J.J., 1988. "A procedure for finding Nash equilibria in bi-matrix games," Research Memorandum 334, Tilburg University, Faculty of Economics and Business Administration.
- Nowak, Andrzej S. & Szajowski, Krzysztof, 1998. "Nonzero-sum Stochastic Games," MPRA Paper 19995, University Library of Munich, Germany, revised 1999.
- Herings, P.J.J. & Elzen, A.H. van den, 1998.
"Computation of the Nash Equilibrium Selected by the Tracing Procedure in N-Person Games,"
1998-04, Tilburg University, Center for Economic Research.
- Herings, P. Jean-Jacques & van den Elzen, Antoon, 2002. "Computation of the Nash Equilibrium Selected by the Tracing Procedure in N-Person Games," Games and Economic Behavior, Elsevier, vol. 38(1), pages 89-117, January.
- McKelvey, Richard D. & McLennan, Andrew, 1996. "Computation of equilibria in finite games," Handbook of Computational Economics, in: H. M. Amman & D. A. Kendrick & J. Rust (ed.), Handbook of Computational Economics, edition 1, volume 1, chapter 2, pages 87-142 Elsevier.
- Govindan, Srihari & Wilson, Robert, 2004. "Computing Nash equilibria by iterated polymatrix approximation," Journal of Economic Dynamics and Control, Elsevier, vol. 28(7), pages 1229-1241, April.
- John Geanakoplos, 2003. "Nash and Walras equilibrium via Brouwer," Economic Theory, Springer, vol. 21(2), pages 585-603, 03.
- Eaves, B. Curtis & Schmedders, Karl, 1999. "General equilibrium models and homotopy methods," Journal of Economic Dynamics and Control, Elsevier, vol. 23(9-10), pages 1249-1279, September.
- Hans M. Amman & David A. Kendrick, . "Computational Economics," Online economics textbooks, SUNY-Oswego, Department of Economics, number comp1, Spring.
- Govindan, Srihari & Wilson, Robert, 2003. "A global Newton method to compute Nash equilibria," Journal of Economic Theory, Elsevier, vol. 110(1), pages 65-86, May.
- Rosenthal, Robert W, 1989. "A Bounded-Rationality Approach to the Study of Noncooperative Games," International Journal of Game Theory, Springer, vol. 18(3), pages 273-91.
- Yamamoto, Yoshitsugu, 1993. "A Path-Following Procedure to Find a Proper Equilibrium of Finite Games," International Journal of Game Theory, Springer, vol. 22(3), pages 249-59.
- Robert Wilson, 1972. "Computing Equilibria of Two-Person Games from the Extensive Form," Management Science, INFORMS, vol. 18(7), pages 448-460, March.
- P.J.J. Herings & R. Peeters, 2001. "A Globally Convergent Algorithm to Compute Stationary Equilibria in Stochastic Games," Game Theory and Information 0205001, EconWPA.
- C. E. Lemke, 1965. "Bimatrix Equilibrium Points and Mathematical Programming," Management Science, INFORMS, vol. 11(7), pages 681-689, May.
- Ron Borkovsky & Ulrich Doraszelski & Yaroslav Kryukov, 2012. "A dynamic quality ladder model with entry and exit: Exploring the equilibrium correspondence using the homotopy method," Quantitative Marketing and Economics, Springer, vol. 10(2), pages 197-229, June.
- Borkovsky, Ron N. & Doraszelski, Ulrich & Kryukov, Yaroslav, 2009. "A Dynamic Quality Ladder Model with Entry and Exit: Exploring the Equilibrium Correspondence Using the Homotopy Method," CEPR Discussion Papers 7560, C.E.P.R. Discussion Papers.
- Iryna Topolyan, 2013. "Existence of perfect equilibria: a direct proof," Economic Theory, Springer, vol. 53(3), pages 697-705, August.
- Bernhard Stengel, 2010. "Computation of Nash equilibria in finite games: introduction to the symposium," Economic Theory, Springer, vol. 42(1), pages 1-7, January.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Guenther Eichhorn) or (Christopher F Baum).
If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.
If references are entirely missing, you can add them using this form.
If the full references list an item that is present in RePEc, but the system did not link to it, you can help with this form.
If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your profile, as there may be some citations waiting for confirmation.
Please note that corrections may take a couple of weeks to filter through the various RePEc services.