10. Deterministic Dynamic Programming

10.1.1 The Bellman equation

$$V(x)\equiv\max_{y\in\Gamma(x)}\{F(x,y)+\beta V(y)\}$$ where \(x\) is the current period state variable, \(y\) is the next period state variable, \(F(x,y)\) is the period return function and \(\beta<1\) is the discounting factor (\(\beta<1\) is crucial for the Contraction Mapping Theorem to apply). Note that the Bellman equation is a functional equation, and its solution is a function \(V(x)\) that satisfies the Bellman equation.

10.1.2 Assumptions and Properties of \(V\)

Let \(C(X)\) be the space of bounded, continuous functions with the sup norm \(\|f\|=\sup_{x\in X}|f(x)|\). Consider the metric space \((C(X),\rho)\) such that for \(f,g\in C(X)\), \(\rho(f,g)=\|f-g\|=\sup_{x\in X}|f(x)-g(x)|\). For \(\tilde v\in C(X)\), define the Bellman operator \(T\) in the metric space \((C(X),\rho)\) as $$(T\tilde v)(x)\equiv\max_{y\in\Gamma(x)}\{F(x,y)+\beta\tilde v(y)\}$$

\(V\) is well-defined (existence, uniqueness). For the Contraction Mapping Theorem to apply, we need that (1) \(T\tilde v\) is bounded; (2) \(T\tilde v\) is continuous; (3) \(T\) is a contraction. - \(T\tilde v\) is bounded because \(F\) is assumed to be bounded and \(\tilde v\) is assumed to be bounded. - \(T\tilde v\) is continuous because \(F\) and \(\tilde v\) are continuous and \(\Gamma\) is compact valued and continuous as a correspondence; then the Theorem of Maximum implies that \(T\tilde v\) is continuous. - \(T\) is a contraction because it satisfies Blackwell's sufficient conditions (monotonicity and discounting): - monotonicity: for \(\forall x\), suppose \(v_1(x)\le v_2(x)\), then $$F(x,y)+\beta v_1(y)\le F(x,y)+\beta v_2(y)\Rightarrow(Tv_1)(x)=\max_{y\in\Gamma(x)}\{F(x,y)+\beta v_1(y)\}\le\max_{y\in\Gamma(x)}\{F(x,y)+\beta v_2(y)\}=(Tv_2)(x)$$ Thus the monotonicity of operator \(T\) is satisfied. - discounting: since we assumed \(\beta\in(0,1)\), for \(a\ge0\), $$T(\tilde v+a)(x)=\max_{y\in\Gamma(x)}\{F(x,y)+\beta(\tilde v(y)+a)\}=\max_{y\in\Gamma(x)}\{F(x,y)+\beta\tilde v(y)\}+\beta a=(T\tilde v)(x)+\beta a$$ which satisfies \(T(\tilde v+a)(x)\le(T\tilde v)(x)+\beta a\), i.e. the discounting condition. - Then the Contraction Mapping Theorem applies: \(T\) has a unique fixed point \(V\) such that \(TV=V\). The principle of optimality holds, i.e. \(V=V^\star\), where \(V^\star\) is the solution to the sequence problem.

