IDEAS home Printed from https://ideas.repec.org/a/oup/restud/v83y2016i2p658-703..html
   My bibliography  Save this article

Recursive Lexicographical Search: Finding All Markov Perfect Equilibria of Finite State Directional Dynamic Games

Author

Listed:
  • Fedor Iskhakov
  • John Rust
  • Bertel Schjerning

Abstract

We define a class of dynamic Markovian games, directional dynamic games (DDG), where directionality is represented by a strategy-independent partial order on the state space. We show that many games are DDGs, yet none of the existing algorithms are guaranteed to find any Markov perfect equilibrium (MPE) of these games, much less all of them. We propose a fast and robust generalization of backward induction we call state recursion that operates on a decomposition of the overall DDG into a finite number of more tractable stage games, which can be solved recursively. We provide conditions under which state recursion finds at least one MPE of the overall DDG and introduce a recursive lexicographic search (RLS) algorithm that systematically and efficiently uses state recursion to find all MPE of the overall game in a finite number of steps. We apply RLS to find all MPE of a dynamic model of Bertrand price competition with cost-reducing investments which we show is a DDG. We provide an exact non-iterative algorithm that finds all MPE of every stage game, and prove there can be only 1, 3, or 5 of them. Using the stage games as building blocks, RLS rapidly finds and enumerates all MPE of the overall game. RLS finds a unique MPE for an alternating move version of the leapfrogging game when technology improves with probability 1, but in other cases, and in any simultaneous move version of the game, it finds a huge multiplicity of MPE that explode exponentially as the number of possible cost states increases.

