TY - JOUR

T1 - Recursive Lexicographical Search

T2 - Finding all Markov Perfect Equilibria of Finite State Directional Dynamic Games

AU - Iskhakov, Fedor

AU - Rust, John

AU - Schjerning, Bertel

N1 - JEL classification: D92, L11, L13

PY - 2016/4/1

Y1 - 2016/4/1

N2 - 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.

AB - 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.

KW - Faculty of Social Sciences

KW - D92

KW - L11

KW - L13

UR - http://bschjerning.com/papers/rls.pdf

U2 - 10.1093/restud/rdv046

DO - 10.1093/restud/rdv046

M3 - Journal article

VL - 83

SP - 658

EP - 703

JO - Review of Economic Studies

JF - Review of Economic Studies

SN - 0034-6527

IS - 2

ER -