IDEAS home Printed from https://ideas.repec.org/p/kud/kuiedp/1416.html
   My bibliography  Save this paper

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

Author

Listed:
  • Fedor Iskhakov

    (University New South Wales)

  • John Rust

    (Georgetown University)

  • Bertel Schjerning

    (Department of Economics, Copenhagen University)

Abstract

We define a class of dynamic Markovian games that we call directional dynamic games (DDG) in which directionality is represented by a partial order on the state space. We propose a fast and robust state recursion algorithm that can find a Markov perfect equilibrium (MPE) via backward induction on the state space of the game. When there are multiple equilibria, this algorithm relies on an equilibrium selection rule (ESR) to pick a particular MPE.We propose a recursive lexicographic search (RLS) algorithm that systematically and efficiently cycles through all feasible ESRs and prove that the RLS algorithm finds all MPE of the overall game. We apply the algorithms to find all MPE of a dynamic duopoly model of Bertrand price competition and cost reducing investments which we show is a DDG. Even with coarse discretization of the state space we find hundreds of millions of MPE in this game.

Suggested Citation

  • Fedor Iskhakov & John Rust & Bertel Schjerning, 2014. "Recursive Lexicographical Search: Finding all Markov Perfect Equilibria of Finite State Directional Dynamic Games," Discussion Papers 14-16, University of Copenhagen. Department of Economics.
  • Handle: RePEc:kud:kuiedp:1416
    as

    Download full text from publisher

    File URL: http://www.econ.ku.dk/english/research/publications/wp/dp_2014/1416.pdf
    Download Restriction: no
    ---><---

    Other versions of this item:

    References listed on IDEAS

    as
    1. Ritzberger, Klaus, 2002. "Foundations of Non-Cooperative Game Theory," OUP Catalogue, Oxford University Press, number 9780199247868.
    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. 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. 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.
    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. Richard Bellman, 1957. "On a Dynamic Programming Approach to the Caterer Problem--I," Management Science, INFORMS, vol. 3(3), pages 270-278, April.
    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. 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.
    7. Ulrich Doraszelski & Mark Satterthwaite, 2010. "Computable Markov‐perfect industry dynamics," RAND Journal of Economics, RAND Corporation, vol. 41(2), pages 215-243, June.
    8. Victor Aguirregabiria & Gustavo Vicentini, 2006. "Dynamic Spatial Competition Between Multi-Store Firms," Working Papers tecipa-253, University of Toronto, Department of Economics.
    9. 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.
    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. Pierre Bernhard & Marc Deschamps, 2017. "Kalman on dynamics and contro, Linear System Theory, Optimal Control, and Filter," Working Papers 2017-10, CRESE.
    17. Jones, Randall E. & Cacho, Oscar J., 2000. "A Dynamic Optimisation Model of Weed Control," 2000 Conference (44th), January 23-25, 2000, Sydney, Australia 123685, Australian Agricultural and Resource Economics Society.
    18. 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.
    19. Pam Norton & Ravi Phatarfod, 2008. "Optimal Strategies In One-Day Cricket," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 25(04), pages 495-511.
    20. 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.

    More about this item

    Keywords

    Dynamic games; directional dynamic games; Markov-perfect equilibrium; subgame perfect equilibrium; multiple equilibria; partial orders; directed acyclic graphs; d-subgames; generalized stage games; state recursion; recursive lexicographic search algorithm; variable-base arithmetic; successor function;
    All these keywords.

    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

    NEP fields

    This paper has been announced in the following NEP Reports:

    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:kud:kuiedp:1416. 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: https://edirc.repec.org/data/okokudk.html .

    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: Thomas Hoffmann (email available below). General contact details of provider: https://edirc.repec.org/data/okokudk.html .

    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.