<p>The function <span class="math-container">$u(F(x)-y)$</span> is not necessarily bounded on <span class="math-container">$A$</span>. For example, if <span class="math-container">$u(x) = F(x) = \sqrt{x}$</span> then:
<span class="math-container">$$
u(F(x)-y) = \sqrt{\sqrt{x}-y},
$$</span>
Taking <span class="math-container">$y = 0$</span>, this gives <span class="math-container">$u(F(x)) = \sqrt{\sqrt{x}}$</span>, which is clearly unbounded in <span class="math-container">$x$</span>.</p>
<p>The problem you are looking at is the following:
<span class="math-container">$$
\max_{(x_t, y_t)_{t = 0}^\infty} \sum_{t = 0}^\infty \beta^t u(F(x_t) - y_{t+1})  \text{ s.t. } y_{t+1} \in [0, F(x_t)].
$$</span>
Notice that this problem is not well defined. In particular, given that <span class="math-container">$u$</span> is strictly increasing, the best choice for <span class="math-container">$y_{t+1}$</span> is to set it equal to zero at every instance <span class="math-container">$t$</span>. This gives the payoff function
<span class="math-container">$$
\sum_{t = 0}^\infty \beta^t u(F(x_t)),
$$</span>
which is clearly increasing in <span class="math-container">$x_t$</span> (as both <span class="math-container">$u$</span> and <span class="math-container">$F$</span> are strictly increasing). As such, the best thing to do is to set <span class="math-container">$x_t$</span> as large as possible (so equal to <span class="math-container">$+ \infty$</span>). This means that your maximisation problem has no solution.</p>
<p>Now, assume that you have a better behaving model, for example, <span class="math-container">$y_t = x_t$</span>. This then gives the problem:
<span class="math-container">$$
\max_{(x_t)_{t = 0}^\infty} \sum_{t = 0}^\infty \beta^t u(F(x_t) - x_{t+1})  \text{ s.t. } x_{t+1} \in [0, F(x_t)].
$$</span>
The function <span class="math-container">$u(F(x)-y)$</span> is still unbounded, but now you can show that the objective function <span class="math-container">$\sum_{t=0}^\infty \beta^t u(F(x_t) - x_{t+1})$</span> is bounded for every feasible path. Let <span class="math-container">$\partial u(0)$</span> be a supdifferential (derivative) for <span class="math-container">$u$</span> at zero. Then, using concavity of <span class="math-container">$u$</span>, we have:
<span class="math-container">$$
\begin{align*}
\sum_{t = 0}^n \beta^t u(F(x_t) - x_{t+1}) &amp;\le \sum_{t = 0}^n \beta^t \left(u(0) + \partial u(0)[F(x_t) - x_{t+1}]\right),\\
&amp;= u(0) \sum_{t = 0}^n \beta^t + \partial u(0) \underbrace{\sum_{t = 0}^n \beta^t [F(x_t) - x_{t+1}]}_{=A}.
\end{align*}
$$</span>
Now, <span class="math-container">$F(x) \le \overline{x} + x$</span> (if <span class="math-container">$x \le \overline{x}$</span> then <span class="math-container">$F(x) \le \overline{x}$</span> and if <span class="math-container">$x \ge \overline{x}$</span>, then <span class="math-container">$F(x) \le x$</span>). So,
<span class="math-container">$$
\begin{align*}
A &amp;\le \sum_{t = 0}^n \beta^t [\overline{x} + x_t - x_{t+1}],\\
&amp;= \overline{x} \sum_{t = 0}^n \beta^t + \underbrace{\sum_{t = 0}^n \beta^t (x_t - x_{t+1})}_{=B}
\end{align*}
$$</span>
Then,
<span class="math-container">$$
\begin{align*}
B &amp;= \sum_{t = 0}^n \beta^t (x_t - x_{t+1}),\\
&amp;=x_0 \underbrace{- x_1 + \beta x_1}_{\le 0} \underbrace{- \beta x_2 + \beta^2 x_2}_{\le 0} \underbrace{- \beta^2 x_3 + \,\,}_{\le 0} \ldots \underbrace{\,\, + \beta^n x_n}_{\le 0} - \beta^n x_{n+1},\\
&amp;\le x_0 - \beta^n x_{n+1} \le x_0
\end{align*}
$$</span>
Putting it all together, we obtain the bound:
<span class="math-container">$$
\begin{align*}
\sum_{t = 0}^n \beta^t u(F(x_t) - x_{t+1}) &amp; \le (u(0) + \partial u(0) \overline{x}) \sum_{t = 0}^n \beta^t + \partial u(0) x_0
\end{align*}
$$</span>
Taking the limit <span class="math-container">$t \to \infty$</span>, the right hand side converges to <span class="math-container">$\frac{u(0) + \partial u(0) \overline{x}}{1 - \beta} + \partial u(0) x_0$</span> (a fixed number).</p>

