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. Stengel, B. von & Elzen, A.H. van den & Talman, A.J.J., 1996. "Tracing equilibria in extensive games by complementary pivoting," Discussion Paper, Tilburg University, Center for Economic Research 1996-86, Tilburg University, Center for Economic Research.
  2. Herings, P.J.J., 1994. "A globally and universally stable price adjustment process," Discussion Paper, Tilburg University, Center for Economic Research 1994-52, Tilburg University, Center for Economic Research.
  3. 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, Elsevier, vol. 10(1-2), pages 33-36, June.
  4. P. Jean-Jacques Herings, 2000. "Two simple proofs of the feasibility of the linear tracing procedure," Economic Theory, Springer, Springer, vol. 15(2), pages 485-490.
  5. Bergemann, Dirk & Valimaki, Juuso, 1996. "Learning and Strategic Pricing," Econometrica, Econometric Society, Econometric Society, vol. 64(5), pages 1125-49, September.
  6. R. McKelvey & T. Palfrey, 2010. "Quantal Response Equilibria for Normal Form Games," Levine's Working Paper Archive 510, David K. Levine.
  7. Judd, Kenneth L., 1997. "Computational economics and economic theory: Substitutes or complements?," Journal of Economic Dynamics and Control, Elsevier, Elsevier, vol. 21(6), pages 907-942, June.
  8. Herbert E. Scarf, 1967. "The Approximation of Fixed Points of a Continuous Mapping," Cowles Foundation Discussion Papers, Cowles Foundation for Research in Economics, Yale University 216R, Cowles Foundation for Research in Economics, Yale University.
  9. Stengel, B. von & Elzen, A.H. van den & Talman, A.J.J., 2002. "Computing normal form perfect equilibria for extensive two-person games," Open Access publications from Tilburg University urn:nbn:nl:ui:12-88290, Tilburg University.
  10. Andrew McLennan, 2005. "The Expected Number of Nash Equilibria of a Normal Form Game," Econometrica, Econometric Society, Econometric Society, vol. 73(1), pages 141-174, 01.
  11. Robert Wilson, 2010. "Computing Equilibria of n-person Games," Levine's Working Paper Archive 402, David K. Levine.
  12. Maskin, Eric & Tirole, Jean, 2001. "Markov Perfect Equilibrium: I. Observable Actions," Journal of Economic Theory, Elsevier, Elsevier, vol. 100(2), pages 191-219, October.
  13. 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.
  14. 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.
  15. Hans Haller & Roger Lagunoff, 1999. "Genericity and Markovian Behavior in Stochastic Games," Game Theory and Information, EconWPA 9901003, EconWPA, revised 03 Jun 1999.
  16. Richard Mckelvey & Thomas Palfrey, 1998. "Quantal Response Equilibria for Extensive Form Games," Experimental Economics, Springer, Springer, vol. 1(1), pages 9-41, June.
  17. Pakes, A. & Ericson, R., 1990. "Empirical Implications Of Alternative Models Of Firm Dynamics," Papers, Yale - Economic Growth Center 594, Yale - Economic Growth Center.
  18. 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).
  19. 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, Tilburg University, Center for Economic Research 1998-04, Tilburg University, Center for Economic Research.
  20. McKelvey, Richard D. & McLennan, Andrew, 1996. "Computation of equilibria in finite games," Handbook of Computational Economics, Elsevier, 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:
This item has more than 25 citations. To prevent cluttering this page, these citations are listed on a separate page.

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.