Properties of \(V\) and \(g\). - (1) Monotonicity of \(V\): Requirement 1: \(\Gamma(x)\) is monotone (i.e. \(x'\ge x\Rightarrow\Gamma(x)\subseteq\Gamma(x')\)). Requirement 2: \(F(x,y)\) weakly increasing in \(x\). If \(F(x,y)\) is strictly increasing in \(x\), then \(V\) is strictly increasing. - (2) Concavity of \(V\): Requirement 1: \(F(x,y)\) weakly concave in \((x,y)\). If \(F\) is strictly concave in \(x\), then \(V\) is strictly concave. Requirement 2: \(\Gamma(x)\) is convex as a correspondence. - (3) Differentiability of \(V\) at \(\hat x\): A space of differentiable functions is not a closed set to the operator \(T\) because the operator \(T\) can push a sequence of differentiable functions infinitesimally close to a function in the limit with a kink. So we need a condition to make sure the kinked shape does not appear in the limit, i.e. for a neighborhood \(D\) around \(\hat x\), there is a concave and differentiable function \(W:D\to\mathbb R\) with \(W(\hat x)=V(\hat x)\) and \(W(x)\le V(x)\) for \(\forall x\in D\). Such a condition can be attained if Requirement 5 is satisfied: - Requirement 1: \(X\subseteq\mathbb R^n\) is a convex set. Requirement 2: \(V\) is concave. Requirement 3: \(\hat x\in\text{int}(X)\). Requirement 4: \(g(\hat x)\in\text{int}(\Gamma(\hat x))\). Requirement 5: \(F\) is differentiable at \(\hat x\). - when this requirement is satisfied, we can construct \(W(x)=F(x,g(\hat x))+\beta V(g(\hat x))\), which satisfies \(W(\hat x)=V(\hat x)\) and \(W(x)\le V(x)\), and \(W(x)\) is differentiable at \(\hat x\) and concave in \(x\). - Differentiability of \(V\) does not give differentiability of \(g\). Differentiability of \(g\) requires twice differentiability of \(V\), and twice differentiability of \(F(x,y)\) in \(x\) and \(y\): $$V(x)=F(x,g(x))+V(g(x))\Rightarrow V'(x)=F_1(x,g(x))\ [\because\text{envelope theorem}]\Rightarrow V''(x)=F_{11}(x,g(x))+F_{12}(x,g(x))g'(x)\Rightarrow g'(x)=\frac{V''(x)-F_{11}(x,g(x))}{F_{12}(x,g(x))}$$ But once differentiability of \(V\) only requires once differentiability of \(F(x,y)\) in \(x\). - (4) Property of \(g\): If \(V(x)\) is strictly concave in \(x\), then the optimal policy function \(g(x)\) is a single valued function (not a correspondence) and continuous in \(x\). If both \(V(x)\) and \(F(x,y)\) are (strictly) concave, then \(g(x)\) is (strictly) increasing in \(x\).

10.2.1 Set-up

