Rust model of bus engine replacement¶
Description: Model background and formulation. Mileage process. Optimal replacement choice with and without EV taste shocks.
Empirical Model of Harold Zurcher¶
📖 John Rust (1987, Econometrica) “Optimal Replacement of GMC Bus Engines: An Empirical Model of Harold Zurcher”
- Foundational paper in dynamic structural econometrics
- Develops the framework used extensively in many fields today
Ingredients:
- Simple dynamic model: binary discrete state regenerative optimal stopping problem
- Smart solution method: polyalgorithm with fast Newton-Kantorovich iterations
- Coherent econometrics specification: unobserved states ensuring not non-degenerate likelihood
- New maximum likelihood estimator: nested fixed point (NFXP) estimator
- Very real application with actual data collected by a real person named Harold Zurcher
Still very powerful method for both solving and estimating dynamic discrete choice models
📖 Iskhakov, Lee, Rust, Schjerning and Seo (2016, Econometrica) “Comment on “Constrained Optimization Approaches to Estimation of Structural Models””
Components of the dynamic model¶
- State variables — vector of variables that describe all relevant information about the modeled decision process, $ x_t $
- Decision variables — vector of variables describing the choices, $ d_t $
- Instantaneous payoff — utility function, $ u(x_t,d_t) $, with time separable discounted utility
- Motion rules — agent’s beliefs of how state variable evolve through time, conditional on choices, $ x_{t+1} \sim F(x_t,d_t) $
Solution is given by:
- Value function — maximum attainable utility $ V(x_t) $
- Policy function — mapping from state space to action space that returns the optimal choice, $ d^{\star}(x_t) $
Zurcher optimization problem¶
- choice set: $ \{ \text{keep} , \text{replace} \} = \{0,1\} $
Each bus comes in for repair once a month and Zurcher chooses between ordinary maintenance $ (d_{t}=0) $ and overhaul/engine replacement $ (d_{t}=1) $.
- state space: mileage at time t since last engine overhaul $ x_t $
Harold observes many different attributes of the buses which come into the shop, but we focus on the main one for now.
Zurcher’s preferences¶
Instantaneous payoffs are given by the cost function that depends on the choice
$$ u(x_{t},d_t,\theta_1)=\left \{ \begin{array}{ll} -RC-c(0,\theta_1) & \text{if }d_{t}=\text{replace}=1 \\ -c(x_{t},\theta_1) & \text{if }d_{t}=\text{keep}=0 \end{array} \right. $$- $ RC $ = replacement cost
- $ c(x,\theta_1) $ = cost of maintenance with preference parameters $ \theta_1 $
Motion rules¶
- First of all, mileage is continuous. How to deal with the continuous state space?
- Rust discretized the range of travelled miles into $ n=175 $ bins, indexed with $ i $, $ \hat{X} = \{\hat{x}_1,...,\hat{x}_n\} $ with $ \hat{x}_1=0 $
Mileage transition probability: for $ j = 0,...,J $
$$ p(x'|\hat{x}_k, d,\theta_2)= \begin{cases} Pr\{x'=\hat{x}_{k+j}|\theta_2\}= \theta_{2j} \text{ if } d=0 \\ Pr\{x'=\hat{x}_{1+j}|\theta_2\}= \theta_{2j} \text{ if } d=1 \end{cases} $$- Mileage in the next period $ x' $ can move up at most $ J $ grid points
- $ J $ is determined from the observed distribution of mileage
- Effectively, the probabilities of increase of mileage from any existing mileage are the same
Transition matrix for mileage¶
If not replacing ($ d=0) $
$$ \Pi(d=0)_{n x n} = \begin{pmatrix} \theta_{20} & \theta_{21} & \theta_{22} & 0 & \cdot & \cdot & \cdot & 0 \\ 0 & \theta_{20} & \theta_{21} & \theta_{22} & 0 & \cdot & \cdot & 0 \\ 0 & 0 &\theta_{20} & \theta_{21} & \theta_{22} & 0 & \cdot & 0 \\ \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot \\ 0 & \cdot & \cdot & 0 & \theta_{20} & \theta_{21} & \theta_{22} & 0 \\ 0 & \cdot & \cdot & \cdot & 0 & \theta_{20} & \theta_{21} & \theta_{22} \\ 0 & \cdot & \cdot & \cdot & \cdot & 0 & \theta_{20} & 1-\theta_{20} \\ 0 & \cdot & \cdot & \cdot & \cdot & \cdot & 0 & 1 \end{pmatrix} $$Transition matrix for mileage¶
If replacing ($ d=1) $
$$ \Pi(d=1)_{n x n} = \begin{pmatrix} \theta_{20} & \theta_{21} & \theta_{22} & 0 & \cdot & \cdot & \cdot & 0 \\ \theta_{20} & \theta_{21} & \theta_{22} & 0 & \cdot & \cdot & \cdot & 0 \\ \theta_{20} & \theta_{21} & \theta_{22} & 0 & \cdot & \cdot & \cdot & 0 \\ \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot \\ \theta_{20} & \theta_{21} & \theta_{22} & 0 & \cdot & \cdot & \cdot & 0 \\ \theta_{20} & \theta_{21} & \theta_{22} & 0 & \cdot & \cdot & \cdot & 0 \\ \theta_{20} & \theta_{21} & \theta_{22} & 0 & \cdot & \cdot & \cdot & 0 \\ \end{pmatrix} $$Dynamic optimization problem¶
To minimize the discounted expected value of the costs, Zurcher should find such policy function $ f(x_t):X\rightarrow \{\text{keep},\text{replace}\} $ such that $ d_t=f(x_t) $ maximizes
$$ \mathbb{E}\sum_{t=0}^{\infty} \beta^t u(x_t,d_t) \longrightarrow \max $$Value function¶
The function $ V(x_t) $ denotes the maximum attainable value at period t
$$ V(x_t) = max_{\Pi} \mathbb{E} \sum_{j=t}^{\infty} \beta^{j-t} u(x_t,d_t) $$where $ \Pi $ is a space of policy functions $ f(x_t):X\rightarrow \{\text{keep},\text{replace}\} $, and $ d_t = f(x_t) $
Recursive form of the maximization problem (Bellman equation)¶
Using Bellman Principle of Optimality, we can show that the value function $ V(x_t) $ constitutes the solution of the following functional equation
$$ V(x) = \max_{d\in \{\text{keep},\text{replace}\}} \big\{ u(x,d) + \beta \mathbb{E}\big[ V(x')\big|x,d\big] \big\} $$where expectation is taken over the next period values of state $ x' $ given the motion rule of the problem
Bellman equation and Bellman operator¶
$$ V(x) = \max_{d\in \{\text{keep},\text{replace}\}} \big\{ u(x,d) + \beta \mathbb{E}\big[ V(x')\big|x,d\big] \big\} $$can be written as a fixed point equation of the Bellman operator in the functional space
$$ T(V)(x) \equiv \max_{d \in \{\text{keep},\text{replace}\}} \big\{ u(x,d) + \beta \mathbb{E}\big[ V(x') \big|x,d\big] \big\} $$The Bellman equations is then $ V(x) = T(V)(x) $, with the solution given by the fixed point $ T(V) = V $
In the finite horizon models there is last period $ T $
- for $ t=T $ Bellman equation does not have the second (discounted expectation) term
- for $ t=T $ can typically be solved analytically
- value and policy functions are time specific, i.e. differ in time
- can be computed with backward induction with finite number of steps
- all the examples in previous video
In the infinite horizon models there is no last period, so $ T=\infty $
- value and policy functions are time invariant
- constitute the fixed point of the functional Bellman operator
Contraction Mapping Theorem (Banach Fixed Point Theorem)¶
Let $ (S,\rho) $ be a complete metric space with a contraction mapping $ T: S \rightarrow S $.
Then
- $ T $ admits a unique fixed-point $ V^{\star} \in S $, i.e. $ T(V^{\star}) = V^{\star} $.
- $ V^{\star} $ can be found by repeated application of the operator $ T $, i.e. $ T^n(V) \rightarrow V^{\star} $ as $ n\rightarrow \infty $.
We will soon see that Bellman operator in a contraction mapping!
Value function iterations solution algorithm¶
Algorithm:
- Initialize the value function $ V $ with arbitrary values
- Solve Bellman equation to compute $ T(V) $
- Repeat until convergence
- Unique fixed point $ \Leftrightarrow $ unique solution to the Bellman equation
- The fixed point algorithm can start from arbitrary initial guess! VFI algorithm converges globally
- Direct resemblance with backward induction, only have to stop after unspecified number of iterations
Making the model suitable for empirical work¶
- Remember that Zurcher observes many different attributes of the busses that come into the shop
- But we as an econometrician do not!
- Yet, these are likely to be the reason for observing different behavior in same states (for the same observed mileage)
Need to include error terms into the model, denote $ \epsilon $
Three independence assumptions¶
- Error terms are independent across observations due to random sampling
- Error terms come in pairs, one for each decision $ d=0 $ and $ d=1 $, and are independent across choices
- Conditional on $ x $, there is no serial correlation in error terms across time
Updating the Bellman equation¶
$ \varepsilon $ is a new (vector) state variable
$$ V(x,\varepsilon) = \max_{d\in \{0,1\}} \big\{ u(x,\varepsilon_d,d) + \beta \mathbb{E}\big[ V(x',\varepsilon')\big|x,\varepsilon,d\big] \big\} $$$$ V(x,\varepsilon) = \max_{d\in \{0,1\}} \big\{ u(x,\varepsilon_d,d) + \beta \int_{X} \int_{\Omega} V(x',\varepsilon') p(x',\varepsilon'|x,\varepsilon,d) dx'd\varepsilon' \big\} $$where $ \varepsilon_d $ is the component of vector $ \varepsilon \in \mathbb{R}^2 $ which corresponds to $ d $
Rust assumptions¶
(AS) Additive separability in preferences
$$ u(x,\varepsilon_d,d) = u(x,d) + \varepsilon_d, $$(CI) Conditional independence
$$ p(x',\varepsilon'|x,\varepsilon,d) = q(\varepsilon'|x')\cdot \pi(x'|x,d) $$(EV) Extreme value Type I (EV1) distribution of $ \varepsilon $
What Rust assumptions allow:¶
$$ V(x,\varepsilon) = \max_{d\in \{0,1\}} \big\{ u(x,d) + \varepsilon_d + \beta \int_{X} \int_{\Omega} V(x',\varepsilon') \pi(x'|x,d) q(\varepsilon'|x') dx' d\varepsilon' \big\} $$- Separate out the deterministic part of choice specific value function $ v(x,d) $ (SA)
- Compute the expectation by part (CI)
- Use max-stability of EV1 to compute expectation w.r.t. $ \varepsilon' $ (EV)
Expected value function¶
Let $ \mathbb{E}\big[ V(x',\varepsilon')\big|x,d\big] = EV(x,d) $, then
$$ \begin{eqnarray} EV(x,d) &=& \int_{X} \log \big( \exp[v(x',0)] + \exp[v(x',1)] \big) \pi(x'|x,d) dx' \\ v(x,d) &=& u(x,d) + \beta EV(x,d) \end{eqnarray} $$- this is Bellman equation in expected value function space
- when the state space is discrete the integral is, of course, a simple sum over future values
Bellman equation and Bellman operator in expected value function space¶
$$ EV(x,d) = \sum_{X} \log \big( \exp[u(x',0) + \beta EV(x',0)] + \exp[u(x',1) + \beta EV(x',1)] \big) \pi(x'|x,d) $$$$ T^*(EV)(x,d) \equiv \sum_{X} \log \big( \exp[u(x',0) + \beta EV(x',0)] + \exp[u(x',1) + \beta EV(x',1)] \big) \pi(x'|x,d) $$Solution to the Bellman functional equation $ EV(x,d) $ is also a fixed point of $ T^* $ operator, $ T^*(EV)(x,d)=EV(x,d) $
Benefits of Rust’s approach¶
- Bellman operator in expected terms is also a contraction mapping $ \Rightarrow $ VFI work!
- Dimentionality of this fixed point problem is smaller that the one in value function terms (because $ \varepsilon $ is not included)
- It is also numerically easier to work with smooth expected values $ EV(x,d) $ rather than $ V(x,\varepsilon) $
- Later we’ll also see a very nice numerical optimization possibilities as well
Choice probabilities¶
Once the fixed point is found, the optimal choice probability $ P(d|x) $ is given by the Logit structure (assumption EV):
$$ P(d|x) = \frac{\exp[v(x,d)]}{\sum_{d'\in \{0,1\}} \exp[v(x,d')]} $$The choice probability serve as the bases for forming the likelihood function. Will continue with this when talking about structural estimation!
Further learning resources¶
- John Rust https://en.wikipedia.org/wiki/John_Rust
- Optimal Replacement of GMC Bus Engines: An Empirical Model of Harold Zurcher https://www.jstor.org/stable/1911259
- Google scholar citing Rust (1987) https://scholar.google.com/scholar?oi=bibs&hl=en&cites=16527795233338248687