Dynamic discrete choice

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.

${\displaystyle {\begin{alignedat}{5}U_{nit}\left(x_{nt},\varepsilon _{nit}\right)&&\;=\;&&u_{nit}&&\;+\;&&\varepsilon _{nit}\\&&\;=\;&&X_{nt}\alpha _{i}&&\;+\;&&\varepsilon _{nit}\end{alignedat}}}$

2. The optimization problem can be written as a Bellman equation

Define by ${\displaystyle V_{nt}(x_{nt})}$ the ex ante value function for individual ${\displaystyle n}$ in period ${\displaystyle t}$ just before ${\displaystyle \varepsilon _{nt}}$ is revealed:

${\displaystyle V_{nt}(x_{nt})=\mathbb {E} \max _{i}\left\{u_{nit}(x_{nt})+\varepsilon _{nit}+\beta \int _{x_{t+1}}V_{nt+1}(x_{nt+1})\,dF\left(x_{t+1}\mid x_{t}\right)\right\}}$

where the expectation operator ${\displaystyle \mathbb {E} }$ is over the ${\displaystyle \varepsilon }$'s, and where ${\displaystyle dF\left(x_{t+1}\mid x_{t}\right)}$ represents the probability distribution over ${\displaystyle x_{t+1}}$ conditional on ${\displaystyle x_{t}}$. The expectation over state transitions is accomplished by taking the integral over this probability distribution.

It is possible to decompose ${\displaystyle V_{nt}(x_{nt})}$ into deterministic and stochastic components:

${\displaystyle V_{nt}(x_{nt})=\mathbb {E} \max _{i}\left\{v_{nit}(x_{nt})+\varepsilon _{nit}\right\}}$

where ${\displaystyle v_{nit}}$ is the value to choosing alternative ${\displaystyle i}$ at time ${\displaystyle t}$ and is written as

${\displaystyle v_{nit}(x_{nt})=u_{nit}\left(x_{nt}\right)+\beta \int _{x_{t+1}}\mathbb {E} \max _{j}\left\{v_{njt+1}(x_{nt+1})+\varepsilon _{njt+1}\right\}\,dF(x_{t+1}\mid x_{t})}$

where now the expectation ${\displaystyle \mathbb {E} }$ is taken over the ${\displaystyle \varepsilon _{njt+1}}$.

3. The optimization problem follows a Markov decision process

The states ${\displaystyle x_{t}}$ follow a Markov chain. That is, attainment of state ${\displaystyle x_{t}}$ depends only on the state ${\displaystyle x_{t-1}}$ and not ${\displaystyle x_{t-2}}$ or any prior state.

The foremost example of a full-solution method is the nested fixed point (NFXP) algorithm developed by John Rust in 1987.[2] The NFXP algorithm is described in great detail in its documentation manual.[3]

A recent work by Che-Lin Su and Kenneth Judd in 2012[4] implements another approach (dismissed as intractable by Rust in 1987), which uses constrained optimization of the likelihood function, a special case of mathematical programming with equilibrium constraints (MPEC). 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[5] 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.[5]

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.[6]

The bus engine replacement model developed in the seminal paper Rust (1987) 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.[4]

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 ${\displaystyle x_{t}}$ denote the odometer reading (mileage) at period ${\displaystyle t}$, ${\displaystyle c(x_{t},\theta )}$ cost of operating the bus which depends on the vector of parameters ${\displaystyle \theta }$, ${\displaystyle RC}$ cost of replacing the engine, and ${\displaystyle \beta }$ the discount factor. Then the per-period utility is given by

${\displaystyle U(x_{t},\xi _{t},d,\theta )={\begin{cases}-c(x_{t},\theta )+\xi _{t,{\text{keep}}},&\\-RC-c(0,\theta )+\xi _{t,{\text{replace}}},&\end{cases}}=u(x_{t},d,\theta )+{\begin{cases}\xi _{t,{\text{keep}}},&{\textrm {if}}\;\;d={\text{keep}},\\\xi _{t,{\text{replace}}},&{\textrm {if}}\;\;d={\text{replace}},\end{cases}}}$

