Dynamic discrete choice
Dynamic discrete choice (DDC) models, also known as discrete choice models of dynamic programming, model an agent's choices over discrete options that have future implications.
≈ 7 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
Dynamic discrete choice (DDC) 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. (For example, how a prospective college student's enrollment decision would change in response to a tuition increase.)
V\left(x_{n0}\right)=\max_{\left\{d_{nt}\right\}_{t=1}^T} \mathbb{E} \left(\sum_{t^{\prime}=t}^T \sum_{i=1}^J \beta^{t'-t} \left(d_{nt}=i\right)U_{nit} \left(x_{nt}, \varepsilon_{nit}\right)\right), where x_{nt} are state variables, with x_{n0} the agent's initial condition d_{nt} represents n 's decision from among J discrete alternatives \beta \in \left(0,1\right) is the discount factor U_{nit} is the flow utility n receives from choosing alternative i in period t , and depends on both the state x_{nt} and unobserved factors \varepsilon_{nit} T is the time horizon The expectation \mathbb{E}\left(\cdot\right) is taken over both the x_{nt} 's and \varepsilon_{nit} 's in U_{nit} . That is, the agent is uncertain about future transitions in the states, and is also uncertain about future realizations of unobserved factors.
U_{nit}\left(x_{nt},\varepsilon_{nit}\right) &&\; = \;&& u_{nit} &&\; + \;&& \varepsilon_{nit} \\ &&\; = \;&& X_{nt}\alpha_{i} &&\; + \;&& \varepsilon_{nit} \end{alignat} 2. The optimization problem can be written as a Bellman equation Define by V_{nt}(x_{nt}) the ex ante value function for individual n in period t just before \varepsilon_{nt} is revealed: 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 \mathbb{E} is over the \varepsilon 's, and where dF\left(x_{t+1} \mid x_t \right) represents the probability distribution over x_{t+1} conditional on x_{t} .
The expectation over state transitions is accomplished by taking the integral over this probability distribution. It is possible to decompose V_{nt}(x_{nt}) into deterministic and stochastic components: V_{nt}(x_{nt}) = \mathbb{E} \max_i \left\{ v_{nit}(x_{nt}) + \varepsilon_{nit} \right\} where v_{nit} is the value to choosing alternative i at time t and is written as 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 \mathbb{E} is taken over the \varepsilon_{njt+1} .
3. The optimization problem follows a Markov decision process The states x_{t} follow a Markov chain. That is, attainment of state x_{t} depends only on the state x_{t-1} and not x_{t-2} or any prior state.
P_{nit} = \frac{\exp(v_{nit})}{\sum_{j=1}^J \exp(v_{njt})} 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 d denotes the decision (keep or replace) and \xi_{t,\text{keep}} and \xi_{t,\text{replace}} represent the component of the utility observed by Harold Zurcher, but not John Rust. It is assumed that \xi_{t,\text{keep}} and \xi_{t,\text{replace}} are independent and identically distributed with the Type I extreme value distribution, and that \xi_{t,\bullet} are independent of \xi_{t-1,\bullet} conditional on x_t . Then the optimal decisions satisfy the Bellman equation 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 p(dx'\mid x,d,\theta) and 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 q(d\xi'\mid x',\theta) , the probability of particular choice d is given by 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 EV(x,d,\theta) is a unique solution to the functional equation 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 x_t is bounded, so there will be a unique solution EV(x,d,\theta) for any \theta , and further the implicit function theorem holds, so EV(x,d,\theta) is also a smooth function of \theta for each (x,d) . 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 x_{i,t} and d_{i,t} represent data on state variables (odometer readings) and decision (keep or replace) for i=1,\dots,N individual buses, each in t=1,\dots,T_i periods. The joint algorithm for solving the fixed point problem given a particular value of parameter \theta and maximizing the log-likelihood L(\theta) with respect to \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 P(d\mid x,\theta) and quasi-Newton methods, such as the Berndt–Hall–Hall–Hausman algorithm, for likelihood maximization. \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{align} 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.
Text derived from https://en.wikipedia.org/w/index.php?oldid=1334060268 under CC BY-SA 4.0; modifications have been made.