Stochastic Algorithms, Symmetric Markov Perfect Equilibrium, and the 'Curse' of Dimensionality
AbstractThis paper introduces a stochastic algorithm for computing symmetric Markov perfect equilibria. The algorithm computes equilibrium policy and value functions, and generates a transition kernel for the (stochastic) evolution of the state of the system. It has two features that together imply that it need not be subject to the curse of dimensionality. First, the integral that determines continuation values is never calculated; rather it is approximated by a simple average of returns from past outcomes of the algorithm, an approximation whose computational burden is not tied to the dimension of the state space. Second, iterations of the algorithm update value and policy functions at a single (rather than at all possible) points in the state space. Random draws from a distribution set by the updated policies determine the location of the next iteration's updates. This selection only repeatedly hits the recurrent class of points, a subset whose cardinality is not directly tied to that of the state space. Numerical results for industrial organization problems show that our algorithm can increase speed and decrease memory requirements by several orders of magnitude.
Download InfoTo our knowledge, this item is not available for download. To find whether it is available, there are three options:
1. Check below under "Related research" whether another version of this item is available online.
2. Check on the provider's web page whether it is in fact available.
3. Perform a search for a similarly titled item that would be available.
Bibliographic InfoArticle provided by Econometric Society in its journal Econometrica.
Volume (Year): 69 (2001)
Issue (Month): 5 (September)
You can help add them by filling out this form.
CitEc Project, subscribe to its RSS feed for this item.
- Ron N. Borkovsky & Ulrich Doraszelski & Yaroslav Kryukov, . "A User''s Guide to Solving Dynamic Stochastic Games Using the Homotopy Method," GSIA Working Papers 2009-E23, Carnegie Mellon University, Tepper School of Business.
- Nguyen, Thang, 2004. "Technological Progress in Races for Product Supremacy," MPRA Paper 235, University Library of Munich, Germany, revised 18 Jul 2006.
- Doraszelski, Ulrich & Satterthwaite, Mark, 2007. "Computable Markov-Perfect Industry Dynamics: Existence, Purification, and Multiplicity," CEPR Discussion Papers 6212, C.E.P.R. Discussion Papers.
- Paolo Pellizzari, 2011. "Optimal trading in a limit order book using linear strategies," Working Papers 2011_16, Department of Economics, University of Venice "Ca' Foscari", revised Sep 2011.
- Ulrich Doraszelski & Kenneth L. Judd, 2005.
"Avoiding the Curse of Dimensionality in Dynamic Stochastic Games,"
NBER Technical Working Papers
0304, National Bureau of Economic Research, Inc.
- Ulrich Doraszelski & Kenneth L. Judd, 2012. "Avoiding the curse of dimensionality in dynamic stochastic games," Quantitative Economics, Econometric Society, vol. 3(1), pages 53-93, 03.
- Ulrich Doraszelski & Kenneth L. Judd, 2005. "Avoiding the Curse of Dimensionality in Dynamic Stochastic Games," Harvard Institute of Economic Research Working Papers 2059, Harvard - Institute of Economic Research.
- Ulrich Doraszelski & Mark Satterthwaite, 2003. "Foundations of Markov-Perfect Industry Dynamics. Existence, Purification, and Multiplicity," Discussion Papers 1383, Northwestern University, Center for Mathematical Studies in Economics and Management Science.
- Wilson, Nathan E., 2012. "Uncertain regulatory timing and market dynamics," International Journal of Industrial Organization, Elsevier, vol. 30(1), pages 102-115.
- Doraszelski, Ulrich & Escobar, Juan, 2010.
"A theory of regular Markov perfect equilibria in dynamic stochastic games: genericity, stability, and purification,"
Econometric Society, vol. 5(3), September.
- 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.
- Juan Escobar & Ulrich Doraszelski, 2008. "A Theory of Regular Markov Perfect Equilibria\\in Dynamic Stochastic Games: Genericity, Stability, and Purification," 2008 Meeting Papers 453, Society for Economic Dynamics.
- David Greenstreet, 2007. "Exploiting Sequential Learning to Estimate Establishment-Level Productivity Dynamics and Decision Rules," Economics Series Working Papers 345, University of Oxford, Department of Economics.
- Darren Filson, 2003. "Dynamic Common Agency, Vertical Integration, and Investment: The Economics of Movie Distribution," Claremont Colleges Working Papers 2003-07, Claremont Colleges.
- Pál, Jenő & Stachurski, John, 2013. "Fitted value function iteration with probability one contractions," Journal of Economic Dynamics and Control, Elsevier, vol. 37(1), pages 251-264.
- Borkovsky, RON N. & Doraszelski, Ulrich & Kryukov, Yaroslav, 2008. "A User's Guide to Solving Dynamic Stochastic Games Using the Homotopy Method," CEPR Discussion Papers 6733, C.E.P.R. Discussion Papers.
- Tchumtchoua, Sylvie & Cotterill, Ronald, 2010. "Optimal Brand and Generic Advertising Policies in a Dynamic Differentiated Product Oligopoly," Research Reports 149978, University of Connecticut, Food Marketing Policy Center.
- 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.
- Allan Collard-Wexler, 2006. "Plant Turnover and Demand Fluctuations in the Ready-Mix Concrete Industry," Working Papers 06-08, Center for Economic Studies, U.S. Census Bureau.
- Ulrich Doraszelski & Mark Satterthwaite, 2007. "Computable Markov-Perfect Industry Dynamics: Existence, Purification, and Multiplicity," Levine's Bibliography 321307000000000912, UCLA Department of Economics.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Wiley-Blackwell Digital Licensing) or (Christopher F. Baum).
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.