Extracted main text — title through conclusion, appendix excluded. This is what our citation measures are computed over, published so the extraction can be checked by eye.
14,325 characters · 9 sections · 16 citation commands
Solving Dynamic Discrete Choice Models: Integrated or Expected Value Function?
Research in, and applications of, Dynamic Discrete Choice Models (DDCMs) has reached some maturity. The history of the research program is well-established, and several surveys exists, see for example rust1994structural and aguirregabiria2010dynamic. In addition to surveys, the most relevant papers are rust1987optimal,john1988maximum,norets2010continuity for information on the expected value function, and aguirregabiria2002swapping, aguirregabiria2010dynamic for the integrated value function formulation. We briefly define relevant objects of interest, as their definitions will be used below. The problem we're trying to solve is
although we will consider the infinite horizon (stationary) dynamic programming formulation
for all purposes below. The choice set, $\mathcal{A}$, is discrete and finite with $J$ elements. The first problem we face is, that the value function depends on the shocks, and that these are typically continuous and unbounded - and unobserved. Then, the usual theorems do not apply.
Below, we will use the the fact that the state $s$ consists of the observed states $x$ and the shocks $\epsilon$, such that $s=(x,\epsilon)$. We will also assume Conditional Independence (CI), that is $(x, \epsilon)$ follows a (controlled) Markov process according to the following transition density
The shocks enter in a specific way
that is they are additive.
The expected value formulation follows john1988maximum and exploits the results the author presented on the the continuity, differentiability, and contraction properties of the expected value function in what aguirregabiria2010dynamic called Rust models. norets2010continuity showed that the results extend beyond the restrictions in the original formulation, but we will focus on Rust models below. The expected value function is defined as
and leads to the following set of expected Bellman equations
It solves two problems of handling $V(s)$ directly: the expected Bellman operator is a contraction even if we have an unbounded (additive) component in $U$, and we do not have to find the solution at each $\epsilon$, only each $x$. If we assume extreme value type I shocks, we can further simplify the expression:
We got rid of the numerical integration over shocks, and the maximization step was replaced with the log-sum-exp calculation. The problem is now almost a trivial exercise in root finding once we realize that Newton's method applied to $\Gamma_{EV}(EV)-EV=0$ will give us convergence to some $\varepsilon$ tolerance level in few iterations.
If we assume that $\mathcal{X}$ is discrete and finite, we get
where $F(a)$ is the conditional transition matrix of dimension $|\mathcal{X}|\times|\mathcal{X}|$, $\log$ and $\exp$ are applied element-wise, and $EV(j)$, $u(j)$ are (stacked over $x$) vectors of length $|\mathcal{X}|$.
We saw that john1988maximum took the joint expectation over $s$ to get rid of two problems: unboundedness of $U$, and $\epsilon$ as an explicit state variable. Let us now consider an way of simplifying the problem. We consider the formulation in aguirregabiria2002swapping. They consider the integrated value function as the object of analysis, defined as
leading to the integrated Bellman equations
which will solve the same problem as $\Gamma$. Again, we get the simplification using extreme value type I shocks that
Since we know that $\Gamma$ is continuous and once differentiable, then so will $\Lambda$ be, as it is simply a $\log$ to the sum of exponentials of the sum of a continuous function (utility) and the EVs. They are also both contraction mappings with the same Lipschitz constant ($\beta$).
Again, discrete and finite $\mathcal{X}$ simplifies matters, and we get
Dimensions are as before, and all terms are stacked over $x$'s.
Since the comparison here is motivated by the solution part of the nested fixed point algorithm in rust1987optimal, we'll focus on two methods: value function iterations and Newton steps for fixed point problems. We consider discrete state spaces, although the lessons apply to the continuous state case as well.
First consider the cost of value function iterations (VFIs). It is the same for $EV$ and $V$. Consider again the expressions from above
as long as we only calculate the log-sum-exp expression in $\Gamma$ once per major VFI iteration, they both require $J$ matrix-vector multiplications, $J$ scalar-vector products, $J$ vector-vector additions, $J$ $\exp$ calls over vectors and one $\log$ call over a vector. This means that really is no reason to choose one over the other.
For Newton's method the computational costs differ. Define the conditional choice probabilities as
where the last line follows from the conditional independence and i.i.d. extreme value type I assumptions from above. Then, stack the Bellman equations
Rearranging, we get
where $I$'s denote the multiplicative identity, and $0$ is the zero element in the Banach spaces where our value functions live. When we say we are using Newton's method, it means applying Newton's method to these equations by use of an inverse function theorem
Looking at the discrete versions of the formul\ae, and calculating the partial derivative state-by-state, we see it is $\beta$ times the controlled transition. That is, for $W$ we get
For the $EV$, the derivative has more elements, and can be calculated as (defining $P$ as the stacked conditional choice probabilities $\{P(j)\}_{j\in\mathcal{A}}$:
where $*^\top$ is the Hadamard product between the vector $P$ and the matrix, but applied down through the rows instead of across the columns as is usually done, such that
for a vector $p$ and matrix $M$. Here we have the problem of using the EV formulation: if we want to use Newton's method (and we really do), then this is now a $J|\mathcal{X}|\times J|\mathcal{X}|$ problem, or $J^2$ as large as the integrated value function problem. Note, that in regenerative models it is possible to use a trick in the style of the original rust1987optimal. However, it does require a little care when specifying the transitions, and indeed there is a mistake in the original application, see the appendix for the details.
The solution of the types of model we've considered here, is typically used in NFXP to estimate parameters in a given model based on some data we observe. This is quite naturally formulated as a constrained maximum likelihood problem as mentioned in RustManual, but NFXP essentially substitutes the constraints into the likelihood function since the model can be efficiently solved using the methods presented here. The MPEC (Mathematical Programming with Equilibrium Constraints) method in SuJudd basically keeps the restrictions on the feasible $EV$'s (the ones that solve $EV=\Gamma(EV)$) in the formulation as equality constraints. They then solve the constrained maximum likelihood problem using an interior point solver. Since each point in the state space has a constraint for each choice, $EV_j(x_k) = \Gamma(EV, j, x_k)$, the considerations mentioned above for Newton's method also applies here. A much more concise specification is available, by simply considering constraints of the form $W(x_k) = \Lambda(W, x_k)$ instead.
We present some numerical evidence to support the claims above, and to assess the practical importance of them. First, convergence is the same in the two approaches. Consider (ref) for a sequence of the $\infty$-norm of the differences between the current and previous iterates.
For a given $k$, we see the similar improvements. What about differences in run-times? In (ref), we see the time to perform a Newton step for the $EV$ formulation relative to the $W$ formulation. We solve Rust's model, and what we call Hitsch's model. The latter is a storable goods demand model. For a similar peer reviewed model see hendel2006measuring. This simpler version is due to a presentation by G\"{u}nter J. Hitsch. \footnote{See the presentation titled "Single Agent Dynamics: Dynamic Discrete Choice" by G\"{u}nter J. Hitsch, The University of Chicago Booth School of Business, 2013.} The $W$ formulation is faster as expected. We also report the time to calculate the Newton step and add it to the existing iterate. The "total" time also includes calculating choice probabilities, the derivative of the Bellman operators, and so on.
rust1987optimal,john1988maximum introduced simplifying assumptions that facilitated solution and estimation of empirically models of dynamic, discrete decision making. The theory and analysis was based on the expected value function. As shown, this is not efficient if Newton's method is applied to solve the system. The same information contained in the $EV(a)$'s can be summarized by the lower dimensional $W$. If successive approximations are used, there is no advantage, but if higher order methods are applied, it is inefficient to use $EV$ over $W$. This also applies to the MPEC approach in SuJudd, which will have more constraints than necessary. The performance gap increase as the number of choices increases, so especially multinomial problem is many discrete choices should be solved with $W$ instead of $EV$.