CC BY-SA 4.0
2023-09-18T07:40:49.790Z
2023-09-18T07:40:49.790Z
tdm
<p>I have the following dynamic programming problem:</p>
<p><span class="math-container">$$\max_{\{x_t,y_{t+1}\}_{t=0}^\infty}\sum_{t=0}^\infty \beta^tu(F(x_t)-y_{t+1})\;\;\;\;\;\text{s.t}\;\;\;\;y_{t+1}\in\Gamma(x_t)$$</span></p>
<p>where <span class="math-container">$\Gamma(x)=\{y\in\mathbb{R}_{+}\mid 0\le y\le F(x)\}$</span>, and the functions <span class="math-container">$u$</span> and <span class="math-container">$F$</span> have the following properties:</p>
<ol>
<li><span class="math-container">$u:\mathbb{R}_{+}\to\mathbb{R}$</span> is continuous, strictly increasing, and strictly concave;</li>
<li><span class="math-container">$F:\mathbb{R}_{+}\to\mathbb{R}$</span> is continuous, strictly increasing, and concave;</li>
<li><span class="math-container">$F(0)=0$</span>;</li>
<li>And there exists <span class="math-container">$\bar{x}&gt;0$</span> such that:</li>
</ol>
<ul>
<li><p>If <span class="math-container">$x\in[0,\bar{x}]$</span> then <span class="math-container">$F(x)\in[x,\bar{x}]$</span>.</p>
</li>
<li><p>If <span class="math-container">$x&gt;\bar{x}$</span> then <span class="math-container">$F(x)&lt;x$</span>.</p>
</li>
</ul>
<p>I've got to show that the function <span class="math-container">$G(x,y)\equiv u(F(x)-y)$</span> is bounded over the set <span class="math-container">$A\equiv\{(x,y)\in \mathbb{R}_{+}\times\mathbb{R}_{+}\mid y\in\Gamma(x)\}$</span>.</p>
<p>What I have tried: Let <span class="math-container">$(x,y)\in A$</span>, then <span class="math-container">$y\in\Gamma(x)$</span>. First, by definition the functions <span class="math-container">$u$</span> and <span class="math-container">$F$</span> clearly <span class="math-container">$G$</span> is bounded below. Now in order to show that <span class="math-container">$G$</span> is bounded above, I noticed that the set of images <span class="math-container">$G(x,\Gamma(x))$</span> is compact <em>in the second argument</em> because <span class="math-container">$G$</span> is continuous and <span class="math-container">$\Gamma(x)$</span> is compact, i.e. given <span class="math-container">$x$</span> we have that the function <span class="math-container">$G(x,\cdot)$</span> is bounded in <span class="math-container">$\Gamma(x)$</span>.</p>
<p>Now, trying to show that <span class="math-container">$G$</span> is bounded above in <span class="math-container">$x$</span> (i.e. in the <em>first</em> argument) has proven to be more involved, I'm trying to use the fourth property shown above about the existence of <span class="math-container">$\bar{x}$</span>, where we have two cases, if <span class="math-container">$x\in[0, \bar{x}]$</span> then clearly <span class="math-container">$G(x,y)\le u(F(\bar{x})-y)\le u(F(\bar{x}))$</span>. But when considering <span class="math-container">$x&gt;\bar{x}$</span> we have <span class="math-container">$F(x)&lt;x$</span>, thus <span class="math-container">$G(x,y)&lt;u(x-y)$</span> which does not show that <span class="math-container">$G$</span> is bounded since the &quot;bound&quot; still depends on <span class="math-container">$x$</span> which is in a unbounded space <span class="math-container">$(\bar{x},\infty)$</span>.</p>
<p>I think there must be a trick with <span class="math-container">$F(x)&lt;x$</span> but I have not been able to see it, any help would be appreciated.</p>
<p>Thanks!</p>

