IDEAS home Printed from https://ideas.repec.org/a/ecm/quante/v3y2012i1p53-93.html
   My bibliography  Save this article

Avoiding the curse of dimensionality in dynamic stochastic games

Author

Listed:
  • Ulrich Doraszelski
  • Kenneth L. Judd

Abstract

Discrete-time stochastic games with a finite number of states have been widely ap- plied to study the strategic interactions among forward-looking players in dynamic en- vironments. However, these games suffer from a "curse of dimensionality" since the cost of computing players' expectations over all possible future states increases exponentially in the number of state variables. We explore the alternative of continuous-time stochas- tic games with a finite number of states, and show that continuous time has substantial computational and conceptual advantages. Most important, continuous time avoids the curse of dimensionality, thereby speeding up the computations by orders of magnitude in games with more than a few state variables. Overall, the continuous-time approach opens the way to analyze more complex and realistic stochastic games than currently feasible.
(This abstract was borrowed from another version of this item.)

Suggested Citation

  • 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, March.
    • Handle: RePEc:ecm:quante:v:3:y:2012:i:1:p:53-93
    DOI: QE153
    as

    Download full text from publisher

    File URL: http://hdl.handle.net/10.3982/QE153
    Download Restriction: Access to full text is restricted to subscribers.
    File URL: https://libkey.io/QE153?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to look for a different version below or search for a different version of it.

    Other versions of this item:

    References listed on IDEAS

    as
    1. Ariel Pakes & Michael Ostrovsky & Steven Berry, 2007. "Simple estimators for the parameters of discrete dynamic games (with entry/exit examples)," RAND Journal of Economics, RAND Corporation, vol. 38(2), pages 373-399, June.
    2. David Besanko & Ulrich Doraszelski, 2004. "Capacity Dynamics and Endogenous Asymmetries in Firm Size," RAND Journal of Economics, The RAND Corporation, vol. 35(1), pages 23-49, Spring.
    3. Ariel Pakes & Paul McGuire, 1994. "Computing Markov-Perfect Nash Equilibria: Numerical Implications of a Dynamic Differentiated Product Model," RAND Journal of Economics, The RAND Corporation, vol. 25(4), pages 555-589, Winter.
    4. Chaim Fershtman & Ariel Pakes, 2000. "A Dynamic Oligopoly with Collusion and Price Wars," RAND Journal of Economics, The RAND Corporation, vol. 31(2), pages 207-236, Summer.
    5. Doraszelski, Ulrich & Pakes, Ariel, 2007. "A Framework for Applied Dynamic Analysis in IO," Handbook of Industrial Organization, in: Mark Armstrong & Robert Porter (ed.), Handbook of Industrial Organization, edition 1, volume 3, chapter 30, pages 1887-1966, Elsevier.
    6. Patrick Bajari & C. Lanier Benkard & Jonathan Levin, 2007. "Estimating Dynamic Models of Imperfect Competition," Econometrica, Econometric Society, vol. 75(5), pages 1331-1370, September.
    7. Caplin, Andrew & Nalebuff, Barry, 1991. "Aggregation and Imperfect Competition: On the Existence of Equilibrium," Econometrica, Econometric Society, vol. 59(1), pages 25-59, January.
    8. Kenneth L. Judd, 1998. "Numerical Methods in Economics," MIT Press Books, The MIT Press, edition 1, volume 1, number 0262100711, December.
    9. Ulrich Doraszelski & Sarit Markovich, 2004. "Advertising Dynamics and Competitive Advantage," Computing in Economics and Finance 2004 61, Society for Computational Economics.
    10. Erkan Erdem & James Tybout, 2003. "Trade Policy and Industrial Sector Responses: Using Evolutionary Models to Interpret the Evidence," NBER Working Papers 9947, National Bureau of Economic Research, Inc.
    11. Pakes, Ariel & McGuire, Paul, 2001. "Stochastic Algorithms, Symmetric Markov Perfect Equilibrium, and the 'Curse' of Dimensionality," Econometrica, Econometric Society, vol. 69(5), pages 1261-1281, September.
    12. Ulrich Doraszelski & Sarit Markovich, 2004. "Advertising Dynamics and Competitive Advantage," Econometric Society 2004 North American Summer Meetings 162, Econometric Society.
    13. Patricia Langohr, 2003. "Competitive Convergence and Divergence: Capability and Position Dynamics," Computing in Economics and Finance 2003 229, Society for Computational Economics.
    14. Gowrisankaran, Gautam, 1999. "Efficient representation of state spaces for some dynamic models," Journal of Economic Dynamics and Control, Elsevier, vol. 23(8), pages 1077-1098, August.
    15. Richard Ericson & Ariel Pakes, 1995. "Markov-Perfect Industry Dynamics: A Framework for Empirical Work," The Review of Economic Studies, Review of Economic Studies Ltd, vol. 62(1), pages 53-82.
    16. Ronald L. Goettler & Christine A. Parlour, 2004. "Equilibrium in a Dynamic Limit Order Market," 2004 Meeting Papers 757, Society for Economic Dynamics.
    17. Martin Pesendorfer & Philipp Schmidt-Dengler, 2003. "Identification and Estimation of Dynamic Games," NBER Working Papers 9726, National Bureau of Economic Research, Inc.
    18. Dockner,Engelbert J. & Jorgensen,Steffen & Long,Ngo Van & Sorger,Gerhard, 2000. "Differential Games in Economics and Management Science," Cambridge Books, Cambridge University Press, number 9780521637329.
    19. C. Lanier Benkard, 2004. "A Dynamic Analysis of the Market for Wide-Bodied Commercial Aircraft," The Review of Economic Studies, Review of Economic Studies Ltd, vol. 71(3), pages 581-611.
    20. 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.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Weintraub, Gabriel Y. & Benkard, C. Lanier & Van Roy, Benjamin, 2007. "Computational Methods for Oblivious Equilibrium," Research Papers 1969, Stanford University, Graduate School of Business.
    2. Weintraub, Gabriel Y. & Benkard, C. Lanier & Van Roy, Benjamin, 2007. "Markov Perfect Industry Dynamics with Many Firms," Research Papers 1919r, Stanford University, Graduate School of Business.
    3. C. Lanier Benkard & Benjamin Van Roy & Gabriel Y. Weintraub, 2005. "Markov perfect industry dynamics with many firms," Working Paper Series 2005-23, Federal Reserve Bank of San Francisco.
    4. Gabriel Weintraub & C. Lanier Benkard & Ben Van Roy, 2005. "Markov Perfect Industry Dynamics with Many Firms," NBER Working Papers 11900, National Bureau of Economic Research, Inc.
    5. Ulrich Doraszelski & Mark Satterthwaite, 2010. "Computable Markov‐perfect industry dynamics," RAND Journal of Economics, RAND Corporation, vol. 41(2), pages 215-243, June.
    6. C. Lanier Benkard & Przemyslaw Jeziorski & Gabriel Y. Weintraub, 2013. "Oblivious Equilibrium for Concentrated Industries," NBER Working Papers 19307, National Bureau of Economic Research, Inc.
    7. Doraszelski, Ulrich & Kryukov, Yaroslav & Borkovsky, Ron N., 2008. "A User's Guide to Solving Dynamic Stochastic Games Using the Homotopy Method," CEPR Discussion Papers 6733, C.E.P.R. Discussion Papers.
    8. Ulrich Doraszelski & Mark Satterthwaite, 2007. "Computable Markov-Perfect Industry Dynamics: Existence, Purification, and Multiplicity," Levine's Bibliography 321307000000000912, UCLA Department of Economics.
    9. Gabriel Y. Weintraub & C. Lanier Benkard & Benjamin Van Roy, 2010. "Computational Methods for Oblivious Equilibrium," Operations Research, INFORMS, vol. 58(4-part-2), pages 1247-1265, August.
    10. , & ,, 2010. "A theory of regular Markov perfect equilibria in dynamic stochastic games: genericity, stability, and purification," Theoretical Economics, Econometric Society, vol. 5(3), September.
    11. Ron N. Borkovsky & Ulrich Doraszelski & Yaroslav Kryukov, "undated". "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.
    12. Doraszelski, Ulrich & Satterthwaite, Mark, 2007. "Computable Markov-Perfect Industry Dynamics: Existence, Purification, and Multiplicity," CEPR Discussion Papers 6212, C.E.P.R. Discussion Papers.
    13. Vivek Farias & Bar Ifrach & Gabriel Weintraub, 2012. "A Framework for Dynamic Oligopoly in Concentrated Industries," 2012 Meeting Papers 505, Society for Economic Dynamics.
    14. C. Lanier Benkard & Przemyslaw Jeziorski & Gabriel Y. Weintraub, 2015. "Oblivious equilibrium for concentrated industries," RAND Journal of Economics, RAND Corporation, vol. 46(4), pages 671-708, October.
    15. Ron Borkovsky & Ulrich Doraszelski & Yaroslav Kryukov, 2012. "A dynamic quality ladder model with entry and exit: Exploring the equilibrium correspondence using the homotopy method," Quantitative Marketing and Economics (QME), Springer, vol. 10(2), pages 197-229, June.
    16. Joao Macieira, 2010. "Oblivious Equilibrium in Dynamic Discrete Games," 2010 Meeting Papers 680, Society for Economic Dynamics.
    17. Aamir Rafique Hashmi & Johannes Van Biesebroeck, 2016. "The Relationship between Market Structure and Innovation in Industry Equilibrium: A Case Study of the Global Automobile Industry," The Review of Economics and Statistics, MIT Press, vol. 98(1), pages 192-208, March.
    18. Victor Aguirregabiria & Gustavo Vicentini, 2006. "Dynamic Spatial Competition Between Multi-Store Firms," Working Papers tecipa-253, University of Toronto, Department of Economics.
    19. Ulrich Doraszelski & Sarit Markovich, 2004. "Advertising Dynamics and Competitive Advantage," Computing in Economics and Finance 2004 61, Society for Computational Economics.
    20. Linli Xu & Jorge M. Silva-Risso & Kenneth C. Wilbur, 2018. "Dynamic Quality Ladder Model Predictions in Nonrandom Holdout Samples," Management Science, INFORMS, vol. 64(7), pages 3187-3207, July.

    More about this item

    JEL classification:

    • C63 - Mathematical and Quantitative Methods - - Mathematical Methods; Programming Models; Mathematical and Simulation Modeling - - - Computational Techniques

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:ecm:quante:v:3:y:2012:i:1:p:53-93. See general information about how to correct material in RePEc.

    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 CitEc recognized a bibliographic reference but did not link an item in RePEc 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 RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Wiley Content Delivery (email available below). General contact details of provider: https://edirc.repec.org/data/essssea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.