Outline

The authors of this paper do 3 main things:

1. Describe a particular class of Dynamic economic games
2. Describe two algorithms for computing Markov perfect equilibria of those games
3. Give two detailed, non-trivial examples of how to apply the algorithms to games in this class

We won’t have time to touch on the examples, but my goal today is to describe the class of models and explain the key components of the algorithms.

Dynamic Directional Games

The class of dynamic games considered in this paper have the following characteristics

• We consider a dynamic stochastic game G with n players and T periods. T might be ∞.
• Payoffs for each player are given by time separable von-Neumann Morgenstern utility functions.
  • Time t payoffs depend on the state s in time t as well as the vector of actions a_t chosen by all players
• The state for time t + 1 is Markov, conditional on time t state and actions
• We restrict the state space to be finite
• Players perfectly observe the current state as well as past actions
• For each player the discount factor, set of feasible actions given the state, and the Markov transition probabilities are common knowledge
• We will consider Markov perfect equilibria over behavior strategies

The authors further refine this class of games by introducing the concept of directionality in one or more state variables. Specifically, they partition the state vector into two components: D and X. The set D contains the elements of S that can be represented by a directed acyclic graph. X contains all other states.

What does this mean? The set D can be further divided into subgroups and ordered such that once the state moves from subgroup i to subgroup j > i, there is 0 probability of ever returning to subgroup i.

Algorithm 1: State Recursion Algorithm

How does directionality help? It allows them to define the first main algorithm in the paper: the state recursion algorithm.

Suppose that the set D has been divided into M groups, ordered such that the model begins in group 1 and terminates in group M. Then the state recursion algorithm roughly proceeds as follows:

• Starting with subgroup M, iterating down to subgroup 1
  • For each state d ∈ D_M
    • Compute all MPE of the subgame starting from s = d × x, ∀x ∈ X, taking as given optimal strategies already computed in subgroups j > i
    • If multiple such equilibria exist, use some deterministic equilibrium selection rule to choose a unique MPE
• When the recursion terminates, the selected equilibria from each subgame are joined to form the MPE of the original game.

To understand how the State Recursion Algorithm works, consider two simple examples:

1. Let the only directional state variable be time. Then SRA is equivalent to familiar backwards time recursion:
   • start in the terminal period, solve the model for each state in that period
   • Step backwards once in time and for each state in time T − 1, compute the equilibrium, taking as given the optimal cap T strategy.
2. A stylized version of Rubenstein’s 2 bargaining over a pie problem.
   • Suppose that 2 agents are bargaining over how to split a single perfectly divisible pie.
   • Further assume that the size of the pie evolves according to a 4 state Markov chain, where states are ordered in decreasing size of the pie (i.e. state 1 is the full pie) with an upper triangular transition matrix. Specifically, suppose that from state 1, there is non-zero probability of remaining in state 1, or moving to either state 2 or state 3. From state 2, you can remain in state 2 or move to state 4. From state 3 you can stay or move to 4. 4 is absorbing.
   • The state is partitioned into 3 subgroups [(1,), (2,3), (4,)]
   • After moving from 1 to 2 or 3, there is zero probability of ever moving back to 1. Similarly, once the state goes to 4, it has zero probability of ever returning to 1, 2, or 3

From the second example we can see how SRA is a generalization of backwards time recursion: the state can include variables other than time and have a stochastic law of motion between groups.

The SRA algorithm makes 2 assumptions:

1. That we know how to solve for an MPE starting from each element in D
2. That we have a deterministic equilibrium selection rule in mind

The output of the algorithm is a single MPE of the original game.

Algorithm 2: Recursive Lexicographical Search

The second algorithm is called “Recursive Lexicographical Search”. This algorithm relaxes the equilibrium selection rule assumption and in return finds all the MPE of the original game.

The core concept behind this algorithm is that you have an outer loop over all possible equilibrium selection rules, and use the SLA algorithm to compute a particular MPE associated with that ESR.

A key feature of their description of the algorithm is an extremely efficient and clearly explained algorithm for iterating over only the feasible ESRs. The output is that you can compute all the MPE of the original game in linear time (i.e. computational time increases linearly with the number of equilibria). Naively iterating over the possible ESRs would require checking K^N candidates, where K is the maximal number of MPE for any particular stage-game and N is the total number of stage-games. In one example this reduces the number of candidates from 1.7445e26 to 1.