Period constraint: \(c+h'\le Ah^\alpha\) for \(A>0\), \(\alpha\in(0,1)\), where \(c\) is current period consumption, \(h'\) is next period human capital, \(h\) is current period human capital, and \(A\) is technology. Preference: \(U(\{c_t\}_{t=1}^\infty)=\sum_{t=0}^\infty\beta^t u(c_t)\) for \(\beta\in(0,1)\), where \(u\) is continuously differentiable, strictly increasing, strictly concave, and \(u'(0)=+\infty\).

10.2.2 Important questions regarding this model

What is a useful state space? The state variable is human capital \(h\), and the state space is \([0,h_{max}]\) where \(h_{max}\) satisfies \(0+h_{max}=Ah_{max}^\alpha\), i.e. \(h_{max}=A^{1/(1-\alpha)}\). So the state space can be rewritten as \(\left[0,A^{1/(1-\alpha)}\right]\).

What is the Bellman equation? $$V(h)=\max_{y\in[0,Ah^\alpha]}\{u(Ah^\alpha-y)+\beta V(y)\}$$ with \(h\in\left[0,A^{1/(1-\alpha)}\right]\).

Explain the following properties of \(V\) (see rigorous proofs in Chapter 4 of Recursive Methods in Economic Dynamics): - well-defined (exists), unique and continuous: Since the state space is compact (bounded and closed), \(c_t\) is bounded for \(\forall t\), so \(u(c_t)\) is bounded for \(\forall t\). We also know that \(\beta<1\), so \(V\) is bounded. We can use the Contraction Mapping Theorem to prove uniqueness. We can use the fact that the set \(\Gamma(h)=[0,Ah^\alpha]\) varies continuously with \(h\) to prove continuity of \(V\). - strictly increasing: \(\Gamma(h)=[0,Ah^\alpha]\) is monotone as a correspondence, \(h'>h\Rightarrow\Gamma(h')\supseteq\Gamma(h)\). Since \(u\) is strictly increasing, a larger \(h\) means a larger \(u(Ah^\alpha-y)\) for any \(y\). Since \(\Gamma(h)\) is monotone, a larger \(h\) means more choices of \(y\). Combined together, the larger period return function for any \(y\) and more choices of \(y\) guarantees a strictly larger \(V(h)\). - strictly concave: Define \(h_\theta=\theta h_1+(1-\theta)h_2\) for \(\theta\in(0,1)\). Since \(Ah^\alpha\) is strictly concave, \(\theta Ah_1^\alpha+(1-\theta)Ah_2^\alphaonce differentiable: Define \(w(h)=u\left(Ah^\alpha-g(\hat h)\right)+\beta V\left(g(\hat h)\right)\). Since \(u\) is once differentiable at point \(\hat h\), \(w(h)\) is once differentiable at \(\hat h\), which implies the uniqueness of the supporting hyper-plane \(l\) of \(w(h)\). Note that \(w(h)\le V(h)\) and the inequality is strict unless \(h=\hat h\). So \(V(h)\) also has a unique hyper-plane at \(h=\hat h\), which rules out the kink shape of \(V(h)\). Therefore \(V(h)\) is once differentiable where the solution \(y^\star=g(h)\) is interior, i.e. \(y^\star\in(0,Ah^\alpha)\). And we know that \(y^\star=g(h)\) cannot be a corner solution since \(y^\star\ne Ah^\alpha\) (since \(u'(0)=+\infty\)) and \(y^\star\ne0\) (since \(y^\star=0\) makes future production impossible). So \(V(h)\) is once differentiable. - Figure (paraphrased): the \(V(h)\) curve has a supporting hyper-plane \(l\) at \(\hat h\); the constructed \(w(h)\) is tangent to \(V(h)\) at \(\hat h\) and below \(V(h)\) elsewhere, so the supporting hyper-plane of \(V(h)\) at \(\hat h\) is unique and there is no kink.

Write the first order condition (f.o.c.) and the envelop condition (EC). - The f.o.c. w.r.t. \(y\): \(u'(Ah^\alpha-y^\star)=\beta V'(y^\star)\). - The EC w.r.t. \(h\): \(V'(h)=A\alpha h^{\alpha-1}u'(Ah^\alpha-y^\star)\).

Figure (the f.o.c. policy function graph, paraphrased): the horizontal axis is next-period human capital \(y^\star\). Draw \(\beta V'(y^\star)\) (an increasing curve) and \(u'(Ah^\alpha-y^\star)\) (a curve increasing in \(y^\star\)); their intersection pins down \(y^\star\). Consider \(\hat h>h\): since \(u'\) is decreasing in \(h\), \(u'(A\hat h^\alpha-y^\star)\) is below \(u'(Ah^\alpha-y^\star)\) for any \(y^\star\). From the graph, \(\hat y^\star>y^\star\), i.e. \(g(\hat h)>g(h)\), so the policy function is increasing in \(h\); also \(u'(A\hat h^\alpha-\hat y^\star)c\), which means \(c(h)=Ah^\alpha-g(h)\) has positive slope, i.e. \(g'(h)\in(0,A\alpha h^{\alpha-1})\).

Write the Euler Equation. $$u'(Ah^\alpha-g(h))=\beta V'(g(h))=\beta A\alpha g(h)^{\alpha-1}u'(Ag(h)^\alpha-g(g(h)))$$ or $$u'(Ah_t^\alpha-h_{t+1})=\beta A\alpha h_{t+1}^{\alpha-1}u'(Ah_{t+1}^\alpha-h_{t+2})$$

Characterize the steady state \(h_{ss}\). $$u'(Ah_{ss}^\alpha-h_{ss})=\beta A\alpha h_{ss}^{\alpha-1}u'(Ah_{ss}^\alpha-h_{ss})\Rightarrow1=\beta A\alpha h_{ss}^{\alpha-1}\Rightarrow h_{ss}=(\beta A\alpha)^{\frac{1}{1-\alpha}}$$ Note that \(h_{ss}\) is increasing in \(\beta\), \(A\), and \(\alpha\).

10.2.3 Summary for the important facts

1. The Bellman Equation (BE): \(V(h)=\max_{y\in[0,Ah^\alpha]}\{u(f(h)-y)+\beta V(y)\}\) with \(h\in\left[0,A^{1/(1-\alpha)}\right]\) and \(f(h)=Ah^\alpha\).
2. There exists a unique, bounded, continuous function \(V\) satisfying the above BE, and \(V=V^\star\) where \(V^\star\) is generated by the sequence problem.
3. \(V\) is strictly increasing and strictly concave.
4. The optimal policy function \(y^\star=g(h)\) is single-valued, continuous, strictly increasing with \(g'(h)\in(0,A\alpha h^{\alpha-1})\).
5. The f.o.c. that characterizes \(y^\star\): \(u'(f(h)-y^\star)=\beta V'(y^\star)\).
6. The Inada condition on \(u\) (i.e. \(u'(0)=+\infty\)) guarantees an interior solution of \(y^\star\).
7. The Envelop Condition (EC): \(V'(h)=f'(h)u'(f(h)-y^\star)\).
8. The Euler Equation (EE): \(u'(f(h_t)-h_{t+1})=\beta f'(h_{t+1})u'(f(h_{t+1})-h_{t+2})\).
9. The steady state \(h_{ss}=(\beta A\alpha)^{1/(1-\alpha)}\), increasing in \(\beta\), \(A\), and \(\alpha\).

10.2.4 Dynamics

We analyze the system's behavior after a disturbance makes it fall into the small neighborhood around the steady state; linear approximation is very useful. Take a second order approximation of the EE around the steady state (with \(c_t=f(h_t)-h_{t+1}\)): $$\begin{aligned}\text{LHS}=u'(c_t)&\approx u'(c_{ss})+u''(c_{ss})[f'(h_{ss})(h_t-h_{ss})-(h_{t+1}-h_{ss})]\\&=u'+u''f'(h_t-h_{ss})-u''(h_{t+1}-h_{ss})\\\text{RHS}=\beta f'(h_{t+1})u'(c_{t+1})&\approx\beta f'u'+\beta\left\{f''u'(h_{t+1}-h_{ss})+(f')^2 u''(h_{t+1}-h_{ss})-f'u''(h_{t+2}-h_{ss})\right\}\end{aligned}$$ Define \(z_t=h_t-h_{ss}\), and using the fact \(\beta f'=1\), rewrite: $$0=-\beta f'u''z_{t+2}+\beta\left(f''u'+(f')^2 u''+u''\right)z_{t+1}-u''f'z_t\tag{10.1}$$ This is a second-order linear difference equation. We need two boundary conditions: (1) the chosen initial condition \(h_0\); (2) convergence to \(h_{ss}\). The characteristic equation of (10.1) is $$-\beta f'u''\lambda^2+\beta\left(f''u'+(f')^2 u''+u''\right)\lambda-u''f'=0$$ which has two roots \(\lambda_1\), \(\lambda_2\), and \(z_t\) has the solution \(z_t=C_1\lambda_1^t+C_2\lambda_2^t\). Suppose \(|\lambda_1|<1\), then by Vieta's theorem \(\lambda_1\cdot\lambda_2=1/\beta>1\), so \(|\lambda_2|>1\). So the first boundary condition pins down \(C_1\) to match \(h_0\) and the second boundary condition requires that \(C_2=0\).

Now suppose the social average human capital \(H\) enters the technology as a positive externality, so the technology is $$F(h,H)=Ah^\theta H^r$$ where \(\theta>0\), \(r>0\), \(\theta+r<1\).

Suppose every agent in the economy starts with the same initial human capital \(h_0\). The social planner gives every agent equal weight and asks them to do exactly the same thing in every period. So every agent's human capital stays the same with each other in every period, i.e. \(h_t=H_t\) for \(\forall t\).

So the social planner's problem is exactly the same as before (without externality) if we set \(\alpha=\theta+r\), i.e. $$F(h,H)=Ah^\theta H^r=Ah^\theta h^r=Ah^{\theta+r}=Ah^\alpha=f(h)$$

10.4 Positive Externality: The Recursive Competitive Equilibrium

In the following discussion, we will consider the economy in which agents make individual decisions for their own.

10.4.1 Set-up

• Same as in the social planner's problem, the social average human capital \(H\) enters the technology as a positive externality: \(F(h,H)=Ah^\theta H^r\), where \(\theta>0\), \(r>0\) and \(\hat\alpha\equiv\theta+r<1\).
• There are two state variables for the agent's problem: \(h\) and \(H\).
• The agent's conjecture of average human capital in the next period is denoted as \(\Phi(H)\), which is based on \(H\), the average human capital of the current period.
• The agent's optimal choice is defined as \(y^\star=\phi(h,H,\Phi)\), which depends on \(\Phi\).
• The value function is now written as \(W(h,H;\Phi)\).

10.4.2 The Bellman equation $$W(h,H)=\max_{y\in[0,F(h,H)]}\{u(F(h,H)-y)+\beta W(y,\Phi(H))\}$$ Here \(\Phi(H)\) is the conjecture about the choice of everyone else.

10.4.3 Recursive competitive equilibrium

A recursive competitive equilibrium is defined by a function \(\Phi^e(H=h)\) with the property $$\phi^\star(h,H=h,\Phi^e(H=h))=\Phi^e(H=h)$$ i.e. \(\phi^\star(h,h,\Phi^e(h))=\Phi^e(h)\).

10.4.4 Results of the model

• The f.o.c. that characterizes \(y^\star\): \(u'(F(h,H)-y^\star)=\beta W_1(y^\star,\Phi^e(H))\), i.e. \(u'(F(h,h)-y^\star)=\beta W_1(y^\star,y^\star)\) (\(W_1\) means the partial derivative w.r.t. \(W\)'s first argument).
• The Envelop Condition (EC): \(W_1(h,H)=F_1(h,H)u'(F(h,H)-y^\star)\), i.e. \(W_1(h,h)=F_1(h,h)u'(F(h,h)-y^\star)\) (\(F_1\) means the partial derivative w.r.t. \(F\)'s first argument).
• The Euler Equation (EE): combine the f.o.c. and the Envelop condition: $$u'(F(h_t,h_t)-h_{t+1})=\beta F_1(h_{t+1},h_{t+1})u'(F(h_{t+1},h_{t+1})-h_{t+2})$$
• The steady state satisfies: $$\begin{aligned}u'(F(h_{ss},h_{ss})-h_{ss})&=\beta F_1(h_{ss},h_{ss})u'(F(h_{ss},h_{ss})-h_{ss})\\\Rightarrow1&=\beta F_1(h_{ss},h_{ss})=\beta\theta Ah_{ss}^{\theta-1}h_{ss}^r=\beta\theta Ah_{ss}^{\theta+r-1}\\\Rightarrow\tilde h_{ss}&=(\beta A\theta)^{\frac{1}{1-(r+\theta)}}\end{aligned}$$ If we define \(\theta=\alpha\) and \(r+\theta=\hat\alpha\), then \(\tilde h_{ss}=(\beta A\alpha)^{1/(1-\hat\alpha)}\).

10.5.1 Set-up

Same as in the infinite horizon case, we have: - state variable \(x\in X\), with state space \(X\in\mathbb R^n\) convex and compact. - correspondence \(\Gamma:X\rightrightarrows X\) non-empty, compact valued and continuous. - period return function \(F(x,y):X\times X\to\mathbb R\) bounded and continuous in \(x\) and \(y\). - discounting factor \(\beta\in(0,1)\). - In addition, fix the number of periods as \(N\), which is finite.

10.5.2 Bellman equations

We can use the backward induction methodology to first derive the value equation for the last period and then go one step back each time to derive value functions for all the previous periods. - The Bellman equation for the ending period \(N\): \(V(x,N)=\max_{y\in\Gamma(x)}F(x,y)\). - The Bellman equation for period \(n=1,2,\dots,N-1\): \(V(x,n)=\max_{y\in\Gamma(x)}\{F(x,y)+\beta V(y,n+1)\}\).

10.5.3 Properties of the value functions

Now we have a sequence of value functions \(\{V(x,n)\}_{n=1}^N\). Let's consider the properties of them. - For the ending period \(N\), \(V(x,N)=\max_{y\in\Gamma(x)}F(x,y)\): - exists: because \(F(x,y)\) is continuous on a compact set, so it attains maximum in \(X\). - is unique: if we assume that \(F(x,y)\) is strictly quasi-concave. - is continuous in \(x\): because \(F(x,y)\) is continuous in \(x\) and \(y\) and \(\Gamma:X\rightrightarrows X\) is continuous as a correspondence, we can use the Theorem of Maximum. - is strictly concave in \(x\): if we assume \(F(x,y)\) is strictly concave in \(x\) and \(y\), and \(\Gamma:X\rightrightarrows X\) is convex as a correspondence. - is strictly increasing in \(x\): if we assume \(F(x,y)\) is strictly increasing in \(x\) and \(\Gamma:X\rightrightarrows X\) is monotone as a correspondence. - is differentiable in \(x\): if we assume \(F(x,y)\) is differentiable in \(x\in\text{int}(X)\) and \(g(x)\in\text{int}(\Gamma(x))\). - For period \(n=1,2,\dots,N-1\), \(V(x,n)=\max_{y\in\Gamma(x)}\{F(x,y)+\beta V(y,n+1)\}\): all the desired properties of \(V(x,n)\) (i.e. existence, uniqueness, continuity in \(x\), strict concavity in \(x\), strict monotonicity in \(x\), and differentiability) hold if these properties hold for \(V(x,n+1)\).