Suggested Citation

  • Fedor Iskhakov & John Rust & Bertel Schjerning, 2016. "Recursive Lexicographical Search: Finding All Markov Perfect Equilibria of Finite State Directional Dynamic Games," Review of Economic Studies, Oxford University Press, vol. 83(2), pages 658-703.
  • Handle: RePEc:oup:restud:v:83:y:2016:i:2:p:658-703.
    as

    Download full text from publisher

    File URL: http://hdl.handle.net/10.1093/restud/rdv046
    Download Restriction: Access to full text is restricted to subscribers.
    ---><---

    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. Richard Bellman, 1957. "On a Dynamic Programming Approach to the Caterer Problem--I," Management Science, INFORMS, vol. 3(3), pages 270-278, April.
    2. Kenneth L. Judd & Philipp Renner & Karl Schmedders, 2012. "Finding all pure‐strategy equilibria in games with continuous strategies," Quantitative Economics, Econometric Society, vol. 3(2), pages 289-331, July.
    3. 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.
    4. 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.
    5. Fedor Iskhakov & John Rust & Bertel Schjerning, 2018. "The Dynamics Of Bertrand Price Competition With Cost‐Reducing Investments," International Economic Review, Department of Economics, University of Pennsylvania and Osaka University Institute of Social and Economic Research Association, vol. 59(4), pages 1681-1731, November.
    6. Ritzberger, Klaus, 2002. "Foundations of Non-Cooperative Game Theory," OUP Catalogue, Oxford University Press, number 9780199247868.
    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


    Cited by:

    1. Simon Quinn & Tom Gole, 2014. "Committees and Status Quo Bias: Structural Evidence from a Randomized Field Experiment," Economics Series Working Papers 733, University of Oxford, Department of Economics.
    2. Jaap H. Abbring & Jeffrey R. Campbell & Jan Tilly & Nan Yang, 2018. "Very Simple Markov‐Perfect Industry Dynamics: Theory," Econometrica, Econometric Society, vol. 86(2), pages 721-735, March.
    3. Prüfer, Jens & Schottmuller, C., 2017. "Competing with Big Data," Discussion Paper 2017-006, Tilburg University, Tilburg Law and Economic Center.
    4. John Rust, 2014. "The Limits of Inference with Theory: A Review of Wolpin (2013)," Journal of Economic Literature, American Economic Association, vol. 52(3), pages 820-850, September.
    5. Andrew Sweeting & Dun Jia & Shen Hui & Xinlu Yao, 2022. "Dynamic Price Competition, Learning-by-Doing, and Strategic Buyers," American Economic Review, American Economic Association, vol. 112(4), pages 1311-1333, April.
    6. Axel Anderson & Jeremy Rosen & John Rust & Kin-Ping Wong, 2021. "Disequilibrium Play in Tennis," Working Papers gueconwpa~21-21-07, Georgetown University, Department of Economics.
    7. Kenneth Gillingham & Fedor Iskhakov & Anders Munk-Nielsen & John Rust & Bertel Schjerning, 2019. "Equilibrium trade in automobile markets," CESifo Working Paper Series 7650, CESifo.
    8. Doraszelski, Ulrich & Escobar, Juan F., 2019. "Protocol invariance and the timing of decisions in dynamic games," Theoretical Economics, Econometric Society, vol. 14(2), May.
    9. Jos'-Antonio Esp'n-S'nchez & 'lvaro Parra & Yuzhou Wang, 2018. "Equilibrium Uniqueness in Entry Games with Private Information," Cowles Foundation Discussion Papers 2126R, Cowles Foundation for Research in Economics, Yale University, revised May 2021.

    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. Doraszelski, Ulrich & Escobar, Juan F., 2019. "Protocol invariance and the timing of decisions in dynamic games," Theoretical Economics, Econometric Society, vol. 14(2), May.
    2. Cai,Yongyang & Selod,Harris & Steinbuks,Jevgenijs, 2015. "Urbanization and property rights," Policy Research Working Paper Series 7486, The World Bank.
    3. Victor Aguirregabiria & Allan Collard-Wexler & Stephen P. Ryan, 2021. "Dynamic Games in Empirical Industrial Organization," NBER Working Papers 29291, National Bureau of Economic Research, Inc.
    4. Ronald Goettler & Brett Gordon, 2014. "Competition and product innovation in dynamic oligopoly," Quantitative Marketing and Economics (QME), Springer, vol. 12(1), pages 1-42, March.
    5. Govindan, Srihari & Wilson, Robert, 2009. "Global Newton Method for stochastic games," Journal of Economic Theory, Elsevier, vol. 144(1), pages 414-421, January.
    6. Ulrich Doraszelski & Mark Satterthwaite, 2010. "Computable Markov‐perfect industry dynamics," RAND Journal of Economics, RAND Corporation, vol. 41(2), pages 215-243, June.
    7. Ron Borkovsky & Paul Ellickson & Brett Gordon & Victor Aguirregabiria & Pedro Gardete & Paul Grieco & Todd Gureckis & Teck-Hua Ho & Laurent Mathevet & Andrew Sweeting, 2015. "Multiplicity of equilibria and information structures in empirical games: challenges and prospects," Marketing Letters, Springer, vol. 26(2), pages 115-125, June.
    8. David Besanko & Ulrich Doraszelski & Yaroslav Kryukov, 2017. "How Efficient is Dynamic Competition? The Case of Price as Investment," NBER Working Papers 23829, National Bureau of Economic Research, Inc.
    9. Victor Aguirregabiria & Gustavo Vicentini, 2006. "Dynamic Spatial Competition Between Multi-Store Firms," Working Papers tecipa-253, University of Toronto, Department of Economics.
    10. Ulrich Doraszelski & Kenneth L. Judd, 2019. "Dynamic stochastic games with random moves," Quantitative Marketing and Economics (QME), Springer, vol. 17(1), pages 59-79, March.
    11. 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.
    12. Victor Aguirregabiria & Gustavo Vicentini, 2016. "Dynamic Spatial Competition Between Multi-Store Retailers," Journal of Industrial Economics, Wiley Blackwell, vol. 64(4), pages 710-754, December.
    13. Besanko, David & Doraszelski, Ulrich & Kryukov, Yaroslav, 2017. "How Efficient is Dynamic Competition? The Case of Price as Investment," CEPR Discussion Papers 12279, C.E.P.R. Discussion Papers.
    14. Eibelshäuser, Steffen & Poensgen, David, 2019. "Markov Quantal Response Equilibrium and a Homotopy Method for Computing and Selecting Markov Perfect Equilibria of Dynamic Stochastic Games," VfS Annual Conference 2019 (Leipzig): 30 Years after the Fall of the Berlin Wall - Democracy and Market Economy 203603, Verein für Socialpolitik / German Economic Association.
    15. Robert C. Feenstra & Deng-Shing Huang & Gary G. Hamilton, 1997. "Business Groups and Trade in East Asia: Part 1, Networked Equilibria," NBER Working Papers 5886, National Bureau of Economic Research, Inc.
    16. Voelkel, Michael A. & Sachs, Anna-Lena & Thonemann, Ulrich W., 2020. "An aggregation-based approximate dynamic programming approach for the periodic review model with random yield," European Journal of Operational Research, Elsevier, vol. 281(2), pages 286-298.
    17. Fedderke, J.W. & Bogetic, Z., 2009. "Infrastructure and Growth in South Africa: Direct and Indirect Productivity Impacts of 19 Infrastructure Measures," World Development, Elsevier, vol. 37(9), pages 1522-1539, September.
    18. Richard Lowery & Tim Landvoigt, 2016. "Financial Industry Dynamics," 2016 Meeting Papers 1248, Society for Economic Dynamics.
    19. Tan, Madeleine Sui-Lay, 2016. "Policy coordination among the ASEAN-5: A global VAR analysis," Journal of Asian Economics, Elsevier, vol. 44(C), pages 20-40.
    20. Wang, Yafeng & Graham, Brett, 2009. "Generalized Maximum Entropy estimation of discrete sequential move games of perfect information," MPRA Paper 21331, University Library of Munich, Germany.

    More about this item

    JEL classification:

    • D92 - Microeconomics - - Micro-Based Behavioral Economics - - - Intertemporal Firm Choice, Investment, Capacity, and Financing
    • L11 - Industrial Organization - - Market Structure, Firm Strategy, and Market Performance - - - Production, Pricing, and Market Structure; Size Distribution of Firms
    • L13 - Industrial Organization - - Market Structure, Firm Strategy, and Market Performance - - - Oligopoly and Other Imperfect Markets

    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:oup:restud:v:83:y:2016:i:2:p:658-703.. 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: . General contact details of provider: .

    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: Oxford University Press (email available below). General contact details of provider: .

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

    IDEAS is a RePEc service hosted by the Research Division of the Federal Reserve Bank of St. Louis . RePEc uses bibliographic data supplied by the respective publishers.