Dynamic discrete choice


Dynamic discrete choice models, also known as discrete choice models of dynamic programming, model an agent's choices over discrete options that have future implications. Rather than assuming observed choices are the result of static utility maximization, observed choices in DDC models are assumed to result from an agent's maximization of the present value of utility, generalizing the utility theory upon which discrete choice models are based.
The goal of DDC methods is to estimate the structural parameters of the agent's decision process. Once these parameters are known, the researcher can then use the estimates to simulate how the agent would behave in a counterfactual state of the world.

Mathematical representation

Agent 's maximization problem can be written mathematically as follows:
where
It is standard to impose the following simplifying assumptions and notation of the dynamic decision problem:
;1. Flow utility is additively separable and linear in parameters
The flow utility can be written as an additive sum, consisting of deterministic and stochastic elements. The deterministic component can be written as a linear function of the structural parameters.
;2. The optimization problem can be written as a Bellman equation
Define by the ex ante value function for individual in period just before is revealed:
where the expectation operator is over the 's, and where represents the probability distribution over conditional on. The expectation over state transitions is accomplished by taking the integral over this probability distribution.
It is possible to decompose into deterministic and stochastic components:
where is the value to choosing alternative at time and is written as
where now the expectation is taken over the.
;3. The optimization problem follows a Markov decision process
The states follow a Markov chain. That is, attainment of state depends only on the state and not or any prior state.

Conditional value functions and choice probabilities

The value function in the previous section is called the conditional value function, because it is the value function conditional on choosing alternative in period. Writing the conditional value function in this way is useful in constructing formulas for the choice probabilities.
To write down the choice probabilities, the researcher must make an assumption about the distribution of the 's. As in static discrete choice models, this distribution can be assumed to be iid Type I extreme value, generalized extreme value, multinomial probit, or mixed logit.
For the case where is multinomial logit, the formulas for the choice probabilities would be:

Estimation

Estimation of dynamic discrete choice models is particularly challenging, due to the fact that the researcher must solve the backwards recursion problem for each guess of the structural parameters.
The most common methods used to estimate the structural parameters are maximum likelihood estimation and method of simulated moments.
Aside from estimation methods, there are also solution methods. Different solution methods can be employed due to complexity of the problem. These can be divided into full-solution methods and non-solution methods.

Full-solution methods

The foremost example of a full-solution method is the nested fixed point algorithm developed by John Rust in 1987.
The NFXP algorithm is described in great detail in its documentation manual.
A recent work by Che-Lin Su and Kenneth Judd in 2012 implements another approach, which uses constrained optimization of the likelihood function, a special case of mathematical programming with equilibrium constraints.
Specifically, the likelihood function is maximized subject to the constraints imposed by the model, and expressed in terms of the additional variables that describe the model's structure. This approach requires powerful optimization software such as Artelys Knitro because of the high dimensionality of the optimization problem.
Once it is solved, both the structural parameters that maximize the likelihood, and the solution of the model are found.
In the later article Rust and coauthors show that the speed advantage of MPEC compared to NFXP is not significant. Yet, because the computations required by MPEC do not rely on the structure of the model, its implementation is much less labor intensive.
Despite numerous contenders, the NFXP maximum likelihood estimator remains the leading estimation method
for Markov decision models.

Non-solution methods

An alternative to full-solution methods is non-solution methods. In this case, the researcher can estimate the structural parameters without having to fully solve the backwards recursion problem for each parameter guess. Non-solution methods are typically faster while requiring more assumptions, but the additional assumptions are in many cases realistic.
The leading non-solution method is conditional choice probabilities, developed by V. Joseph Hotz and Robert A. Miller.

Examples

Bus engine replacement model

The bus engine replacement model developed in the seminal paper is one of the first dynamic stochastic models of discrete choice estimated using real data, and continues to serve as classical example of the problems of this type.
The model is a simple regenerative optimal stopping stochastic dynamic problem faced by the decision maker, Harold Zurcher, superintendent of maintenance at the Madison, Wisconsin Metropolitan Bus Company. For every bus in operation in each time period Harold Zurcher has to decide whether to replace the engine and bear the associated replacement cost, or to continue operating the bus at an ever raising cost of operation, which includes insurance and the cost of lost ridership in the case of a breakdown.
Let denote the odometer reading at period, cost of operating the bus which depends on the vector of parameters, cost of replacing the engine, and the discount factor. Then the per-period utility is given by
where denotes the decision and and represent the component of the utility observed by Harold Zurcher, but not John Rust. It is assumed that and are independent and identically distributed with the Type I extreme value distribution, and that are independent of conditional on.
Then the optimal decisions satisfy the Bellman equation
where and are respectively transition densities for the observed and unobserved states variables. Time indices in the Bellman equation are dropped because the model is formulated in the infinite horizon settings, the unknown optimal policy is stationary, i.e. independent of time.
Given the distributional assumption on, the probability of particular choice is given by
where is a unique solution to the functional equation
It can be shown that the latter functional equation defines a contraction mapping if the state space is bounded, so there will be a unique solution for any, and further the implicit function theorem holds, so is also a smooth function of for each.

Estimation with nested fixed point algorithm

The contraction mapping above can be solved numerically for the fixed point that yields choice probabilities for any given value of. The log-likelihood function can then be formulated as
where and represent data on state variables and
decision for individual buses, each in periods.
The joint algorithm for solving the fixed point problem given a particular value of parameter and maximizing the log-likelihood with respect to was named by John Rust nested fixed point algorithm.
Rust's implementation of the nested fixed point algorithm is highly optimized for this problem, using Newton–Kantorovich iterations to calculate and quasi-Newton methods, such as the Berndt–Hall–Hall–Hausman algorithm, for likelihood maximization.

Estimation with MPEC

In the nested fixed point algorithm, is recalculated for each guess of the parameters. The MPEC method instead solves the constrained optimization problem:
This method is faster to compute than non-optimized implementations of the nested fixed point algorithm, and takes about as long as highly optimized implementations.

Estimation with non-solution methods

The conditional choice probabilities method of Hotz and Miller can be applied in this setting. Hotz, Miller, Sanders, and Smith proposed a computationally simpler version of the method, and tested it on a study of the bus engine replacement problem. The method works by estimating conditional choice probabilities using simulation, then backing out the implied differences in value functions.