Advanced Search
MyIDEAS: Login to save this paper or follow this series

Stationary Equilibria in Stochastic Games: Structure, Selection, and Computation

Contents:

Author Info

  • Herings,P. Jean-Jacques
  • Peeters,Ronald J.A.P

    (METEOR)

Abstract

This paper is the first to introduce an algorithm to compute stationary equilibria in stochastic games, and shows convergence of the algorithm for almost all such games. Moreover, since in general the number of stationary equilibria is overwhelming, we pay attention to the issue of equilibrium selection. We do this by extending the linear tracing procedure to the class of stochastic games, called the stochastic tracing procedure. From a computational point of view, the class of stochastic games possesses substantial difficulties compared to normal form games. Apart from technical difficulties, there are also conceptual difficulties,, for instance the question how to extend the linear tracing procedure to the environment of stochastic games. We prove that there is a generic subclass of the class of stochastic games for which the stochastic tracing procedure is a compact one-dimensional piecewise differentiable manifold with boundary. Furthermore, we prove that the stochastic tracing procedure generates a unique path leading from any exogenously specified prior belief, to a stationary equilibrium. A well-chosen transformation of variables is used to formulate an everywhere differentiable homotopy function, whose zeros describe the (unique) path generated by the stochastic tracing procedure. Because of differentiability we are able to follow this path using standard path-following techniques. This yields a globally convergent algorithm that is easily and robustly implemented on a computer using existing software routines. As a by-product of our results, we extend a recent result on the generic finiteness of stationary equilibria in stochastic games to oddness of equilibria.

Download Info

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://edocs.ub.unimaas.nl/loader/file.asp?id=353
Download Restriction: no

Bibliographic Info

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

as in new window
Length:
Date of creation: 2000
Date of revision:
Handle: RePEc:unm:umamet:2000004

Contact details of provider:
Postal: P.O. Box 616, 6200 MD Maastricht
Phone: +31 (0)43 38 83 830
Email:
Web page: http://www.maastrichtuniversity.nl/
More information through EDIRC

Related research

Keywords: mathematical economics and econometrics ;

Other versions of this item:

References

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. Eric Maskin & Jean Tirole, 1997. "Markov Perfect Equilibrium, I: Observable Actions," Harvard Institute of Economic Research Working Papers 1799, Harvard - Institute of Economic Research.
  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. Ariel Pakes & Richard Ericson, 1989. "Empirical Implications of Alternative Models of Firm Dynamics," NBER Working Papers 2893, National Bureau of Economic Research, Inc.
  4. Hans Haller & Roger Lagunoff, 2000. "Genericity and Markovian Behavior in Stochastic Games," Econometrica, Econometric Society, vol. 68(5), pages 1231-1248, September.
  5. Herings, P.J.J. & Elzen, A.H. van den, 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.
  6. John C. Harsanyi & Reinhard Selten, 1988. "A General Theory of Equilibrium Selection in Games," MIT Press Books, The MIT Press, edition 1, volume 1, number 0262582384, December.
  7. R. McKelvey & T. Palfrey, 2010. "Quantal Response Equilibria for Normal Form Games," Levine's Working Paper Archive 510, David K. Levine.
  8. Richard Mckelvey & Thomas Palfrey, 1998. "Quantal Response Equilibria for Extensive Form Games," Experimental Economics, Springer, vol. 1(1), pages 9-41, June.
  9. Bernhard von Stengel & Antoon van den Elzen & Dolf Talman, 2002. "Computing Normal Form Perfect Equilibria for Extensive Two-Person Games," Econometrica, Econometric Society, vol. 70(2), pages 693-715, March.
  10. Kenneth L. Judd, 1997. "Computational Economics and Economic Theory: Substitutes or Complements," NBER Technical Working Papers 0208, National Bureau of Economic Research, Inc.
  11. P. Jean-Jacques Herings, 2000. "Two simple proofs of the feasibility of the linear tracing procedure," Economic Theory, Springer, vol. 15(2), pages 485-490.
  12. Dirk Bergemann & Juuso Valimaki, 1996. "Learning and Strategic Pricing," Cowles Foundation Discussion Papers 1113, Cowles Foundation for Research in Economics, Yale University.
  13. Robert Wilson, 2010. "Computing Equilibria of n-person Games," Levine's Working Paper Archive 402, David K. Levine.
  14. McLennan, A., 1999. "The Expected Number of Nash Equilibria of a Normal Form Game," Papers 306, Minnesota - Center for Economic Research.
  15. Herbert E. Scarf, 1967. "The Approximation of Fixed Points of a Continuous Mapping," Cowles Foundation Discussion Papers 216R, Cowles Foundation for Research in Economics, Yale University.
  16. G. Steven Olley & Ariel Pakes, 1992. "The Dynamics of Productivity in the Telecommunications Equipment Industry," NBER Working Papers 3977, National Bureau of Economic Research, Inc.
  17. 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.
  18. Breton, Michele & Haurie, Alain & Filar, Jerzy A., 1986. "On the computation of equilibria in discounted stochastic dynamic games," Journal of Economic Dynamics and Control, Elsevier, vol. 10(1-2), pages 33-36, June.
  19. Stengel, B. von & Elzen, A.H. van den & Talman, A.J.J., 1996. "Tracing equilibria in extensive games by complementary pivoting," Discussion Paper 1996-86, Tilburg University, Center for Economic Research.
