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. 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. Fedor Iskhakov & John Rust & Bertel Schjerning, 2013. "The Dynamics of Bertrand Price Competition with Cost-Reducing Investments," Discussion Papers 13-05, University of Copenhagen. Department of Economics.
    5. 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. Abbring, Jaap & Campbell, J.R. & Tilly, J. & Yang, N., 2017. "Very Simple Markov-Perfect Industry Dynamics : Theory," Discussion Paper 2017-020, Tilburg University, Center for Economic Research.
    3. Doraszelski, Ulrich & Escobar, Juan, 2016. "Protocol Invariance and the Timing of Decisions in Dynamic Games," CEPR Discussion Papers 11447, C.E.P.R. Discussion Papers.
    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. Prüfer, Jens & Schottmuller, C., 2017. "Competing with Big Data," Discussion Paper 2017-006, Tilburg University, Tilburg Law and Economic Center.

    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;

    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: (Thomas Hoffmann). General contact details of provider: http://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 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.