Homotopy methods to compute equilibria in game theory
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.
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.
Volume (Year): 42 (2010)
Issue (Month): 1 (January)
|Contact details of provider:|| Web page: http://link.springer.de/link/service/journals/00199/index.htm|
|Order Information:||Web: http://link.springer.de/orders.htm|
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.:
- Nowak, Andrzej S. & Szajowski, Krzysztof, 1998. "Nonzero-sum Stochastic Games," MPRA Paper 19995, University Library of Munich, Germany, revised 1999.
- Herings, P.J.J. & van den Elzen, A.H., 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.
- 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.
- KOHLBERG, Elon & MERTENS, Jean-François, .
"On the strategic stability of equilibria,"
CORE Discussion Papers RP
-716, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
- Herings,P. Jean-Jacques & Peeters,Ronald J.A.P, 2000.
"Stationary Equilibria in Stochastic Games: Structure, Selection, and Computation,"
004, Maastricht University, Maastricht Research School of Economics of Technology and Organization (METEOR).
- Herings, P. Jean-Jacques & Peeters, Ronald J. A. P., 2004. "Stationary equilibria in stochastic games: structure, selection, and computation," Journal of Economic Theory, Elsevier, vol. 118(1), pages 32-60, September.
- Hans M. Amman & David A. Kendrick, . "Computational Economics," Online economics textbooks, SUNY-Oswego, Department of Economics, number comp1, December.
- 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.
- 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.
- 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.
- Andrew McLennan, 2005.
"The Expected Number of Nash Equilibria of a Normal Form Game,"
Econometric Society, vol. 73(1), pages 141-174, 01.
- McLennan, A., 1999. "The Expected Number of Nash Equilibria of a Normal Form Game," Papers 306, Minnesota - Center for Economic Research.
- John Geanakoplos, 2003. "Nash and Walras equilibrium via Brouwer," Economic Theory, Springer, vol. 21(2), pages 585-603, 03.
- 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.
- 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.
- 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.
- 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.
- 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.
- Herings, P.J.J., 1994.
"A globally and universally stable price adjustment process,"
1994-52, Tilburg University, Center for Economic Research.
- 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.
- 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.
- Kenneth L. Judd, 1997. "Computational Economics and Economic Theory: Substitutes or Complements," NBER Technical Working Papers 0208, National Bureau of Economic Research, Inc.
- P.J.J. Herings & R. Peeters, 2001. "A Globally Convergent Algorithm to Compute Stationary Equilibria in Stochastic Games," Game Theory and Information 0205001, EconWPA.
- Wilson, Robert, 1992. "Computing Simply Stable Equilibria," Econometrica, Econometric Society, vol. 60(5), pages 1039-70, September.
- 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).
- 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.
- Robert Wilson, 1972. "Computing Equilibria of Two-Person Games from the Extensive Form," Management Science, INFORMS, vol. 18(7), pages 448-460, March.
- 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.
- C. E. Lemke, 1965. "Bimatrix Equilibrium Points and Mathematical Programming," Management Science, INFORMS, vol. 11(7), pages 681-689, May.
- Richard Mckelvey & Thomas Palfrey, 1998. "Quantal Response Equilibria for Extensive Form Games," Experimental Economics, Springer, vol. 1(1), pages 9-41, June.
- 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.
- Robert Wilson, 2010. "Computing Equilibria of n-person Games," Levine's Working Paper Archive 402, David K. Levine.
- repec:ner:tilbur:urn:nbn:nl:ui:12-153117 is not listed on IDEAS
- 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.
- 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.
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: (Guenther Eichhorn)or (Christopher F Baum)
If references are entirely missing, you can add them using this form.