<mathematical-economics><dynamic-programming>
Showing that reward function is bounded (dynamic programing)
manifold
# Showing that reward function is bounded (dynamic programing)

(Asked by: username_0 on 2023-09-17)

I have the following dynamic programming problem:

$$\max\_{\{x\_t,y\_{t+1}\}\_{t=0}^\infty}\sum\_{t=0}^\infty \beta^tu(F(x\_t)-y\_{t+1})\;\;\;\;\;\text{s.t}\;\;\;\;y\_{t+1}\in\Gamma(x\_t)$$

where $\Gamma(x)=\{y\in\mathbb{R}\_{+}\mid 0\le y\le F(x)\}$, and the functions $u$ and $F$ have the following properties:

1. $u:\mathbb{R}\_{+}\to\mathbb{R}$ is continuous, strictly increasing, and strictly concave;
2. $F:\mathbb{R}\_{+}\to\mathbb{R}$ is continuous, strictly increasing, and concave;
3. $F(0)=0$;
4. And there exists $\bar{x}>0$ such that:

* If $x\in[0,\bar{x}]$ then $F(x)\in[x,\bar{x}]$.
* If $x>\bar{x}$ then $F(x).

I've got to show that the function $G(x,y)\equiv u(F(x)-y)$ is bounded over the set $A\equiv\{(x,y)\in \mathbb{R}\_{+}\times\mathbb{R}\_{+}\mid y\in\Gamma(x)\}$.

What I have tried: Let $(x,y)\in A$, then $y\in\Gamma(x)$. First, by definition the functions $u$ and $F$ clearly $G$ is bounded below. Now in order to show that $G$ is bounded above, I noticed that the set of images $G(x,\Gamma(x))$ is compact *in the second argument* because $G$ is continuous and $\Gamma(x)$ is compact, i.e. given $x$ we have that the function $G(x,\cdot)$ is bounded in $\Gamma(x)$.

Now, trying to show that $G$ is bounded above in $x$ (i.e. in the *first* argument) has proven to be more involved, I'm trying to use the fourth property shown above about the existence of $\bar{x}$, where we have two cases, if $x\in[0, \bar{x}]$ then clearly $G(x,y)\le u(F(\bar{x})-y)\le u(F(\bar{x}))$. But when considering $x>\bar{x}$ we have $F(x), thus $G(x,y) which does not show that $G$ is bounded since the "bound" still depends on $x$ which is in a unbounded space $(\bar{x},\infty)$.

I think there must be a trick with $F(x) but I have not been able to see it, any help would be appreciated.

Thanks!

**Tags:** mathematical-economics, dynamic-programming


---

## 1 answers

### Answer by username_1 on 2023-09-18. Score: 2

The function $u(F(x)-y)$ is not necessarily bounded on $A$. For example, if $u(x) = F(x) = \sqrt{x}$ then:
$$
u(F(x)-y) = \sqrt{\sqrt{x}-y},
$$
Taking $y = 0$, this gives $u(F(x)) = \sqrt{\sqrt{x}}$, which is clearly unbounded in $x$.

