Sequential & Recursive Problems

Sequential & Recursive Problems#

Exercises from the Class Notes#

Exercise 1.1#

Show that the objective function of the cake-eating problem is strictly concave when the per-period utility is strictly concave.

Solution

If \(U\left(c\right)\) is strictly concave, then \(\forall c_{1}, c_{2}, \forall \alpha\in\left(0,1\right)\),

\[\begin{equation*} U\left(\left(1-\alpha\right)c_{1}+\alpha c_{2}\right)>\left(1-\alpha\right)U\left(c_{1}\right) + \alpha U\left(c_{2}\right). \end{equation*}\]

Due to subadditivity of a concave function,

\[\begin{equation*} \sum_{t=0}^{\infty}\beta^{t}U\left(\left(1-\alpha\right)c_{1}+\alpha c_{2}\right)>\sum_{t=0}^{\infty}\beta^{t}\left(1-\alpha\right)U\left(c_{1}\right) + \sum_{t=0}^{\infty}\beta^{t}\alpha U\left(c_{2}\right). \end{equation*}\]

Therefore the objective function of the cake-eating problem is strictly concave when the per-period utility is strictly concave.

Exercise 1.2#

Generalize Theorem 1.1 without assuming that a maximum exists. Instead let the solution of (SP) be defined as a supremum and prove that it satisfies (FE).

Solution

See Proof of Theorem 4.2 in SLP.

Exercise 1.4#

Consider the Estate Planning problem when \(U(c)=c\), \(\beta=1/(1+r)\) and modify the savings technology so that

\(\Gamma(x)= \begin{cases} -x/\beta, \text{ if } x>0 \\ x/\beta, \text{ if } x \leq 0 \end{cases}\)

Show that \(V(x)=(1+r)x\) solves the Bellman equation although \(V^*(x)\neq (1+r)x\).

Solution

Since the feasibility set is always a singleton, the agent has no control over his action. Considering first cases where \(x<0\), we have

\[\begin{align*} V^*(x_0) & = (1+r)x_0-x_1+\beta V^*(x_1) \\ & = (1+r)x_0 -\frac{x_0}{\beta}+\beta V^*\left(\frac{x_0}{\beta}\right) \\ & = \beta V^*\left(\frac{x_0}{\beta}\right). \end{align*}\]

The second equality follows from \(\beta=1/(1+r)\). Iterating the computation above, one finds that \(V^*(x_0)=0\) when \(x_0<0\).

Consider now cases where \(x>0\). Then we have

\[\begin{align*} V^*(x_0) & = (1+r)x_0-x_1+\beta V^*(x_1) \\ & = (1+r)x_0 +\frac{x_0}{\beta}+\beta V^*\left(-\frac{x_0}{\beta}\right) \\ & = 2(1+r)x_0+\beta V^*\left(-\frac{x_0}{\beta}\right)\\ & = 2(1+r)x_0. \end{align*}\]

The last equality follows from the fact that \(V^*\left(-\frac{x_0}{\beta}\right)=0\) because \(-x_0/\beta\) is negative.

Putting together the two solutions, we find that \(V^*(x)=\max\{2(1+r)x,0\}\). The optimal solution to the sequential problem satisfies the trensversality condition since \(\lim_{t\rightarrow \infty}\beta^tV^*(x^*_t)=0\).

