16 Dynamic Discrete Choice Models
In the previous chapter we studied individuals making a single discrete choice. But many of the discrete choices that economists care about are made repeatedly, and today’s choice changes the circumstances under which tomorrow’s choice will be made. A firm that enters a market today does not have to pay an entry cost to stay in the market tomorrow. A woman who works today accumulates experience that raises her wages tomorrow. A welfare recipient who uses a month of benefits today has one less month of eligibility available under a time limit. In each case, a forward-looking agent must weigh the payoff today against the consequences for the future.
This chapter introduces the general dynamic discrete choice (DDC) framework, building on the foundational work of Rust (1987). We will cover three things:
- The framework and its key assumptions, which deliver a tractable, recursive characterization of choice probabilities.
- How to solve the model and estimate it by maximum likelihood using the nested fixed point (NFXP) algorithm.
- Identification: what can (and cannot) be learned about payoffs from data on choices and states.
The chapters that follow put the framework to work in three prototype models: a single-agent entry model from industrial organization, a model of female labor force participation with human capital accumulation, and a model of labor supply and program participation under welfare time limits. Each chapter shows how to solve, simulate, and estimate the model, and uses it to answer a counterfactual question.
16.1 The Framework
Time is discrete and indexed by \(t\). In each period, an agent observes a vector of state variables \(x_{t}\in\mathcal{X}=\{1,\ldots,K\}\) and a vector of payoff shocks \(\varepsilon_{t}=(\varepsilon_{0t},\varepsilon_{1t},\ldots,\varepsilon_{Jt})\), and then chooses an option \(d_{t}\in\{0,1,\ldots,J\}\). The flow payoff from choosing \(j\) is:
\[ u_{j}(x_{t}) + \varepsilon_{jt}. \]
The agent chooses a sequence of decisions to maximize the expected discounted sum of payoffs:
\[ \mathbb{E}\left[\sum_{t=0}^{\infty}\beta^{t}\left(u_{d_{t}}(x_{t}) + \varepsilon_{d_{t}t}\right)\Big| x_{0},\varepsilon_{0}\right]. \]
As always, the econometrician observes the state \(x_{t}\) and the choice \(d_{t}\) but not the shocks \(\varepsilon_{t}\). As in the static case, these unobserved shocks are what turn deterministic decisions by the agent into choice probabilities from the perspective of the econometrician.
Without further restrictions, this problem is not very tractable. The standard assumptions, due to Rust (1987), are:
Definition 16.1 (Rust’s Assumptions)
- Additive separability (AS): unobserved payoff shocks enter additively, as written above.
- Conditional independence (CI): the state evolves according to \[ \mathbb{P}(x_{t+1},\varepsilon_{t+1}|x_{t},\varepsilon_{t},d_{t}) = f_{d_{t}}(x_{t+1}|x_{t})g(\varepsilon_{t+1}) \] so that (i) the shocks \(\varepsilon\) are iid over time and do not directly affect the transition of the observed states; and (ii) the observed states are a controlled Markov process.
- Extreme value shocks: each \(\varepsilon_{jt}\) is an iid draw from the Type I Extreme Value distribution with location zero and scale \(\sigma\).
Assumption 3 is primarily a matter of convenience, and we will see how it can be relaxed. Assumption 2 is the one that does the heavy lifting: it rules out persistent unobservables. All of the serial dependence in choices that is not driven by the shocks is attributed to the observed states \(x_{t}\). We will return to this restriction at length in the chapter on unobserved heterogeneity.
16.1.1 The Integrated Value Function
Let \(W(x,\varepsilon)\) be the value of arriving in a period with state \((x,\varepsilon)\). By the principle of optimality:
\[ W(x,\varepsilon) = \max_{j}\left\{u_{j}(x) + \varepsilon_{j} + \beta\mathbb{E}\left[W(x',\varepsilon')|x,j\right]\right\}. \]
At first glance, this is a functional equation over a \((J+1)\)-dimensional continuous shock in addition to \(x\). Assumption CI allows us to integrate the shocks out. Define the integrated (or ex-ante) value function:
\[ V(x) = \int W(x,\varepsilon)dG(\varepsilon) \]
and the conditional value function (also called the choice-specific value function):
\[ v_{j}(x) = u_{j}(x) + \beta\sum_{x'}V(x')f_{j}(x'|x).\]
Then integrating both sides of the Bellman equation gives a recursion over \(V\) alone:
\[ V(x) = \int\max_{j}\left\{v_{j}(x) + \varepsilon_{j}\right\}dG(\varepsilon). \]
The agent’s optimal choice is to pick the option with the highest value of \(v_{j}(x)+\varepsilon_{j}\). Hence, conditional on the conditional value functions \(v_{j}(x)\), the agent is solving a static random utility problem with representative utilities \(v_{j}(x)\). Everything we learned in the previous chapter applies. In particular, when the shocks are extreme value we can use the results for the GEV family (with \(G(y)=\sum_{j}y_{j}\)) to get:
\[ V(x) = \sigma\gamma + \sigma\log\left(\sum_{j=0}^{J}\exp(v_{j}(x)/\sigma)\right) \]
where \(\gamma\) is the Euler-Mascheroni constant, and the conditional choice probabilities (CCPs) are:
\[ p_{j}(x) = \frac{\exp(v_{j}(x)/\sigma)}{\sum_{k}\exp(v_{k}(x)/\sigma)}. \]
Notice that nothing in this derivation required extreme value shocks until the very last step. If the shocks were instead generated by a nested logit (as in Example 15.2), we would simply replace the “log-sum” formula for \(V\) with the log of the GEV generating function (plus \(\sigma\gamma\)), and the logit formula for choice probabilities with the nested logit formula. The Williams-Daly-Zachary theorem (Theorem 15.1) tells us that, for any distribution of shocks, the CCPs are the gradient of the function that maps conditional values to the integrated value function.
16.1.2 Solving the Model
It is useful to write the model in vector notation. Let \(\mathbf{V}\) be a \(K\times 1\) vector that stacks \(V(x)\) over the state space, and similarly for \(\mathbf{u}_{j}\) and \(\mathbf{v}_{j}\). Let \(\mathbf{F}_{j}\) be the \(K\times K\) transition matrix with \((x,x')\) entry \(f_{j}(x'|x)\). Then the integrated value function is the solution to:
\[ \mathbf{V} = \Gamma(\mathbf{V}) \equiv \sigma\gamma + \sigma\log\left(\sum_{j}\exp\left(\left[\mathbf{u}_{j} + \beta\mathbf{F}_{j}\mathbf{V}\right]/\sigma\right)\right). \]
When the horizon is finite (say the agent lives for \(T\) periods) then the conditional value functions and choice probabilities depend on time and we can simply solve the model by backward induction: given a terminal value \(\mathbf{V}_{T+1}\) (often zero), we calculate \(\mathbf{V}_{t} = \Gamma(\mathbf{V}_{t+1})\) for \(t=T,T-1,\ldots,1\). This is what we did for the savings model.
When the horizon is infinite, we need to find a fixed point. Fortunately, it is straightforward to verify that \(\Gamma\) satisfies Blackwell’s sufficient conditions: it is monotone (\(\mathbf{V}\geq\mathbf{V}'\Rightarrow\Gamma(\mathbf{V})\geq\Gamma(\mathbf{V}')\)) and it discounts (\(\Gamma(\mathbf{V}+c) = \Gamma(\mathbf{V})+\beta c\) for any constant \(c\)). Hence \(\Gamma\) is a contraction mapping with modulus \(\beta\), there is a unique fixed point, and value function iteration (\(\mathbf{V}^{n+1} = \Gamma(\mathbf{V}^{n})\)) converges to it from any starting point.
The downside of value function iteration is that the error only shrinks by a factor of \(\beta\) in each iteration, which can be painfully slow when \(\beta\) is close to one. A much faster alternative is to apply Newton’s method to the equation \(\mathbf{V}-\Gamma(\mathbf{V})=\mathbf{0}\). Conveniently, the Jacobian of \(\Gamma\) has a simple form:
\[ \nabla_{\mathbf{V}}\Gamma(\mathbf{V}) = \beta\sum_{j}\text{diag}(\mathbf{p}_{j})\mathbf{F}_{j} \equiv \beta\mathbf{F}^{\mathbf{p}}\]
where \(\mathbf{p}_{j}\) are the choice probabilities implied by \(\mathbf{V}\) and \(\mathbf{F}^{\mathbf{p}}\) is therefore the transition matrix over states that is induced by those choice probabilities. Each Newton iteration is:
\[ \mathbf{V}^{n+1} = \mathbf{V}^{n} - \left(\mathbf{I} - \beta\mathbf{F}^{\mathbf{p}^{n}}\right)^{-1}\left(\mathbf{V}^{n} - \Gamma(\mathbf{V}^{n})\right).\]
This is closely related to policy iteration, and it converges quadratically once we are close enough to the solution. Rust (1987) recommended a “poly-algorithm” that begins with a few contraction iterations and then switches to Newton. In the small problems we will consider here, Newton’s method from a starting guess of zero works just fine.
16.2 Estimation by Nested Fixed Point
Suppose we observe a panel of \(N\) agents over \(T\) periods, recording the state and the choice of each: \((X_{nt},D_{nt})_{n=1,t=1}^{N,T}\). Let \(\theta\) collect the payoff parameters (and \(\beta\) and \(\sigma\), if they are to be estimated), and let \(\theta_{f}\) collect the parameters of the transition process \(f\) for the observed states. Under Rust’s assumptions, the likelihood of the data is:
\[ \mathcal{L}(\theta,\theta_{f}) = \prod_{n=1}^{N}\prod_{t=1}^{T}p_{D_{nt}}(X_{nt};\theta,\theta_{f})\times\prod_{n=1}^{N}\prod_{t=1}^{T-1}f_{D_{nt}}(X_{n,t+1}|X_{nt};\theta_{f}). \]
Notice that the likelihood factors into the likelihood of choices and the likelihood of state transitions. The conditional independence assumption is what makes this possible: since the shocks \(\varepsilon\) do not affect transitions, the transitions are informative about \(\theta_{f}\) alone. However, the choice probabilities depend on both sets of parameters since agents take the transitions into account when making decisions. Rust (1987) proposed a three-step approach:
- Estimate \(\theta_{f}\) by maximizing the likelihood of transitions alone. When the states are discrete, a simple option is a frequency estimator, which is the nonparametric maximum likelihood estimator.
- Taking \(\hat{\theta}_{f}\) as given, estimate \(\theta\) by maximizing the partial likelihood of choices.
- Optionally, use \((\hat{\theta},\hat{\theta}_{f})\) as starting values and maximize the full likelihood. This delivers efficient estimates and correct standard errors in one step.
Step 2 is computationally intensive, because every time we evaluate the likelihood at a new guess of \(\theta\) we must solve the model. This “inner loop” (solving the model) nested inside an “outer loop” (searching over parameters) is what gives the nested fixed point algorithm its name. In finite-horizon models the inner loop is backward induction rather than a fixed point, but the logic is identical.
Since the solution of the model is a finite sequence of differentiable operations, we can use automatic differentiation to get exact gradients and Hessians of the log-likelihood, through the model solution. This lets us use Newton’s method in the outer loop and calculate standard errors with the Hessian (Theorem 13.5). We will see this in action in each of the prototype models that follow.
When some of the states are only partially observed, the transition process may be informative about \(\theta\) directly. For example, in the labor force participation model wages are a function of experience, and the wage equation can be estimated in a first step using data on workers. The same logic of first-step estimation applies.
The computational burden of the nested fixed point has motivated two families of alternatives. The first, which we will study in a later chapter, uses estimates of the choice probabilities to avoid solving the model altogether. The second, proposed by Su and Judd (2012), reformulates estimation as a constrained optimization problem (MPEC: mathematical programming with equilibrium constraints) in which the value function is treated as an additional set of parameters to be chosen, subject to the constraint that the Bellman equation holds. Modern constrained optimizers can then exploit the sparsity of this problem.
16.3 Identification
Now let’s consider what can be learned from data on choices and states. Since the transitions \(f_{j}(x'|x)\) are directly observed, we take them as known. The data also directly reveal the choice probabilities \(p_{j}(x)\). The question is: what do these choice probabilities tell us about payoffs \(u_{j}(x)\), the discount factor \(\beta\), and the distribution of shocks \(G\)?
16.3.1 The Inversion
The key step, due to Hotz and Miller (1993), is that the mapping from conditional values to choice probabilities can be inverted. In the logit case, this inversion is especially simple:
\[ v_{j}(x) - v_{0}(x) = \sigma\log\left(\frac{p_{j}(x)}{p_{0}(x)}\right). \]
Furthermore, the integrated value function can be written in terms of the value of any single choice plus a correction that depends only on the probability of that choice:
\[ V(x) = \sigma\gamma + \sigma\log\left(\sum_{k}\exp(v_{k}(x)/\sigma)\right) = v_{0}(x) + \sigma\gamma - \sigma\log p_{0}(x). \]
Let’s normalize \(\sigma=1\) and suppose that we know \(\beta\) and \(u_{0}(x)\). Then, since \(v_{0}(x) = u_{0}(x) + \beta\sum_{x'}V(x')f_{0}(x'|x)\), the expression above can be written in vector form as:
\[ \mathbf{V} = \mathbf{u}_{0} + \beta\mathbf{F}_{0}\mathbf{V} + \gamma - \log\mathbf{p}_{0}\quad\Rightarrow\quad \mathbf{V} = \left(\mathbf{I}-\beta\mathbf{F}_{0}\right)^{-1}\left(\mathbf{u}_{0}+\gamma-\log\mathbf{p}_{0}\right). \]
So \(\mathbf{V}\) is identified! With \(\mathbf{V}\) in hand, each \(\mathbf{v}_{j}\) is identified from the inversion, and we can back out flow payoffs as:
\[ \mathbf{u}_{j} = \mathbf{v}_{j} - \beta\mathbf{F}_{j}\mathbf{V}.\]
This constructive argument is the basis for the following result.
Theorem 16.1 (Identification of Flow Payoffs (Magnac and Thesmar 2002)) Suppose that Rust’s assumptions (AS) and (CI) hold. If the distribution of shocks \(G\), the discount factor \(\beta\), and the payoffs of one reference choice \(u_{0}(x)\) are known, then the flow payoffs \(u_{j}(x)\) for all \(j\) and \(x\) are identified from the choice probabilities and transitions.
Conversely, for any choice of \((G,\beta,u_{0})\) there exist flow payoffs \(u_{j}\) that rationalize the observed choice probabilities. Hence, without further restrictions, the model is not identified.
This is a sobering result. It says that the data cannot tell us the discount factor, and that the normalization of one choice’s payoffs (which is innocuous in static models) is a substantive assumption in dynamic models. Here is a more general way to see the problem. Take any function \(c(x)\) and define a new set of payoffs:
\[ \tilde{u}_{j}(x) = u_{j}(x) + c(x) - \beta\sum_{x'}c(x')f_{j}(x'|x). \]
You will show in Exercise 16.1 that \(\tilde{u}\) and \(u\) imply exactly the same choice probabilities. Intuitively, the agent receives an extra payoff of \(c(x)\) today but “pays it back” in expectation tomorrow, so these payoffs do not change any trade-offs between choices. In a static model (\(\beta=0\)), this just tells us that we can add any function of the state to all payoffs, so we normalize the payoff of one choice to zero. In a dynamic model, the “pay back” term \(\beta\mathbb{E}[c(x')|x,j]\) depends on the choice. This means that normalizing \(u_{0}(x)=0\) is not innocuous: it restricts how payoffs of other choices can depend on the state.
In each of our prototype models we will see a concrete example of this problem. In the entry model, for example, the entry cost and the scrap value from exiting cannot be separately identified (Example 17.4).
16.3.2 Identifying the Discount Factor
Theorem 16.1 tells us that \(\beta\) cannot be identified without additional restrictions. What kind of restriction helps? The answer is an exclusion restriction: a variable that shifts the agent’s expectations about the future without affecting payoffs today (Magnac and Thesmar 2002; Abbring and Daljord 2020).
To see how this works, consider a simple example where the horizon is finite and there are two periods. Suppose payoffs do not depend on time, normalize \(\sigma=1\) and \(u_{0}(x)=0\), and let \(p_{jt}(x)\) be the choice probabilities in period \(t\). In the final period there is no future, so \(v_{j2}(x)=u_{j}(x)\) and:
\[ u_{1}(x) = \log\left(\frac{p_{12}(x)}{p_{02}(x)}\right),\qquad V_{2}(x) = \gamma - \log p_{02}(x). \]
Both objects are identified from period 2 choice probabilities. In the first period:
\[ \log\left(\frac{p_{11}(x)}{p_{01}(x)}\right) = u_{1}(x) + \beta\sum_{x'}V_{2}(x')\left[f_{1}(x'|x) - f_{0}(x'|x)\right].\]
Substituting in the expressions from the second period gives:
\[ \beta = \frac{\log\left(p_{11}(x)/p_{01}(x)\right) - \log\left(p_{12}(x)/p_{02}(x)\right)}{\sum_{x'}\left[\gamma - \log p_{02}(x')\right]\left[f_{1}(x'|x) - f_{0}(x'|x)\right]} \]
which is identified as long as the denominator is not zero. Notice what is doing the work here: time changes the continuation value of each choice but is excluded from flow payoffs. The difference in choice behavior between the two periods (holding the state fixed) reveals how much the agent cares about the future.
In stationary, infinite-horizon models, we need a variable that plays the same role. Suppose the state can be partitioned as \(x = (\tilde{x},z)\), where \(z\) affects the transitions but is excluded from flow payoffs:
\[ u_{j}(\tilde{x},z) - u_{0}(\tilde{x},z) = u_{j}(\tilde{x}) - u_{0}(\tilde{x}). \]
Then, comparing two values \(z\) and \(z'\) with the same \(\tilde{x}\), the inversion gives:
\[ \log\left(\frac{p_{j}(\tilde{x},z)}{p_{0}(\tilde{x},z)}\right) - \log\left(\frac{p_{j}(\tilde{x},z')}{p_{0}(\tilde{x},z')}\right) = \beta\left[\Delta_{j}(\tilde{x},z;\beta) - \Delta_{j}(\tilde{x},z';\beta)\right] \]
where \(\Delta_{j}(x;\beta) = \sum_{x'}V(x')\left[f_{j}(x'|x)-f_{0}(x'|x)\right]\) and \(\mathbf{V}\) is identified (as a function of \(\beta\)) using the formula above. This gives us an equation in a single unknown, \(\beta\), for each \((\tilde{x},z,z')\).
16.4 Further Reading
Rust (1994) and Aguirregabiria and Mira (2010) are excellent surveys of the econometrics of dynamic discrete choice models. Keane and Wolpin (1997) is a classic application to the career decisions of young men that introduced several practical methods for solving and estimating models with large state spaces.