The problem you are looking at is the following:
$$
\max\_{(x\_t, y\_t)\_{t = 0}^\infty} \sum\_{t = 0}^\infty \beta^t u(F(x\_t) - y\_{t+1}) \text{ s.t. } y\_{t+1} \in [0, F(x\_t)].
$$
Notice that this problem is not well defined. In particular, given that $u$ is strictly increasing, the best choice for $y\_{t+1}$ is to set it equal to zero at every instance $t$. This gives the payoff function
$$
\sum\_{t = 0}^\infty \beta^t u(F(x\_t)),
$$
which is clearly increasing in $x\_t$ (as both $u$ and $F$ are strictly increasing). As such, the best thing to do is to set $x\_t$ as large as possible (so equal to $+ \infty$). This means that your maximisation problem has no solution.

Now, assume that you have a better behaving model, for example, $y\_t = x\_t$. This then gives the problem:
$$
\max\_{(x\_t)\_{t = 0}^\infty} \sum\_{t = 0}^\infty \beta^t u(F(x\_t) - x\_{t+1}) \text{ s.t. } x\_{t+1} \in [0, F(x\_t)].
$$
The function $u(F(x)-y)$ is still unbounded, but now you can show that the objective function $\sum\_{t=0}^\infty \beta^t u(F(x\_t) - x\_{t+1})$ is bounded for every feasible path. Let $\partial u(0)$ be a supdifferential (derivative) for $u$ at zero. Then, using concavity of $u$, we have:
$$
\begin{align\*}
\sum\_{t = 0}^n \beta^t u(F(x\_t) - x\_{t+1}) &\le \sum\_{t = 0}^n \beta^t \left(u(0) + \partial u(0)[F(x\_t) - x\_{t+1}]\right),\\
&= u(0) \sum\_{t = 0}^n \beta^t + \partial u(0) \underbrace{\sum\_{t = 0}^n \beta^t [F(x\_t) - x\_{t+1}]}\_{=A}.
\end{align\*}
$$
Now, $F(x) \le \overline{x} + x$ (if $x \le \overline{x}$ then $F(x) \le \overline{x}$ and if $x \ge \overline{x}$, then $F(x) \le x$). So,
$$
\begin{align\*}
A &\le \sum\_{t = 0}^n \beta^t [\overline{x} + x\_t - x\_{t+1}],\\
&= \overline{x} \sum\_{t = 0}^n \beta^t + \underbrace{\sum\_{t = 0}^n \beta^t (x\_t - x\_{t+1})}\_{=B}
\end{align\*}
$$
Then,
$$
\begin{align\*}
B &= \sum\_{t = 0}^n \beta^t (x\_t - x\_{t+1}),\\
&=x\_0 \underbrace{- x\_1 + \beta x\_1}\_{\le 0} \underbrace{- \beta x\_2 + \beta^2 x\_2}\_{\le 0} \underbrace{- \beta^2 x\_3 + \,\,}\_{\le 0} \ldots \underbrace{\,\, + \beta^n x\_n}\_{\le 0} - \beta^n x\_{n+1},\\
&\le x\_0 - \beta^n x\_{n+1} \le x\_0
\end{align\*}
$$
Putting it all together, we obtain the bound:
$$
\begin{align\*}
\sum\_{t = 0}^n \beta^t u(F(x\_t) - x\_{t+1}) & \le (u(0) + \partial u(0) \overline{x}) \sum\_{t = 0}^n \beta^t + \partial u(0) x\_0
\end{align\*}
$$
Taking the limit $t \to \infty$, the right hand side converges to $\frac{u(0) + \partial u(0) \overline{x}}{1 - \beta} + \partial u(0) x\_0$ (a fixed number).


---