We now compute the solution of the Functional Equation \(V(x)=\max_{x' \in \Gamma(x)}\left\{(1+r)x-x'+\beta V(x')\right\}.\)

We try the following guess \(V(x)=(1+r)x\). Reinserting it into the Functional Equation, we get

\[\begin{align*} V(x) & = \max_{x' \in \Gamma(x)}\left\{(1+r)x-x'+\beta (1+r)(x')\right\} \\ & = \max_{x' \in \Gamma(x)}\left\{(1+r)x\right\}\\ & = (1+r)x,\\ \end{align*}\]

The second equality follows from \(\beta=1/(1+r)\). Hence \(V(x)=(1+r)x\) is indeed a solution of the Functional Equation. However, \(V(x) \neq V^*(x)\) even though \(V^*(x^*)\) satisfies the transversality condition. By contrast, \(V(x)\) does not satsfy the condition of Theorem 1.5 in the class notes since

\[ \lim_{t\rightarrow \infty}\beta^tV(x^*_t)=x_0<0, \text{when } x_0<0.\]

Additional Exercises#

Exercise 1.5 (Lagrangian)#

  1. Consider the Estate Planning problem in Exercice 1.1. Let the horizon \(T\) go to infinity and use the Lagrangian to derive the transversality condition.

  2. Under what condition on the value function is the transversality condition for the Lagrangian problem implied by that of the recursive problem?

Solution

  1. We introduce the Lagrange multiplier \((\lambda)\) for the intertemporal constraint that govern the evolution of assets, and a terminal multiplier \(( \mu_T \geq 0 )\) for the no Ponzi condition \(( a_{T+1} \geq 0 )\).

    The Lagrangian for this problem with finite horizon \(T\) can be written as follows

    \( \mathcal{L} = \sum_{t=0}^T \beta^t U(c_t) + \lambda \left[a_0 - \sum_{t=0}^T c_t - a_{T+1}\right] + \mu_T a_{T+1}. \)

    Focusing on the terminal condition, we find that

    \( \frac{\partial \mathcal{L}}{\partial a_{T+1}} = 0 \rightarrow \lambda = \mu_T . \)

    Since \(\lambda = \beta^t u'(c_t) >0\), we have \(\mu_T >0\) and the Kuhn-Tucker condition \(\mu_T a_{T+1} = 0\) implies that \(a_{T+1} = 0\).

    Letting the horizon go to infinity, we obtain the transversality condition

    \( \lim_{T\rightarrow \infty} \mu_T a_{T+1} = \lim_{T\rightarrow \infty} \beta^T u'(c_T) a_{T+1} = 0.\)

  2. The FOC of the Bellman equation is given by \(\beta V'(a_{t+1})= u'(c_t)\). Hence, if the value function is concave, we have

    \( u'(c_T) a_{T+1}=\beta V'(a_{T+1})a_{T+1} \leq \beta V(a_{T+1})\),

    which implies that \( \beta^T u'(c_T) a_{T+1} \leq \beta^{T+1} V(a_{T+1})\). Remember that the transversality condition of the Bellman equation reads \(\lim_{T\rightarrow \infty} \beta^TV(a_T) =0\). Hence we indeed have \(\lim_{T\rightarrow \infty} \beta^T u'(c_T) a_{T+1} = 0\), whenever the transversality condition of the recursive problem holds and the value function is concave.

    We will show in lecture 2 that concavity of the value function holds true because the value function inherits the concavity of the per-period utility function \(u(c)\). In other words, the transversality condition of the recrusive problem is more stringent than that of the Lagrangian problem.

Exercise 1.6 (Unbounded Rewards)#

Show that the transversality condition of Theorem 1.3 is violated in the cake-eating problem when \(U(c)=ln(c)\).

Solution

Consider the path where \(c_0=(1+r)a_0\) and \(c_t=0\) for all \(t>0\). This consumption profile is obviously feasible. Hence \(\underline{a}=\{(1+r)a_0,0,0,...\}\in \Pi(a_0)\). Given that \(\Gamma(0)=0\), the value function must satisfy

\( V(0) = U(0) + \beta V(0),\)

and so \(V(0) = U(0)/(1-\beta)=-\infty\) since \(U(c)=ln(c)\). In particular, we have \(V(0)<-\beta^{-T}\), which implies in turn that \(\beta^TV(a_T)<-1\) for all \(T\). It follows that \(\underline{a}\) violates the transversality condition \(\lim_{T\rightarrow \infty} \beta^TV(a_T)=0\).

Exercise 1.7 (Bubbles)#

Consider a deterministic version of the Lucas (1978) asset pricing model. There are many homogeneous agents, a single good and a single asset that pays a dividend of \(d_t\) units of the good in each period \(t\). The asset supply is normalized to one. The agent solves

\[\begin{align*} \max_{\{c_t,x_t\}_{t=0}^\infty} & \sum_{t=0}^\infty \beta^t u(c_t) \\ s.t. \text{ } & x_0 = 1, \\ \text{ } & c_t + p_tx_{t+1} =(p_t+d_t)x_t, x_{t+1} \geq 0, t=0,1,2,\dots \end{align*}\]

  1. Show that the fundamental price

    \[\begin{equation*} p^*_t =\sum_{i=0}^\infty \beta^i \frac{u'(d_{t+i})}{u'(d_t)}d_{t+i} \end{equation*}\]

    satisfies the Euler equation of the agent.

  2. The sequence \(\{p^*_t+b_t\}\) also satisfies the Euler equation as long as the bubbly component \(b_t\) obeys the following law of motion

    \[\begin{equation*} u'(d_{t})b_t=\beta u'(d_{t+1})b_{t+1}. \end{equation*}\]

    Explain why the bubble is ruled out by the transversality condition of the Lagrangian problem.

Solution

  1. Since The Euler equation is given by

    \[\begin{equation*} u'(d_{t})p_t=\beta u'(d_{t+1})(p_{t+1}+d_{t+1}), \end{equation*}\]

    it is indeed satisfied replacing \(p_t\) with \(p^*_t\).

  2. The transversality condition of the Lagrangian problem reads \(\lim_{T\rightarrow \infty} \beta^Tu'(d_t)p_T=0\). However, when \(b_0\) is positive, we have \(\beta^t u'(d_t)b_t = u'(d_0)b_0 >0\) for all \(t\), and so the transversality condition is violated. Hence, the transversality condition is not only sufficient but also necessary to ensure that the bubble component of asset prices vanishes. See Kamihigashi (2001, Econometrica) for more details on the necessity of transversality conditions.