IDEAS home Printed from
MyIDEAS: Log in (now much improved!) to save this article

Homotopy methods to compute equilibria in game theory

  • P. Herings


  • Ronald Peeters

This 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.

(This abstract was borrowed from another version of this item.)

If 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.

File URL:
Download Restriction: Access to full text is restricted to subscribers.

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.

Article provided by Springer & Society for the Advancement of Economic Theory (SAET) in its journal Economic Theory.

Volume (Year): 42 (2010)
Issue (Month): 1 (January)
Pages: 119-156

in new window

Handle: RePEc:spr:joecth:v:42:y:2010:i:1:p:119-156
DOI: 10.1007/s00199-009-0441-5
Contact details of provider: Web page:

Web page:

More information through EDIRC

Order Information: Web:

References listed on IDEAS
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.:

as in new window
  1. Herings,P. Jean-Jacques & Peeters,Ronald J.A.P, 2000. "Stationary Equilibria in Stochastic Games: Structure, Selection, and Computation," Research Memorandum 004, Maastricht University, Maastricht Research School of Economics of Technology and Organization (METEOR).
  2. 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.
  3. Andrew McLennan, 2005. "The Expected Number of Nash Equilibria of a Normal Form Game," Econometrica, Econometric Society, vol. 73(1), pages 141-174, 01.
  4. 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.
  5. Rosenthal, Robert W, 1989. "A Bounded-Rationality Approach to the Study of Noncooperative Games," International Journal of Game Theory, Springer;Game Theory Society, vol. 18(3), pages 273-91.
  6. Herings Jean-Jacques & Peeters Ronald, 2002. "A Globally Convergent Algorithm to Compute All Nash Equilibria of n-Person Games," Research Memorandum 084, Maastricht University, Maastricht Research School of Economics of Technology and Organization (METEOR).
  7. 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.
  8. Herings P. Jean-Jacques & Peeters R., 1999. "A Differentiable Homotopy to Compute Nash Equilibria of n-Person Games," Research Memorandum 038, Maastricht University, Maastricht Research School of Economics of Technology and Organization (METEOR).
  9. Herings, P.J.J. & van den Elzen, A.H., 1998. "Computation of the Nash Equilibrium Selected by the Tracing Procedure in N-Person Games," Discussion Paper 1998-04, Tilburg University, Center for Economic Research.
  10. Hans M. Amman & David A. Kendrick, . "Computational Economics," Online economics textbooks, SUNY-Oswego, Department of Economics, number comp1, December.
  11. Wilson, Robert, 1992. "Computing Simply Stable Equilibria," Econometrica, Econometric Society, vol. 60(5), pages 1039-70, September.
  12. John Geanakoplos, 2003. "Nash and Walras equilibrium via Brouwer," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 21(2), pages 585-603, 03.
  13. Nowak, Andrzej S. & Szajowski, Krzysztof, 1998. "Nonzero-sum Stochastic Games," MPRA Paper 19995, University Library of Munich, Germany, revised 1999.
  14. 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.
  15. Richard Mckelvey & Thomas Palfrey, 1998. "Quantal Response Equilibria for Extensive Form Games," Experimental Economics, Springer;Economic Science Association, vol. 1(1), pages 9-41, June.
  16. Voorneveld, Mark, 2003. "Probabilistic choice in games: properties of Rosenthal's t-solutions," SSE/EFI Working Paper Series in Economics and Finance 542, Stockholm School of Economics, revised 31 Oct 2003.
  17. 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.
  18. Kohlberg, Elon & Mertens, Jean-Francois, 1986. "On the Strategic Stability of Equilibria," Econometrica, Econometric Society, vol. 54(5), pages 1003-37, September.
  19. 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.
  20. Kenneth L. Judd, 1997. "Computational Economics and Economic Theory: Substitutes or Complements," NBER Technical Working Papers 0208, National Bureau of Economic Research, Inc.
  21. Yamamoto, Yoshitsugu, 1993. "A Path-Following Procedure to Find a Proper Equilibrium of Finite Games," International Journal of Game Theory, Springer;Game Theory Society, vol. 22(3), pages 249-59.
  22. Robert Wilson, 2010. "Computing Equilibria of n-person Games," Levine's Working Paper Archive 402, David K. Levine.
  23. 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.
  24. C. E. Lemke, 1965. "Bimatrix Equilibrium Points and Mathematical Programming," Management Science, INFORMS, vol. 11(7), pages 681-689, May.
  25. 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.
  26. Talman, A.J.J. & van den Elzen, A.H., 1991. "A procedure for finding Nash equilibria in bi-matrix games," Other publications TiSEM 14df3398-1521-43ad-8803-a, Tilburg University, School of Economics and Management.
  27. P.J.J. Herings & R. Peeters, 2001. "A Globally Convergent Algorithm to Compute Stationary Equilibria in Stochastic Games," Game Theory and Information 0205001, EconWPA.
  28. Robert Wilson, 1972. "Computing Equilibria of Two-Person Games from the Extensive Form," Management Science, INFORMS, vol. 18(7), pages 448-460, March.
  29. 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.
  30. 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.
  31. Mas-Colell,Andreu, 1985. "The Theory of General Economic Equilibrium," Cambridge Books, Cambridge University Press, number 9780521265140, September.
Full references (including those not matched with items on IDEAS)

This item is not listed on Wikipedia, on a reading list or among the top items on IDEAS.

When requesting a correction, please mention this item's handle: RePEc:spr:joecth:v:42:y:2010:i:1:p:119-156. See general information about how to correct material in RePEc.

For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Sonal Shukla)

or (Rebekah McClure)

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.

This information is provided to you by IDEAS at the Research Division of the Federal Reserve Bank of St. Louis using RePEc data.