IDEAS home Printed from https://ideas.repec.org/
MyIDEAS: Login to save this paper or follow this series

Homotopy Methods to Compute Equilibria in Game Theory

  • Herings P. Jean-Jacques
  • Peeters Ronald

    (METEOR)

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.

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: http://digitalarchive.maastrichtuniversity.nl/fedora/objects/guid:56d43efa-aba8-4630-8e94-728d6c78700f/datastreams/ASSET1/content
Our checks indicate that this address may not be valid because: 401 Unauthorized. If this is indeed the case, please notify (Charles Bollen)


Download Restriction: no

Paper provided by Maastricht University, Maastricht Research School of Economics of Technology and Organization (METEOR) in its series Research Memorandum with number 046.

as
in new window

Length:
Date of creation: 2006
Date of revision:
Handle: RePEc:unm:umamet:2006046
Contact details of provider: Postal: P.O. Box 616, 6200 MD Maastricht
Phone: +31 (0)43 38 83 830
Web page: http://www.maastrichtuniversity.nl/
Email:


More information through EDIRC

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. 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.
  2. Andrew McLennan, 2005. "The Expected Number of Nash Equilibria of a Normal Form Game," Econometrica, Econometric Society, vol. 73(1), pages 141-174, 01.
  3. C. E. Lemke, 1965. "Bimatrix Equilibrium Points and Mathematical Programming," Management Science, INFORMS, vol. 11(7), pages 681-689, May.
  4. 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.
  5. 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).
  6. 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.
  7. E. Kohlberg & J.-F. Mertens, 1998. "On the Strategic Stability of Equilibria," Levine's Working Paper Archive 445, David K. Levine.
  8. Wilson, Robert, 1992. "Computing Simply Stable Equilibria," Econometrica, Econometric Society, vol. 60(5), pages 1039-70, September.
  9. 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.
  10. P.J.J. Herings & R. Peeters, 2001. "A Globally Convergent Algorithm to Compute Stationary Equilibria in Stochastic Games," Game Theory and Information 0205001, EconWPA.
  11. 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.
  12. Hans M. Amman & David A. Kendrick, . "Computational Economics," Online economics textbooks, SUNY-Oswego, Department of Economics, number comp1, March.
  13. John Geanakoplos, 2003. "Nash and Walras equilibrium via Brouwer," Economic Theory, Springer, vol. 21(2), pages 585-603, 03.
  14. 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.
  15. 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).
  16. 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.
  17. Nowak, Andrzej S. & Szajowski, Krzysztof, 1998. "Nonzero-sum Stochastic Games," MPRA Paper 19995, University Library of Munich, Germany, revised 1999.
  18. 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.
  19. Robert Wilson, 2010. "Computing Equilibria of n-person Games," Levine's Working Paper Archive 402, David K. Levine.
  20. 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.
  21. Richard Mckelvey & Thomas Palfrey, 1998. "Quantal Response Equilibria for Extensive Form Games," Experimental Economics, Springer, vol. 1(1), pages 9-41, June.
  22. 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.
  23. Robert Wilson, 1972. "Computing Equilibria of Two-Person Games from the Extensive Form," Management Science, INFORMS, vol. 18(7), pages 448-460, March.
  24. 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.
  25. 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.
  26. Kenneth L. Judd, 1997. "Computational Economics and Economic Theory: Substitutes or Complements," NBER Technical Working Papers 0208, National Bureau of Economic Research, Inc.
  27. 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.
  28. 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.
  29. 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.
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:unm:umamet:2006046. 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: (Charles Bollen)

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.