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

Fedor Iskhakov, John Rust () and Bertel Schjerning

No 14-16, Discussion Papers from University of Copenhagen. Department of Economics

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.

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 (search for similar items in EconPapers)
JEL-codes: D92 L11 L13 (search for similar items in EconPapers)
Pages: 62 pages
Date: 2014-06-01
New Economics Papers: this item is included in nep-cmp, nep-com, nep-gth and nep-mic
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (7)

Downloads: (external link)
http://www.econ.ku.dk/english/research/publications/wp/dp_2014/1416.pdf (application/pdf)

Related works:
Journal Article: Recursive Lexicographical Search: Finding All Markov Perfect Equilibria of Finite State Directional Dynamic Games (2016)
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:kud:kuiedp:1416

Access Statistics for this paper

More papers in Discussion Papers from University of Copenhagen. Department of Economics Oester Farimagsgade 5, Building 26, DK-1353 Copenhagen K., Denmark. Contact information at EDIRC.
Bibliographic data for series maintained by Thomas Hoffmann ().