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