IDEAS home Printed from
   My bibliography  Save this paper

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


  • Fedor Iskhakov

    (University New South Wales)

  • John Rust

    (Georgetown University)

  • Bertel Schjerning

    (Department of Economics, Copenhagen University)


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

    Download full text from publisher

    File URL:
    Download Restriction: no

    Other versions of this item:

    References listed on IDEAS

    1. 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.
    2. 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.
    3. Richard Bellman, 1957. "On a Dynamic Programming Approach to the Caterer Problem--I," Management Science, INFORMS, vol. 3(3), pages 270-278, April.
    4. Ritzberger, Klaus, 2002. "Foundations of Non-Cooperative Game Theory," OUP Catalogue, Oxford University Press, number 9780199247868.
    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.
    Full references (including those not matched with items on IDEAS)


    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.

    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. Doraszelski, Ulrich & Escobar, Juan F., 2019. "Protocol invariance and the timing of decisions in dynamic games," Theoretical Economics, Econometric Society, vol. 14(2), May.
    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 P. Rust & Bertel Schjerning, 2019. "Equilibrium Trade in Automobile Markets," NBER Working Papers 25840, National Bureau of Economic Research, Inc.

    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. Pierre Bernhard & Marc Deschamps, 2017. "Kalman on dynamics and contro, Linear System Theory, Optimal Control, and Filter," Working Papers 2017-10, CRESE.
    4. 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.
    5. 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.
    6. 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.
    7. Aghayi, Nazila & Maleki, Bentolhoda, 2016. "Efficiency measurement of DMUs with undesirable outputs under uncertainty based on the directional distance function: Application on bank industry," Energy, Elsevier, vol. 112(C), pages 376-387.
    8. 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.
    9. 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.
    10. D. W. K. Yeung, 2008. "Dynamically Consistent Solution For A Pollution Management Game In Collaborative Abatement With Uncertain Future Payoffs," International Game Theory Review (IGTR), World Scientific Publishing Co. Pte. Ltd., vol. 10(04), pages 517-538.
    11. Onyeka Osuji, 2011. "Fluidity of Regulation-CSR Nexus: The Multinational Corporate Corruption Example," Journal of Business Ethics, Springer, vol. 103(1), pages 31-57, September.
    12. Hanafi, Said & Freville, Arnaud, 1998. "An efficient tabu search approach for the 0-1 multidimensional knapsack problem," European Journal of Operational Research, Elsevier, vol. 106(2-3), pages 659-675, April.
    13. Schön, Cornelia & König, Eva, 2018. "A stochastic dynamic programming approach for delay management of a single train line," European Journal of Operational Research, Elsevier, vol. 271(2), pages 501-518.
    14. Eric D. Gould, 2008. "Marriage and Career: The Dynamic Decisions of Young Men," Journal of Human Capital, University of Chicago Press, vol. 2(4), pages 337-378.
    15. Renato Cordeiro Amorim, 2016. "A Survey on Feature Weighting Based K-Means Algorithms," Journal of Classification, Springer;The Classification Society, vol. 33(2), pages 210-242, July.
    16. Dmitri Blueschke & Ivan Savin, 2015. "No such thing like perfect hammer: comparing different objective function specifications for optimal control," Jena Economic Research Papers 2015-005, Friedrich-Schiller-University Jena.
    17. Sieniutycz, Stanislaw, 2015. "Synthesizing modeling of power generation and power limits in energy systems," Energy, Elsevier, vol. 84(C), pages 255-266.
    18. Miller, Marcus & Papi, Laura, 1997. "The 'laissez faire' bias of managed floating," Journal of International Money and Finance, Elsevier, vol. 16(6), pages 989-1000, December.
    19. Changming Ji & Chuangang Li & Boquan Wang & Minghao Liu & Liping Wang, 2017. "Multi-Stage Dynamic Programming Method for Short-Term Cascade Reservoirs Optimal Operation with Flow Attenuation," Water Resources Management: An International Journal, Published for the European Water Resources Association (EWRA), Springer;European Water Resources Association (EWRA), vol. 31(14), pages 4571-4586, November.
    20. Ghassan, Hassan B. & Al-Jefri, Essam H., 2015. "الحساب الجاري في المدى البعيد عبر نموذج داخلي الزمن [The Current Account in the Long Run through the Intertemporal Model]," MPRA Paper 66527, University Library of Munich, Germany.

    More about this item


    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:


    Access and download statistics


    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: (Thomas Hoffmann). 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 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.

    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.