where ${\displaystyle d}$ denotes the decision (keep or replace) and ${\displaystyle \xi _{t,{\text{keep}}}}$ and ${\displaystyle \xi _{t,{\text{replace}}}}$ represent the component of the utility observed by Harold Zurcher, but not John Rust. It is assumed that ${\displaystyle \xi _{t,{\text{keep}}}}$ and ${\displaystyle \xi _{t,{\text{replace}}}}$ are independent and identically distributed with the Type I extreme value distribution, and that ${\displaystyle \xi _{t,\bullet }}$ are independent of ${\displaystyle \xi _{t-1,\bullet }}$ conditional on ${\displaystyle x_{t}}$.

Then the optimal decisions satisfy the Bellman equation

${\displaystyle V(x,\xi ,\theta )=\max _{d={\text{keep}},{\text{replace}}}\left\{u(x,d,\theta )+\xi _{d}+\iint V(x',\xi ',\theta )q(d\xi '\mid x',\theta )p(dx'\mid x,d,\theta )\right\}}$

where ${\displaystyle p(dx'\mid x,d,\theta )}$ and ${\displaystyle q(d\xi '\mid x',\theta )}$ 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 ${\displaystyle q(d\xi '\mid x',\theta )}$, the probability of particular choice ${\displaystyle d}$ is given by

${\displaystyle P(d\mid x,\theta )={\frac {\exp\{u(x,d,\theta )+\beta EV(x,d,\theta )\}}{\sum _{d'\in D(x)}\exp\{u(x,d',\theta )+\beta EV(x,d',\theta )\}}}}$

where ${\displaystyle EV(x,d,\theta )}$ is a unique solution to the functional equation

${\displaystyle EV(x,d,\theta )=\int \left[\log \left(\sum _{d={\text{keep}},{\text{replace}}}\exp\{u(x,d',\theta )+\beta EV(x',d',\theta )\}\right)\right]p(x'\mid x,d,\theta ).}$

It can be shown that the latter functional equation defines a contraction mapping if the state space ${\displaystyle x_{t}}$ is bounded, so there will be a unique solution ${\displaystyle EV(x,d,\theta )}$ for any ${\displaystyle \theta }$, and further the implicit function theorem holds, so ${\displaystyle EV(x,d,\theta )}$ is also a smooth function of ${\displaystyle \theta }$ for each ${\displaystyle (x,d)}$.

The contraction mapping above can be solved numerically for the fixed point ${\displaystyle EV(x,d,\theta )}$ that yields choice probabilities ${\displaystyle P(d\mid x,\theta )}$ for any given value of ${\displaystyle \theta }$. The log-likelihood function can then be formulated as

${\displaystyle L(\theta )=\sum _{i=1}^{N}\sum _{t=1}^{T_{i}}\log(P(d_{it}\mid x_{it},\theta ))+\log(p(x_{it}\mid x_{it-1},d_{it-1},\theta )),}$

where ${\displaystyle x_{i,t}}$ and ${\displaystyle d_{i,t}}$ represent data on state variables (odometer readings) and decision (keep or replace) for ${\displaystyle i=1,\dots ,N}$ individual buses, each in ${\displaystyle t=1,\dots ,T_{i}}$ periods.

The joint algorithm for solving the fixed point problem given a particular value of parameter ${\displaystyle \theta }$ and maximizing the log-likelihood ${\displaystyle L(\theta )}$ with respect to ${\displaystyle \theta }$ was named by John Rust nested fixed point algorithm (NFXP).

Rust's implementation of the nested fixed point algorithm is highly optimized for this problem, using Newton–Kantorovich iterations to calculate ${\displaystyle P(d\mid x,\theta )}$ and quasi-Newton methods, such as the Berndt–Hall–Hall–Hausman algorithm, for likelihood maximization.[5]

In the nested fixed point algorithm, ${\displaystyle P(d\mid x,\theta )}$ is recalculated for each guess of the parameters θ. The MPEC method instead solves the constrained optimization problem:[4]

${\displaystyle {\begin{aligned}\max &\qquad L(\theta )&\\{\text{subject to}}&\qquad EV(x,d,\theta )=\int \left[\log \left(\sum _{d={\text{keep}},{\text{replace}}}\exp\{u(x,d',\theta )+\beta EV(x',d',\theta )\}\right)\right]p(x'\mid x,d,\theta )\end{aligned}}}$

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.[5]

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.[7][8]