Stationary equilibria in stochastic games: structure, selection, and computation
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.)
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.
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.:
- Richard Mckelvey & Thomas Palfrey, 1998. "Quantal Response Equilibria for Extensive Form Games," Experimental Economics, Springer, vol. 1(1), pages 9-41, June.
- 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.
- 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).
- P. Jean-Jacques Herings, 2000.
"Two simple proofs of the feasibility of the linear tracing procedure,"
Springer;Society for the Advancement of Economic Theory (SAET), vol. 15(2), pages 485-490.
- Herings, P.J.J., 1997. "Two Simple Proofs of the Feasibility of the Linear Tracing Procedure," Discussion Paper 1997-77, 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.
- Herings, P.J.J., 1994. "A globally and universally stable price adjustment process," Discussion Paper 1994-52, Tilburg University, Center for Economic Research.
- 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.
- von Stengel, B. & van den Elzen, A.H. & Talman, A.J.J., 2002. "Computing normal form perfect equilibria for extensive two-person games," Other publications TiSEM 9f112346-b587-47f3-ad2e-6, Tilburg University, School of Economics and Management.
- Bergemann, Dirk & Valimaki, Juuso, 1996.
"Learning and Strategic Pricing,"
Econometric Society, vol. 64(5), pages 1125-49, September.
- 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.
- 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.
- 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.
- Ariel Pakes & Richard Ericson, 1989. "Empirical Implications of Alternative Models of Firm Dynamics," NBER Working Papers 2893, National Bureau of Economic Research, Inc.
- Pakes, A. & Ericson, R., 1990. "Empirical Implications Of Alternative Models Of Firm Dynamics," Papers 594, Yale - Economic Growth Center.
- Olley, G Steven & Pakes, Ariel, 1996.
"The Dynamics of Productivity in the Telecommunications Equipment Industry,"
Econometric Society, vol. 64(6), pages 1263-97, November.
- George S Olley & Ariel Pakes, 1992. "The Dynamics Of Productivity In The Telecommunications Equipment Industry," Working Papers 92-2, Center for Economic Studies, U.S. Census Bureau.
- 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.
- Mas-Colell,Andreu, 1990.
"The Theory of General Economic Equilibrium,"
Cambridge University Press, number 9780521388702, November.
- 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.
- Hans Haller & Roger Lagunoff, 1999.
"Genericity and Markovian Behavior in Stochastic Games,"
Game Theory and Information
9901003, EconWPA, revised 03 Jun 1999.
- Hans Haller & Roger Lagunoff, 2000. "Genericity and Markovian Behavior in Stochastic Games," Econometrica, Econometric Society, vol. 68(5), pages 1231-1248, September.
- Robert Wilson, 2010. "Computing Equilibria of n-person Games," Levine's Working Paper Archive 402, David K. Levine.
- 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.
- R. McKelvey & T. Palfrey, 2010. "Quantal Response Equilibria for Normal Form Games," Levine's Working Paper Archive 510, David K. Levine.
- 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.
- von Stengel, B. & van den Elzen, A.H. & Talman, A.J.J., 1996. "Tracing equilibria in extensive games by complementary pivoting," Discussion Paper 1996-86, Tilburg University, Center for Economic Research.
- 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.
- Maskin, Eric & Tirole, Jean, 2001.
"Markov Perfect Equilibrium: I. Observable Actions,"
Journal of Economic Theory,
Elsevier, vol. 100(2), pages 191-219, October.
- Eric Maskin & Jean Tirole, 1997. "Markov Perfect Equilibrium, I: Observable Actions," Harvard Institute of Economic Research Working Papers 1799, Harvard - Institute of Economic Research.
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: (Shamier, Wendy)
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.