Advanced Search
MyIDEAS: Login to save this article or follow this journal

Stationary equilibria in stochastic games: structure, selection, and computation

Contents:

Author Info

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

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.

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

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://www.sciencedirect.com/science/article/B6WJ3-4B84WW9-2/2/e52ced09b70d9e990846d688f59849d3
Download Restriction: Full text for ScienceDirect subscribers only

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 Info

Article provided by Elsevier in its journal Journal of Economic Theory.

Volume (Year): 118 (2004)
Issue (Month): 1 (September)
Pages: 32-60

as in new window
Handle: RePEc:eee:jetheo:v:118:y:2004:i:1:p:32-60

Contact details of provider:
Web page: http://www.elsevier.com/locate/inca/622869

Related research

Keywords:

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. Pakes, Ariel & Ericson, Richard, 1998. "Empirical Implications of Alternative Models of Firm Dynamics," Journal of Economic Theory, Elsevier, vol. 79(1), pages 1-45, March.
  2. 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.
  3. 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.
  4. 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.
  5. Richard Mckelvey & Thomas Palfrey, 1998. "Quantal Response Equilibria for Extensive Form Games," Experimental Economics, Springer, vol. 1(1), pages 9-41, June.
  6. Maskin, Eric & Tirole, Jean, 2001. "Markov Perfect Equilibrium: I. Observable Actions," Journal of Economic Theory, Elsevier, vol. 100(2), pages 191-219, October.
  7. 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.
  8. Andrew McLennan, 2005. "The Expected Number of Nash Equilibria of a Normal Form Game," Econometrica, Econometric Society, vol. 73(1), pages 141-174, 01.
  9. Stengel, B. von & Elzen, A.H. van den & Talman, A.J.J., 1997. "Computing normal form perfect equilibria for extensive two-person games," Research Memorandum 752, Tilburg University, Faculty of Economics and Business Administration.
  10. 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.
  11. 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.
  12. Bergemann, Dirk & Valimaki, Juuso, 1996. "Learning and Strategic Pricing," Econometrica, Econometric Society, vol. 64(5), pages 1125-49, September.
  13. Hans Haller & Roger Lagunoff, 2000. "Genericity and Markovian Behavior in Stochastic Games," Econometrica, Econometric Society, vol. 68(5), pages 1231-1248, September.
  14. 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.
  15. R. McKelvey & T. Palfrey, 2010. "Quantal Response Equilibria for Normal Form Games," Levine's Working Paper Archive 510, David K. Levine.
  16. 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.
  17. 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.
  18. Robert Wilson, 2010. "Computing Equilibria of n-person Games," Levine's Working Paper Archive 402, David K. Levine.
  19. 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.
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. Haller, Hans & Lagunoff, Roger, 2010. "Markov Perfect equilibria in repeated asynchronous choice games," Journal of Mathematical Economics, Elsevier, vol. 46(6), pages 1103-1114, November.
  2. 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).
  3. Duggan, John & Kalandrakis, Tasos, 2012. "Dynamic legislative policy making," Journal of Economic Theory, Elsevier, vol. 147(5), pages 1653-1688.
  4. 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).
  5. Arthur Zillante, 2005. "Spaced Out Monopolies: Theory and Empirics of Alternating Product Releases," Industrial Organization 0505008, EconWPA.
  6. 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.
  7. Ulrich Doraszelski & Mark Satterthwaite, 2007. "Computable Markov-Perfect Industry Dynamics: Existence, Purification, and Multiplicity," Levine's Bibliography 321307000000000912, UCLA Department of Economics.
  8. Besanko, David & Doraszelski, Ulrich & Kryukov, Yaroslav & Satterthwaite, Mark, 2007. "Learning-by-Doing, Organizational Forgetting and Industry Dynamics," CEPR Discussion Papers 6160, C.E.P.R. Discussion Papers.
  9. Doraszelski, Ulrich & Escobar, Juan, 2010. "A theory of regular Markov perfect equilibria in dynamic stochastic games: genericity, stability, and purification," Theoretical Economics, Econometric Society, vol. 5(3), September.
  10. Doraszelski, Ulrich & Satterthwaite, Mark, 2007. "Computable Markov-Perfect Industry Dynamics: Existence, Purification, and Multiplicity," CEPR Discussion Papers 6212, C.E.P.R. Discussion Papers.
  11. 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.
  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. Frank H. Page, Jr., Myrna H. Wooders, 2009. "Endogenous Network Dynamics," Caepr Working Papers 2009-002, Center for Applied Economics and Policy Research, Economics Department, Indiana University Bloomington.

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:eee:jetheo:v:118:y:2004:i:1:p:32-60. 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: (Zhang, Lei).

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.