Full references (including those not matched with items on IDEAS)

Citations

Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
as in new window

Cited by:
  1. Arthur Zillante, 2005. "Spaced Out Monopolies: Theory and Empirics of Alternating Product Releases," Industrial Organization 0505008, EconWPA.
  2. Balbus, Łukasz & Reffett, Kevin & Woźny, Łukasz, 2014. "A constructive study of Markov equilibria in stochastic games with strategic complementarities," Journal of Economic Theory, Elsevier, vol. 150(C), pages 815-840.
  3. Doraszelski, Ulrich & Satterthwaite, Mark, 2007. "Computable Markov-Perfect Industry Dynamics: Existence, Purification, and Multiplicity," CEPR Discussion Papers 6212, C.E.P.R. Discussion Papers.
  4. Roger Lagunoff & Hans Haller, 1997. "Markov Perfect Equilibria in Repeated Asynchronous Choice Games," Game Theory and Information 9707006, EconWPA.
  5. Murat Kurt & Mark S. Roberts & Andrew J. Schaefer & M. Utku Ünver, 2011. "Valuing Prearranged Paired Kidney Exchanges: A Stochastic Game Approach," Boston College Working Papers in Economics 785, Boston College Department of Economics, revised 14 Oct 2011.
  6. John Duggan & Tasos Kalandrakis, 2007. "Dynamic Legislative Policy Making," Wallis Working Papers WP45, University of Rochester - Wallis Institute of Political Economy.
  7. Doraszelski, Ulrich & Escobar, Juan, 2008. "A Theory of Regular Markov Perfect Equilibria in Dynamic Stochastic Games: Genericity, Stability, and Purification," CEPR Discussion Papers 6805, C.E.P.R. Discussion Papers.
  8. Frank H. Page & Myrna H. Wooders, 2009. "Endogenous Network Dynamics," Working Papers 2009.28, Fondazione Eni Enrico Mattei.
  9. David Besanko & Ulrich Doraszelski & Yaroslav Kryukov & Mark Satterthwaite, 2007. "Learning-by-Doing, Organizational Forgetting, and Industry Dynamics," Levine's Bibliography 321307000000000903, UCLA Department of Economics.
  10. Leufkens, Kasper & Peeters, Ronald, 2006. "Alternating-move Hotelling with Demand Shocks," Research Memorandum 039, Maastricht University, Maastricht Research School of Economics of Technology and Organization (METEOR).
  11. Pot Erik & Flesch János & Peeters Ronald & Vermeulen Dries, 2011. "Dynamic Competition with Consumer Inertia," Research Memorandum 016, Maastricht University, Maastricht Research School of Economics of Technology and Organization (METEOR).
  12. David Besanko & Ulrich Doraszelski & Yaroslav Kryukov & Mark Satterthwaite, 2008. "Learning-by-Doing, Organizational Forgetting, and Industry Dynamics," GSIA Working Papers 2009-E22, Carnegie Mellon University, Tepper School of Business.
  13. Ulrich Doraszelski & Mark Satterthwaite, 2007. "Computable Markov-Perfect Industry Dynamics: Existence, Purification, and Multiplicity," Levine's Bibliography 321307000000000912, UCLA Department of Economics.

Lists

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

Statistics

Access and download statistics

Corrections

When requesting a correction, please mention this item's handle: RePEc:unm:umamet:2000004. 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.