DP2013-35

Elementary Results on Solutions to the
Bellman Equation of Dynamic
Programm ing: Existence, Uniqu eness,
and Convergence
Takashi KAMIHIGASHI
Revised December 2, 2013

Elementary Results on Solutions to the
Bellman Equation of Dynamic Programming:
Existence, Uniqueness, and Convergence∗
Takashi Kamihigashi†‡
December 2, 2013
Abstract
We establish some elementary results on solutions to the Bellman
equation without introducing any topological assumption. Under asmall number of conditions, we show that the Bellman equation has aunique solution in a certain set, that this solution is the value function,and that the value function can be computed by value iteration with
an appropriate initial condition. In addition, we show that the valuefunction can be computed by the same procedure under alternative
conditions. We apply our results to two optimal growth models: one
with a discontinuous production function and the other with “roughly
increasing” returns.
Keywords: Dynamic programming, Bellman equation, value function,
fixed point.
JEL Classification: C61∗

I would like to thank participants at the 11th SAET Conferance in Faro, 2011, theWorkshop in Honor of Cuong Le Van in Exeter, 2011, a seminar at the Paris School of
Economics in 2012, and the 21st European Workshop on General Equilibrium Theory
in Exeter, 2012—especially, Larry Blume, Myrna Wooders, Felix Kübler, Juan Pablo
Rincón-Zapatero, V. Filipe Martins-da-Rocha, Yiannis Vailakis, Cuong Le Van, Kevin
Reffett—for helpful comments and discussions. This paper has benefited from comments
and suggestions by three anonymous referees and an associate editor. Financial support
from the Japan Society for the Promotion of Science is gratefully acknowledged.
†
IPAG Business School, 184 Bd Saint Germain, 75006 Paris, France.
‡
RIEB, Kobe University, Rokkodai, Nada, Kobe 657-8501 Japan.
Email: tkamihig@rieb.kobe-u.ac.jp. Tel/Fax: +81-78-803-7015.

1

Introduction

Dynamic programming has been one of the most fundamental tools in economic analysis, particularly since Stokey and Lucas (1989).1 One of thelimitations of Stokey and Lucas’ work and earlier studies was that models
with unbounded returns were not fully addressed though such models are
extremely common in economics. This has been a major issue in the subsequent economic literature on dynamic programming, and important contributions have been made by Alvarez and Stokey (1998), Durán (2000), Le Van
and Morhaim (2002), Rincón-Zapatero and Rodrı́guez-Palmero (2003, 2007,2009), Martins-da-Rocha and Vailakis (2010), and Matkowski and Nowak(2011).
One thing common to the results established by these recent contributions
is that they rely heavily on topological assumptions, such as the continuityof the return function and that of the feasibility correspondence. While theseassumptions are completely standard in many models, there are important
cases in which they clearly fail. For example, threshold effects are associatedwith discontinuous technologies (Azariadiz and Drazen, 1990); moreoever,discontinuities are a common feature of ecological phenomena (Muradian,2001; Nævdal, 2003).2 Even a well-behaved maximization problem that
depends continuously on a parameter often results in discontinuities sinceparametric continuity of the objective function does not imply parametriccontinuity of the solution.3 Thus, in general, discontinuities are widespreadin principal-agent models and game theoretic models (though such models
are beyond the scope of this paper).4
The purpose of this paper is to establish some elementary results on
solutions to the Bellman equation—or fixed points of the Bellman operator—
without introducing any topological assumption. Such results not only apply
1

Recent applications of dynamic programming include Algan et al. (2011), Bloch andHouy (2012), Dutta and Radner (2012), Goenka and Lin (2012), Karp and Zhang (2012),
Llanes and Trento (2012), Roy and Zilcha (2012), Herrera and Martinelli (2013), Reis
(2013), and Schaar et al. (2013).
2
See Kamihigashi and Roy (2006, 2007) for optimal growth models with discontinuous
technologies.
3
Recall that the Theorem of the Maximum (e.g., Stokey and Lucas, 1989, Theorem 3.6)
shows that parametric continuity of the objective function only implies upper hemicontinuity of the solution correspondence, which means that the correspondence is in general
not continuous. See Dutta and Mitra (1989a, 1989b) for related discussions.
4
See Kamihigashi and Furusawa (2010, Figure 5) for a simple example.

1

to models with discontinuities but also disentangle basic properties of fixed
points of the Bellman operator from topological assumptions. One might
think that in our approach, topological assumptions would simply be replacedby alternative, more abstract assumptions, but that is certainly not the case.
In fact, the conditions required for each formal result proved in this paper
are all included in the statement of the result itself, and they are expressed
mostly in terms of inequalities between functions. Therefore, our results arehighly accessible to applied researchers as well as graduate students.
Our main results are twofold. First, given an order interval of functions
that is mapped into itself by the Bellman operator, if the upper and lower
boundaries of this order interval satisfy transversality-like conditions, then(a) the Bellman operator has a unique fixed point in the order interval; (b)this fixed point is the value function; and (c) the value function can becomputed by value iteration starting from the lower boundary of the orderinterval. Second, if there exists a function that is mapped upward by the
Bellman operator, and if this function is dominated by the value function
and satisfies a transversality-like condition, then the value function can becomputed by value iteration starting from this function.
To understand why such results can be shown without any topological assumption, note that most of the recent contributions except for Le Van andMorhaim (2002) are based on variants of the contraction mapping theorem.
In this approach, the Bellman operator is shown to be some type of contraction, and a variant of the contraction mapping theorem is used to show thatthe Bellman operator has a unique fixed point in the space of continuousfunctions with a suitable topology. Then this fixed point is shown to be thevalue function using standard arguments.
However, the technical conditions required for these results imply thatany fixed point in the function space under consideration must be the valuefunction. Since there is only one value function, it follows that the uniquenessof a fixed point can be guaranteed without using any variant of the contraction mapping theorem. The idea of our approach is to use the Knaster-Tarski
fixed point theorem instead of a variant of the contraction mapping theorem,
and to impose a minimal set of assumptions required for the application of
the Knaster-Tarski theorem. It turns out that this approach requires no topological assumption, yielding results that are considerably simpler than mostexisting results. We clarify this point by comparing one of our main resultswith the recent result developed by Rincón-Zapatero and Rodrı́guez-Palmero(2003, 2009) and Martins-da-Rocha and Vailakis (2010).
2

There is of course a downside to our approach, which offers only a minimal
convergence result and directly establishes no property of the value function
except that it lies in the given order interval. On the other hand, in mostcases, our convergence result is sufficient for computing the value function,and it is also useful in establishing certain properties of the value function
under additional conditions. We discuss the latter point in some detail in
Subsection 3.2.
In some sense, this paper is intended to be a continuation of Section 4.1
of Stokey and Lucas (1989), in which several fundamental results on dynamic
programming were developed without topological assumptions. Stokey andLucas introduced topological assumptions in their subsequent analysis, but it
is possible to continue further without introducing any topological assumption. Our results are also similar in spirit to those shown by Bertsekas andShreve (1978, Chapter 5), who mainly used monotonicity arguments. Our
results extend some of their results to cases in which the return function isunbounded both above and below. In Sections 2 and 3, we offer detailed
discussions of how our results relate to existing ones, including the relevant
results of Stokey and Lucas (1989) and Bertsekas and Shreve (1978).
The rest of the paper is organized as follows. In the next section, we
describe our framework and state our main results, which we prove in the
Appendix. In Section 3, we demonstrate how they can be used to derive otheruseful results, and discuss related results in the literature. In Section 4, we
present three examples. The first two examples are optimal growth models
with logarithmic utility: one having a discontinuous production function andthe other having “roughly increasing” returns. The third example demonstrates that value iteration may fail to converge to the value function unlessthe initial function is chosen appropriately. In Section 5, we conclude thepaper.

2

Main Results

Let X be a set, and Γ be a nonempty-valued correspondence from X to X.
Let D be the graph of Γ:
D = {(x, y) ∈ X × X : y ∈ Γ(x)}.

(2.1)

Let u : D → [−∞, ∞). In the optimization problem introduced below, X isthe state space, Γ is the feasibility correspondence, u is the return function,
3

and D is the domain of u.
Let Π and Π(x0 ) denote the set of feasible paths and that of feasible paths
from x0 , respectively:∞Π = {{xt }∞: ∀t ∈ Z+ , xt+1 ∈ Γ(xt )},t=0 ∈ X∞∞Π(x0 ) = {{xt }t=1 ∈ X : {xt }∞x0 ∈ X.
t=0 ∈ Π},

(2.2)
(2.3)

Let β ≥ 0. Given x0 ∈ X, consider the following optimization problem:
sup

T
X

L

T ↑∞
{xt }∞
t=1 ∈Π(x0 )t=0

β t u(xt , xt+1 ),(2.4)

where L ∈ {lim, lim} with lim = lim inf and lim = lim sup. Since u(x, y) < ∞for all (x, y) ∈ D, the objective function is well defined for any feasible path.
For {xt }∞t=0 ∈ Π, we define
S({xt }∞
t=0 ) = L

∞
X

T ↑∞

β t u(xt , xt+1 ).

(2.5)

t=0

The value function v ∗ : X → R is defined byv ∗ (x0 ) =sup{xt }∞
t=1 ∈Π(x0 )S({xt }∞
t=0 ),x0 ∈ X.

(2.6)

Note that v ∗ (x0 ) is unaffected if Π(x0 ) is replaced by Π0 (x0 ),5 where∞Π0 = {{xt }∞t=0 ∈ Π : S({xt }t=0 ) > −∞},∞0
Π0 (x0 ) = {{xt }∞t=1 ∈ Π(x0 ) : {xt }t=0 ∈ Π },x0 ∈ X.

(2.7)
(2.8)

Let V be the set of functions from X to [−∞, ∞). The Bellman operator
B on V is defined by(Bv)(x) = sup {u(x, y) + βv(y)},x ∈ X, v ∈ V.

(2.9)

y∈Γ(x)

Given v ∈ V , it need not be the case that Bv ∈ V . A fixed point of B
is a function v ∈ V such that Bv = v. It follows from Kamihigashi (2008,
Theorem 2) that v ∗ is a fixed point of B provided that v ∗ ∈ V :5

We follow the convention that sup ∅ = −∞.

4

Lemma 2.1. If v ∗ ∈ V , then v ∗ is a fixed point of B.
This is essentially the same result as Theorem 4.2 of Stokey and Lucas(1989). The difference is that Lemma 2.1 does not assume that u(x, y) > −∞for all (x, y) ∈ D; this assumption is often violated in applications. Instead,the lemma assumes that v ∗ ∈ V .
Let v, w : X → R. The partial order ≤ on the set of functions from X to
R is defined in the usual way:v≤w⇐⇒

∀x ∈ X, v(x) ≤ w(x).

(2.10)The partial order ≤ on the set of functions from D to R is defined in thesame way. It is immediate from (2.9) that B is a monotone operator on V :
v≤w∈V

⇒

Bv ≤ Bw.

(2.11)

If v ≤ w, we define the order interval [v, w] by[v, w] = {f ∈ V : v ≤ f ≤ w}.

(2.12)The order interval [−∞, w] means [v, w] with v = −∞; likewise [v, ∞] means[v, w] with w = ∞.6
Now we are ready to state the main results of this paper, the proofs ofwhich appear in the Appendix.
Theorem 2.1. Suppose that there exist v, v ∈ V such thatv ≤ v,
Bv ≥ v,
Bv ≤ v,0∀{xt }∞
t=0 ∈ Π ,lim β t v(xt ) ≥ 0,∀{xt }∞
t=0 ∈ Π,lim β t v(xt ) ≤ 0.

(2.13)(2.14)(2.15)(2.16)

t↑∞t↑∞(2.17)

Then the following conclusions hold:(a) The Bellman operator B has a unique fixed point in [v, v].
(b) This fixed point is the value function v ∗ .
6Given r ∈ R, the notation r is understood as the extended-real number r or thefunction identically equal to r depending on the context.

5∗7(c) The increasing sequence {B n v}∞
n=1 converges to v pointwise.

In conclusion (c) above, the sequence {B n v}∞
n=1 is increasing because wen+1nhave B v ≥ B v for any n ∈ N by applying B n to both sides of (2.14).
The next two results follow from intermediate steps in the proof of Theorem
2.1.
Proposition 2.1. Suppose that there exists v ∈ V satisfying (2.17) andv ∗ ≤ v.

(2.18)

Then v ∗ is the largest fixed point of B in [−∞, v].8
Theorem 2.2. Suppose that v ∗ ∈ V . Suppose further that there exists v ∈ V
satisfying (2.14), (2.16), andv ≤ v∗.
(2.19)
Then v ∗ is the smallest fixed point of B in [v, ∞]. Furthermore, the increasing∗
sequence {B n v}∞
n=1 converges to v pointwise.
Proposition 2.1 and the first conclusion of Theorem 2.2 can be shownby extending the proof of Stokey and Lucas (1989, Theorem 4.3) to ourslightly more general setting (though we do not entirely follow this route).
Their argument, which assumes the stronger version of (2.16) with Π inplace of Π0 , in fact goes through even with the original version of (2.16).
The idea of replacing Π with Π0 is due to Le Van and Morhaim (2002). Thisreplacement is important because even the value function v ∗ almost neversatisfies the stronger version of (2.16) if the return function is unbounded
below. See Subsection 3.3 for related conditions used by Rincón-Zapatero
and Rodrı́guez-Palmero (2003) and Martins-da-Rocha and Vailakis (2010).9
To our knowledge, the second conclusion of Theorem 2.2 is new. If it
is known a priori that v ∗ ∈ [v, v], which implies both (2.18) and (2.19),
then Theorem 2.1 follows directly from Proposition 2.1 and Theorem 2.2.
7

In this paper, “increasing” means “nondecreasing,” “decreasing” means “nonincreasing,” “positive” means “nonnegative,” and “negative” means “nonpositive.”
8
This means that any fixed point v of B in [−∞, v] satisfies v ≤ v ∗ . A similar remark
applies to the first conclusion of Theorem 2.2.
9
Rincón-Zapatero and Rodrı́guez-Palmero (2003, Theorem 5) also use a function satisfying (2.17) as an upper bound on an increasing sequence of fixed points of the Bellman
operators corresponding to truncated problems.

6But since it is not known a priori whether v ∗ lies in [v, v], the additional
contribution of Theorem 2.1 is to show that v ∗ indeed lies in [v, v].
If there exist functions v, v ∈ V satisfying (2.13)–(2.15), then the Bellman
operator B has a fixed point in [v, v] by the Knaster-Tarski fixed point theorem (see the Appendix for a precise argument). However, this fixed pointneed not be the value function v ∗ . In fact, under (2.13)–(2.15), we do noteven know whether v ∗ lies in V . Even if it does, it still need not lie in [v, v]
though it is a fixed point of B by Lemma 2.1.
Therefore, additional conditions are needed to ensure that v ∗ ∈ [v, v].
Conditions (2.16) and (2.17), which we called transversality-like conditionsin the Introduction, serve this purpose, implying that any fixed point of
B in [v, v] must be the value function v ∗ . Since we already know that B
has a fixed point in [v, v], this fixed point must be the value function v ∗ ,so that v ∗ lies in [v, v]. The uniqueness of a fixed point of B in [v, v] follows from the fact that any fixed point in [v, v] equals v ∗ . Rincón-Zapatero
and Rodrı́guez-Palmero (2003) offer several nontrivial, economically relevant
examples satisfying stronger versions of (2.13)–(2.17).
If (2.16) and (2.17) are violated, then the Bellman operator B can havemultiple fixed points in [v, v]; see Kamihigashi (2013). It follows that conditions such as (2.16) and (2.17) are crucial to ensuring that v ∗ is the only
fixed point of B in [v, v].
Note that in conclusion (c) of Theorem 2.1, convergence to v ∗ is guaranteed only from v. Our argument for this convergence result is based on
the simple observation that the limit of the increasing sequence {B n v}∞
n=1 isthe supremum of the sequence. This allows us to interchange this supremum
with another supremum (see (A.16)–(A.18)) to show that the limit is thevalue function v ∗ . The case of the decreasing sequence {B n v}∞
n=1 , which also
converges pointwise, is not symmetric since the sup and inf operators arein general not interchangeable. In Subsection 4.3, we construct an example
satisfying (2.13)–(2.17) in which limn↑∞ B n v 6= v ∗ .10
Recall that the definition of the value function v ∗ in (2.6) depends on thedefinition of L, which can be lim or lim. Thus there are in fact two valuefunctions: one with L = lim and the other with L = lim. An interesting
implication of Theorem 2.1 is that these two functions coincide under (2.13)–(2.17). This is because the unique fixed point of B established in Theorem
2.1 depends only on B, which is independent of L.
10

See Strauch (1966, p. 880) for a related example of an undiscounted stochastic model.

73Corollaries

3.1

Special Cases

In this subsection, we show various special cases of the results shown in theprevious section to illustrate how our results can be used to derive otheruseful results. Many of the results shown here are more or less known, butthese results are intended to clarify how our results relate to existing ones.
The last two results in this subsection are new and useful in our view. Let
us start with a simple consequence of Proposition 2.1.
Corollary 3.1. Suppose that there exists v ∈ V satisfying (2.15), (2.17), and(2.18). Let v ∗ be the pointwise limit of the decreasing sequence {B n v}∞
n=1 .
Then v ∗ ≤ v ∗ . Furthermore, if v ∗ is a fixed point of B, then v ∗ = v ∗ .
Proof. The inequality v ∗ ≤ v ∗ is immediate from (2.15) and (2.18). If v ∗ is a
fixed point of B, then v ∗ ≤ v ∗ by Proposition 2.1; thus v ∗ = v ∗ .
The above result is essentially equivalent to Theorem 4.14 of Stokey andLucas (1989). Corollary 3.1 along with Proposition 2.1 implies the following.
Corollary 3.2. Suppose that u ≤ 0. Then v ∗ is the largest negative fixed
point of B. Let v ∗ be the pointwise limit of the decreasing sequence {B n 0}∞
n=1 .
∗
∗
∗
∗
∗
Then v ≤ v . Furthermore, if v is a fixed point of B, then v = v .
Proof. Since u ≤ 0, we have B0 ≤ 0 and v ∗ ≤ 0; thus (2.15) and (2.18) holdwith v = 0. In addition, (2.17) trivially holds. Hence the conclusions holdby Proposition 2.1 and Corollary 3.1.
The above result is essentially equivalent to Proposition 5.8 of Bertsekas
and Shreve (1978). The following result deals with the case u ≥ 0.
Corollary 3.3. Suppose that u ≥ 0, and that v ∗ ∈ V . Then v ∗ is the smallest
positive fixed point of B, and the increasing sequence {B n 0}∞
n=1 converges to∗v pointwise.
Proof. Since u ≥ 0, we have B0 ≥ 0 and v ∗ ≥ 0; thus (2.14) and (2.19) holdwith v = 0. In addition, (2.16) trivially hold. Hence the conclusions hold byTheorem 2.2.

8

The above result is essentially equivalent to Proposition 5.7 of Bertsekas
and Shreve (1978). Corollaries 3.2 and 3.3 indicate that our results in theprevious section extend their results to problems in which the return function is unbounded both above and below. Since such return functions arecommon in economics, this extension is significant. It is also nontrivial giventhat Bertsekas and Shreve’s (1978, Chapter 5) arguments rely heavily on
the assumption that the return function takes only one sign, as assumed in
Corollaries 3.2 and 3.3 above.
Next we consider the case in which the return function u is bounded:
Corollary 3.4. Suppose that β ∈ [0, 1). Suppose further that there exist
constants µ, µ ∈ R such thatµ ≤ u ≤ µ.

(3.1)

Then conclusions (a)–(c) of Theorem 2.1 hold with
v=

µ
,
1−β

v=

µ
.
1−β

(3.2)

Proof. We have v ≤ v by construction. Note that for any x ∈ X, we have(Bv)(x) = sup {u(x, y) + βv(y)}(3.3)

y∈Γ(x)≥ sup {µ + βµ/(1 − β)} = µ/(1 − β) = v(x).

(3.4)

y∈Γ(y)

Thus Bv ≥ v. We similarly obtain Bv ≤ v. Hence (2.13)–(2.15) hold. Sincev and v are constant functions and β ∈ [0, 1), (2.16) and (2.17) trivially hold.
Conclusions (a)–(c) of Theorem 2.1 now follow.
The above result is similar to the well known result that if u is bounded
and continuous, and if Γ is continuous and compact-valued, then the Bellman operator has a unique fixed point in the space of bounded continuousfunctions; this fixed point is the value function; and value iteration converges
uniformly to the value function starting from any bounded continuous function (Stokey and Lucas, 1989, pp. 79–80). Corollary 3.4 shows that similar
conclusions can be obtained without any topological assumption except for
the globally uniform convergence result. This result is particularly useful toapplied researchers and graduate students because it can be shown and usedwithout knowing mathematical concepts such as metric spaces, contractions,9and completeness. In addition, even under standard topological assumptions,the approach based on the contraction mapping theorem fails as soon as one
inequality is removed from (3.1), but our approach continues to work:
Corollary 3.5. Suppose that β ∈ [0, 1), and that v ∗ ∈ V . Suppose further
that there exists a constant µ ∈ R such that u ≥ µ. Then v ∗ is the smallest
fixed point v of B with v ≥ µ/(1 − β), and the increasing sequence {B n µ}∞n=1
converges to v ∗ pointwise.
Proof. Let v = µ/(1 − β) ∈ V . Then (2.14) and (2.16) hold as in the proofof Corollary 3.4. In addition, (2.19) is immediate from the inequality u ≥ µ.
Thus the conclusions hold by Theorem 2.2.
The above result is similar to Corollary 3.3, but requires the additional
assumption that β ∈ [0, 1) in order to allow for the case µ < 0. To ourknowledge, the next two results are new although they are somewhat similar
to Corollaries 3.4 and 3.5. The new results show how one can construct
functions v and v that can be used to apply Theorems 2.1 and/or 2.2 evenwhen the conditions of Corollaries 3.4 and 3.5 are too restrictive; see Section
4.1 for applications.
Corollary 3.6. Suppose that there exist functions u, u : D → [−∞, ∞) such
that
(3.5)
u ≤ u ≤ u.
Suppose further that there exist correspondences Γ, Γ : X → X such that∀x ∈ X,Γ(x) ⊂ Γ(x) ⊂ Γ(x).

(3.6)

Let v : X → R be the value function given by (2.6) with u and Γ replacing uand Γ, respectively. Let v : X → R be the value function given by (2.6) withu and Γ replacing u and Γ, repectively. Suppose that v ∈ V , and that (2.16)
and (2.17) hold. Then conclusions (a)–(c) of Theorem 2.1 hold.
Proof. We have v ≤ v by construction. Since v ≤ v ∈ V , we have v ∈ V aswell. Note that for any x ∈ X, we have(Bv)(x) = sup {u(x, y) + βv(y)}(3.7)

y∈Γ(x)≥ sup {u(x, y) + βv(y)} = v(x),y∈Γ(y)

10(3.8)

where the last equality holds by Lemma 2.1. It follows that Bv ≥ v. We
similarly obtain Bv ≤ v. Now (2.13)–(2.15) hold. Since (2.16) and (2.17)
hold by assumption, conclusions (a)–(c) of Theorem 2.1 now follow.
Corollary 3.7. Suppose that v ∗ ∈ V , and that there exists a function u :D → [−∞, ∞) such that u ≤ u. Suppose further that there exists a correspondence Γ : X → X such that Γ(x) ⊂ Γ(x) for all x ∈ X. Define v asin Corollary 3.6. Suppose that (2.16) holds. Then v ∗ is the smallest fixed
point v of B in [v, ∞], and the increasing sequence {B n v}∞
n=1 converges tov ∗ pointwise.
Proof. We have (2.14) and (2.16) as in the proof of Corollary 3.6. In addition,(2.19) is immediate from the inequality u ≤ u. Since v ∗ ∈ V by hypothesis,
we have v ∈ V by (2.19). Thus the conclusions hold by Theorem 2.2.

3.2

Properties of the Value Function

There are two obvious limitations of the convergence result in Theorems 2.1
and 2.2. First, convergence to the value function v ∗ is guaranteed only fromone particular function v. Second, convergence occurs only pointwise. Despite these limitations, there are various situations in which this convergence
result can help establish a property of the value function. This is because
pointwise convergence preserves many important properties such as monotonicity, concavity, convexity, measurability, and supermodularity. In fact,
any property that can be expressed in terms of weak inequalities is preserved
under pointwise convergence. In addition, since our convergence result deals
only with a particular increasing sequence starting from v, it suffices to verify
that a property of interest is preserved at the limit of this sequence. The
following result formalizes this idea.
Corollary 3.8. Suppose that v ∗ ∈ V . Let v ∈ V satisfy (2.14), (2.16), and(2.19). Let W ⊂ V satisfy the following conditions:(i) v ∈ W .
(ii) For any v ∈ W with Bv ≥ v, we have Bv ∈ W .
(iii) For any increasing sequence {vn }∞n=1 ⊂ W with limn↑∞ vn ∈ V , wehave limn↑∞ vn ∈ W .
Then v ∗ ∈ W .

11

Proof. Let v and W be as above. For n ∈ N, let v n = B n v, and let v ∗ =limn↑∞ v n . By Theorem 2.2, we have v ∗ = v ∗ . Since v ∈ W by condition(i), and since the sequence {B n v} is increasing by (2.14), we have v n ∈ W
for all n ∈ N by condition (ii). By condition (iii), we have v ∗ ∈ W ; that is,v∗ ∈ W .
To see how the above result can be used in practice, suppose that one
wishes to establish that the value function has a certain property, say property (P). One can do so in four steps as follows:
I. Find a function v ∈ V with property (P) that satisfies (2.14), (2.16),
and (2.19).
II. Show that if a function v ∈ V has property (P) and satisfies Bv ≥ v,
then Bv also has property (P).
III. Show that for any increasing sequence {vn } such that each vn has
property (P), limn↑∞ vn also has property (P).
IV. Using Corollary 3.8, conclude that the value function v ∗ has property(P).
This type of argument is not new (e.g., Stokey and Lucas, 1989, p. 52;
Amir et al., 1991, p. 637), but note that it is the convergence result in
Theorems 2.1 and 2.2 that makes the above procedure work. In Subsection
4.2, we apply a slightly different version of this procedure to an optimal
growth model with “roughly increasing” returns.

3.3

Comparison with the Result Shown by RincónZapatero and Rodrı́guez-Palmero/Martins-da-Rocha
and Vailakis

We now compare Theorem 2.1 with Martins-da-Rocha and Vailakis’ (2010,
Sec. 3) result on the Bellman operator, which is built upon the work of
Rincón-Zapatero and Rodrı́guez-Palmero (2003, 2009). Under numerous
technical conditions, their result shows that the Bellman operator has aunique fixed point in a certain set of continuous functions, that this fixed
point is the value function, and that value iteration converges locally uniformly to the value function starting from any continuous function in thegiven function set. Since our result does not establish any property of thevalue function and ensures only pointwise convergence from a specific initial12

function, the conclusions of our result are weaker in some directions. However, our result, which requires only a small subset of the conditions requiredby their result, is considerably simpler to apply. This point immediately
becomes clear in what follows.
The result stated by Martins-da-Rocha and Vailakis (2010, Theorem 3.1)
requires the assumptions listed below:
DP0. (i) X = Rm
+ for some m ∈ N. (ii) β ∈ (0, 1). (iii) The right-hand sideof (2.5) with L = lim exists in R for all {xt }∞t=0 ∈ Π.
DP1. The feasibility correspondence Γ is continuous and compact-valued.
DP2. The return function u is continuous on D.
Let C(X, [−∞, ∞)) be the set of continuous functions from X to [−∞, ∞).
Under DP0(i), we define
X ∗ = X \ {0},C ∗ (X) = {v ∈ C(X, [−∞, ∞)) : ∀x ∈ X ∗ , v(x) > −∞}.

(3.9)
(3.10)

Although DP2 requires u to be continuous, it is allowed that u(x, y) = −∞for some (x, y) ∈ D. The following assumption requires that one can avoid
u(x, y) = −∞ unless x = 0.
DP3. There exists a continuous function q : X ∗ → X ∗ such that∀x ∈ X ∗ ,(x, q(x)) ∈ D,u(x, q(x)) > −∞.

(3.11)

DP4. (i) There exist v, v ∈ C ∗ (X) satisfying (2.13)–(2.15). (ii) We have0∀{xt }∞
t=0 ∈ Π ,lim β t v(xt ) = 0,

(3.12)

0∀{xt }∞
t=0 ∈ Π ,lim β t v(xt ) = 0.

(3.13)t↑∞t↑∞(iii) For any x0 ∈ X ∗ , Π0 (x0 ) 6= ∅. (iv) There exists v̂ ∈ C ∗ (X) such that∀x ∈ X ∗ ,∃ > 0,∃δ > 0,v(x) < v̂(x), (Bv̂)(x) < v̂(x),v(x) − v̂(x)sup< ∞,x∈X ∗ :kxk< v(x) − v̂(x)v(x) − v̂(x)< ∞,x∈X ∗ :kxk<δ (Bv̂)(x) − v̂(x)supwhere k · k is any norm on Rm .
13

(3.14)(3.15)(3.16)

DP5. There exists an increasing sequence {Kj }∞j=1 of compact subsets of X
such that Γ(Kj ) ⊂ Kj for each j ∈ N, and such that for any compact set
K ⊂ X, there exists j ∈ N with K ⊂ Kj .
We are now ready to present the result stated by Martins-da-Rocha andVailakis (2010):
Theorem 3.1. (Martins-da-Rocha and Vailakis, 2010, Theorem 3.1)
Under DP0–DP5, the following conclusions hold:(a) The Bellman operator B has a unique fixed point in [v, v] ∩ C ∗ (X).
(b) The unique fixed point of B in [v, v] ∩ C ∗ (X) is the value function v ∗ .
∗(c) For any v ∈ [v, v] ∩ C ∗ (X), the sequence {B n v}∞
n=1 converges to v in∞the topology generated by the family {dj }j=1 of semidistances defined for
all f, g ∈ [v, v] ∩ C ∗ (X) bydj (f, g) =supx∈Kj \{0}lnf (x) − v̂(x)g(x) − v̂(x)− ln,v(x) − v̂(x)v(x) − v̂(x)j ∈ N. (3.17)

Let us compare the conclusions of Theorem 2.1 with those of Theorem 3.1
under DP0–DP5 (which imply the hypotheses of Theorem 2.1 by Corollary
3.9 below). In terms of the existence of a fixed point, Theorem 2.1 is weaker
than Theorem 3.1 in the sense that the latter shows that the fixed point lies inC ∗ (X) (and thus the value function v ∗ is continuous). In terms of uniqueness,
Theorem 2.1 is stronger than Theorem 3.1, which ensures uniqueness only in[v, v] ∩ C ∗ (X). In terms of convergence, Theorem 2.1 is considerably weaker
than Theorem 3.1, which shows that convergence to v ∗ occurs from any initial
function in [v, v] ∩ C ∗ (X) under a criterion much stronger than ours.
Let us now clarify which parts of DP0–DP5 are needed for the conclusionsof Theorem 2.1. The following is a corollary of Theorem 2.1.
Corollary 3.9. Assume DP0(i), DP0(ii), DP4(i), (3.12), and DP5. Thenthe functions v and v given by DP4(i) satisfy (2.13)–(2.17), and thus conclusions (a)–(c) of Theorem 2.1 hold.
Proof. DP4(i) ensures (2.13)–(2.15). Condition (3.12) implies (2.16). To
verify (2.17), let {xt }∞t=0 ∈ Π. By DP5, there exists a compact set Kj withj ∈ N such that x0 ∈ Kj and Γ(Kj ) ⊂ Kj . Since v is continuous by DP4(i),we have v(xt ) ≤ maxx∈Kj v(x) < ∞ for all t ∈ Z+ , which together with
DP0(ii) implies (2.17).
14

The above result shows that a small subset of the conditions stated in
DP0–DP5 is sufficient to show that the value function v ∗ is the unique fixed
point of the Bellman operator B in [v, v] and that convergence to v ∗ occurs
from v. In the proof, (2.17) is shown as a consequence of DP5 rather than
(3.13). The only role of DP0(i) is to keep C ∗ (X) well defined, while thatof DP5 is to ensure (2.17). Thus DP0(i) can be dropped entirely if we do
not require v, v ∈ C ∗ (X), while DP5 can be replaced by a weaker sufficientcondition for (2.17). The following result can be shown by modifying theproof of Corollary 3.9.
Corollary 3.10. Let β ∈ [0, 1). Suppose that there exist v, v ∈ V satisfying(2.13)–(2.16). Suppose further that for any x ∈ X, there exists a set K ⊂ Xsuch that Γ(K) ⊂ K and supx∈K v(x) < ∞. Then conclusions (a)–(c) of
Theorem 2.1 hold.

4

ExamplesThroughout this section, we assume that β ∈ (0, 1) for simplicity.

4.1

Optimal Growth with Threshold Effects

Azariadis and Drazen (1990, p. 508) define threshold effects as “radical differences in dynamic behavior arising from local variations in social returns toscale,” and explain this idea by using a discontinuous production function.
In this subsection, we consider a one-sector growth model with this feature.
The example here is a special case of the model studied by Kamihigashi andRoy (2007).
Let θ, θ, x̂ > 0 with θ < θ. Consider the production function f : R+ → R
specified by(θx if x < x̂,
f (x) =
(4.1)
θx if x ≥ x̂.
Figure 1 illustrates a production function of this form. We defineu(x, y) = ln[f (x) − y], (x, y) ∈ D,
Γ(x) = {y ∈ R : 0 ≤ y ≤ f (x)}, x ∈ X.
This is clearly a special case of the framework described in Section 2.
15

(4.2)
(4.3)

f HxL

Θx
Θx

x

0

`
x

x

Figure 1: Production function of the form (4.1)
Since the production function f is discontinuous, it is immediately clearthat u is not a continuous function and Γ is not a continuous correspondence.11 Hence any result that requires u and Γ to be continuous is notapplicable here. For example, it is easy to see that this example violates
DP1 and DP2 in Subsection 3.3. It also violates DP5, which rules out unbounded growth.
In contrast, our results are easily applicable. To be specific, defineu(x, y) = ln(θx − y),Γ(x) = {y ∈ R : 0 ≤ y ≤ θx},u(x, y) = ln(θx − y),Γ(x) = {y ∈ R : 0 ≤ y ≤ θx}.

(4.4)
(4.5)

Let B and B be the Bellman operators corresponding to (u, Γ) and (u, Γ),respectively. Then, using the method of undetermined coefficients, it is easy
to show that there exist γ, γ, η, η > 0 such that v = B v and v = Bv withv(x) = γ ln x + η,v(x) = γ ln x + η.

11

(4.6)

By using a different state variable, it is possible to construct a continuous return
function, but the feasibility correspondence cannot be made continuous.

16

In particular,
γ=γ=

1
,
1−β

η=

1
[ln θ + β ln β + (1 − β) ln(1 − β)],(1 − β)2(4.7)

and η is similar.12 It is easy to see that (2.13)–(2.15) hold. It is also easy toverify (2.16) and (2.17) following Rincón-Zapatero and Rodrı́guez-Palmero(2003, Example 12); thus conclusions (a)–(c) of Theorem 2.1 hold.
Note that in the above argument, it was not required to show that v
and v are the value functions corresponding to (u, Γ) and (u, Γ), respectively.
However, one can easily show that v and v are indeed the associated valuefunctions by using Theorem 2.1 or Corollary 3.1.13 In that case, one canapply Corollary 3.6 or 3.7 to obtain the corresponding conclusions.
In this example, the production function is assumed to have only one
discontinuity and to be upper semicontinuous. However, these properties are
not required by our results. Indeed, the above arguments go through as longas the production function lies between θx and θx.

4.2

Optimal Growth with Roughly Increasing Returns

The importance of increasing returns in explaining cross-country differencesin the long run has been well recognized since Romer (1986). In this subsection, we consider an optimal growth model with “roughly increasing” returns,
which is again a special case of the model studied by Kamihigashi and Roy(2007). In particular, we assume that the production function f is continuous and strictly increasing, and that there exist θ, θ ∈ R++ and α ∈ (1, 1/β)
such that(4.8)
θxα ≤ f (x) ≤ θxα .
Figure 2 illustrates a production function of this form, which roughly exhibits increasing returns. We define the return function u and the feasibility
correspondence Γ by (4.2).
In this example, both u and Γ are continuous, but to our knowledge, inthe current literature, there is no result on the convergence of value iteration
12

To derive these values of γ and η, for example, suppose that v takes the form given by(4.6), and solve the maximization problem maxy∈Γ(x) {ln(θx−y)+β[γ ln y+η]}. Substitutethe solution into the objective function, and find the values of γ and η such that the
maximized objective function always equals γ ln x + η.
13
The latter approach is used by Stokey and Lucas (1989, Section 4.4).

17

f HxL

Θ xΑ

Θ xΑ
x

0

Figure 2: Production function of the form (4.8)
that applies to this example. However, our results are easily applicable as in
the previous subsection. To demonstrate this, define u, Γ, u, and Γ by (4.4)
and (4.5) with θxα and θxα replacing θx and θx, respectively. Then following
the procedure in the previous subsection, we see that there exist γ, γ, η, η > 0such that v = B v and v = Bv with v and v given by (4.6); thus we can apply
Theorem 2.1 in the same way. In particular, the increasing sequence {B n v}
converges to v ∗ pointwise.
It follows from Kamihigashi and Roy (2007, Lemma 3.3) that the valuefunction v ∗ here is upper semicontinuous. Let us show that v ∗ is in fact
continuous.14 Since v is continuous, and since the Bellman operator B here
maps a continuous function to another continuous function, B n v is continuous for each n ∈ N. However, we cannot apply Corollary 3.8 here sincecontinuity is not preserved under pointwise convergence. On the other hand,the pointwise limit of an increasing sequence of continuous functions is lower
Note from Le Van and Morhaim (2002) that continuity of v ∗ is not necessarily immediate. One can verify the continuity of v ∗ here by following Le Van and Morhaim (2002,
Theorem 3(iii)), even though their assumptions rule out increasing returns. One can also
verify it more directly using the interiority of optimal paths. However, given that v ∗ is
known to be upper semicontinuous, the following argument seems to be more efficient.
14

18

semicontinuous (e.g., Alipratnis and Border, 2006, Lemma 2.41). This suffices for our purpose since then v ∗ is both upper and lower semicontinuous,i.e., v ∗ is continuous.

4.3

Nonconvergence of {B n v} to v ∗Under (2.13)–(2.17), conclusion (c) of Theorem 2.1 shows that the increasing∗
sequence {B n v}∞
n=1 converges to the value function v pointwise. The natural∗
question is: Does the decreasing sequence {B n v}∞
n=1 also converge to v ? The
answer is no in general.
To verify this, let α ∈ (0, β). Consider the symbolic diagram depicted in
Figure 3; more precisely, assume the following:
X = {(i, j) : i, j ∈ Z+ , j ≤ i},00{(i , 0) : i ∈ Z+ } if (i, j) = (0, 0),Γ((i, j)) = {(i, j)}
if i = j 6= 0,{(i, j + 1)}
if j < i,
if (i, j) = (i0 , j 0 ) = (0, 0),−αu((i, j), (i0 , j 0 )) = −β −i if (i, j) = (i0 , j 0 ) 6= (0, 0),0otherwise.
The value function v ∗ can be computed directly:15(−α/(1 − β)if (i, j) = (0, 0),v ∗ ((i, j)) =−j−β /(1 − β) otherwise.

(4.9)(4.10)(4.11)(4.12)

Let v = v ∗ and v = 0. Then v ≤ v and Bv = v. Since u ≤ 0, we have
Bv ≤ v. Thus (2.13)–(2.15) hold. As any feasible path eventually becomes
constant, (2.16) and (2.17) hold with equality. Hence Theorem 2.1 applies.
n∞Consider the decreasing sequence {v n }∞n=1 ≡ {B v}n=1 . If (i, j) 6= (0, 0),
there is only one feasible transition from (i, j), so that v n ((i, j)) can be comLet i ∈ N. Then at state (i, i), we have v ∗ ((i, i)) = −β −i /(1 − β). Note that v ∗ ((i, i −k)) = β k v ∗ ((i, i)) for k = 1, . . . , i; thus v ∗ ((i, j)) = −β i−j v ∗ ((i, i)) = −β −j /(1 − β). It
remains to compute v((0, 0)). If xt = (0, 0) for all t ∈ Z+ , then S({xt }∞t=0 ) = −α/(1 − β).
∗If x1 = (i, 0) with i > 0, then S({xt }∞t=0 ) = βv ((i, 0)) = −β/(1 − β) < −α/(1 − β). Hence
it is never optimal to leave state (0, 0), so that v ∗ ((0, 0)) = −α/(1 − β).
15

19

-Β-3

3, 3
-2

-Β

0

2, 2

3, 2

0

0

1, 1

2, 1

3, 1

0

0

0

2, 0

3, 0

-Β-1

-Α

0, 0

0

1, 0
0

0

0

Figure 3: States (i, j) ∈ X (circles), feasible transitions (arrows), and associated returns (values adjacent to arrows) under (4.9)–(4.11)

20

puted directly:(
Pn−(i−j)−1 k
β−β −j k=0v n ((i, j)) =0

if i > 0 and n ≥ i − j + 1,
otherwise.

(4.13)

This formula works for (i, j) = (0, 0) as well; i.e., v n ((0, 0)) = 0 for alln ∈ N.16
Now letting v ∗ = limn↑∞ v n , we see that v ∗ ((i, j)) = v ∗ ((i, j)) for all(i, j) ∈ X \ {(0, 0)}, but v ∗ ((0, 0)) = 0 > v ∗ ((0, 0)); i.e., the sequence {v n }∞n=1
fails to converge to v ∗ at (0, 0).
∗∗Interestingly, the sequence {B n v ∗ }∞t=1 restarted from v converges to v .
Indeed, (B n v ∗ )((0, 0)) = −α(1 + β + · · · + β n−1 ) → v ∗ ((0, 0)) as n ↑ ∞.

5

Concluding Remarks

In this paper, we have established some elementary results on solutions to
the Bellman equation—or fixed points of the Bellman operator—without
introducing any topological assumption. Our main results are twofold. First,
given an order interval of functions that is mapped into itself by the Bellman
operator, if the upper and lower boundaries of the order interval satisfy
transversality-like conditions, then (a) the Bellman equation has a uniquesolution in this order interval, (b) this solution is the value function, and(c) the value function can be computed by value iteration starting from thelower boundary of the order interval. Second, if there exists a function that is
mapped upward by the Bellman operator, and if this function is dominatedby the value function and satisfies a transversality-like condition, then thevalue function can be computed by value iteration starting from this function.
As a consequence of these results, we have derived various known results toclarify how our results relate to existing ones. We have applied our results
to two optimal growth models, one with a discontinuous production function
and the other with “roughly increasing” returns. We have also presented
an example to show that even under the conditions of our first main result,value iteration starting from the upper boundary of the order interval neednot converge to the value function.
16

To see this, define v 0 = v = 0. Then v 0 ((0, 0)) = 0. Let n ∈ Z+ . With v n given by(4.13), we have v n+1 ((0, 0)) = β supi∈X v n ((i, 0)) = 0 since v n ((i, 0)) = 0 for all i ≥ n. By
induction, v n ((0, 0)) = 0 for all n ∈ N.

21

Our results are elementary in the sense that they do not require any
knowledge of mathematics beyond undergraduate analysis. Therefore, they
are highly accessible to applied researchers as well as graduate students.
Even in situations where standard topological assumptions hold, our results
are considerably simpler than most of the existing results on fixed points of
the Bellman operator. In addition, our results, which require no topologicalassumption, apply to models with discontinuities and even to those with“roughly increasing” returns.
In sharp contrast to the existing results based on variants of the contraction mapping theorem, our results directly establish virtually no property ofthe value function. Regarding this matter, we have shown how the increasing, convergent sequence given by our results can be used to derive certain
properties of the value function. We plan to pursue applications of this idea
as well as extensions to stochastic models in future research.

Appendix A
A.1

Proofs

Proof of Theorem 2.1

The proof consists of three lemmas and a concluding argument. The proof of
the first lemma slightly generalizes an argument of Stokey and Lucas (1989,
Theorem 4.3). The second lemma essentially shows that B T v with T ∈ N
and v ∈ V is the value function of the T -period problem with the valueof the terminal stock xT given by v(xT ). This result extends the classicalidea of Bertsekas and Shreve (1978, Section 3.2) to our setting. The lastlemma is less trivial than the first two. The concluding argument applies theKnaster-Tarski fixed point theorem and combines the first and last lemmas.
Lemma A.1. Let v ∈ V satisfy (2.17). Let v ∈ V be a fixed point of B withv ≤ v. Then v ≤ v ∗ .
Proof. Let x0 ∈ X. If v(x0 ) = −∞, then v(x0 ) ≤ v ∗ (x0 ). Consider
case
P∞ thetv(x0 ) > −∞. Let  > 0. Let {t }∞
⊂
(0,
∞)
be
such
that
β

≤
.
t
t=0
t=0
Since v = Bv, for any t ∈ Z+ and xt ∈ X, there exists xt+1 ∈ Γ(xt ) such thatv(xt ) ≤ u(xt , xt+1 ) + βv(xt+1 ) + t .

(A.1)

We pick x1 ∈ Γ(x0 ), x2 ∈ Γ(x1 ), . . . so that (A.1) holds for all t ∈ Z+ . Then{xt }∞
t=1 ∈ Π(x0 ). By repeated application of (A.1), we havev(x0 ) ≤ u(x0 , x1 ) + βv(x1 ) + 0
22

(A.2)

≤ u(x0 , x1 ) + β[u(x1 , x2 ) + βv(x2 ) + 1 ] + 0
..
.
T −1
X

≤

β t u(xt , xt+1 ) + β T v(xT ) + ,

∀T ∈ N.

(A.3)
(A.4)
(A.5)

t=0

Since v(x0 ) > −∞, we have β T v(xT ) > −∞ for all T ∈ N. It follows thatTv(x0 ) −  − β v(xT ) ≤T −1
X

β t u(xt , xt+1 ).

(A.6)

t=0

Applying limT ↑∞ to both sides and recalling (2.5) and (2.6), we haveTv(x0 ) −  − lim β v(xT ) ≤ lim
T ↑∞

T −1
X

T ↑∞ t=0∗
β t u(xt , xt+1 ) ≤ S({xt }∞t=0 ) ≤ v (x0 ).

(A.7)
By (2.17), we have v(x0 ) −  ≤ v (x0 ). Since this is true for any  > 0, we
have v(x0 ) ≤ v ∗ (x0 ). Since x0 is arbitrary, we obtain v ≤ v ∗ .
∗For any v ∈ V , define v1 = Bv; for each n ∈ N, provided that vn ∈ V ,define vn+1 = Bvn . The following remark follows from (2.11).
Remark A.1. Let v, w ∈ V satisfy v ≤ w and Bw ≤ w. Then for all n ∈ N,
we have vn ≤ w and thus vn ∈ V .
Lemma A.2. Let v ∈ V satisfy (2.15). Let v ∈ V satisfy v ≤ v. Then for
any T ∈ N, we have vT ∈ V and
(T −1
)
X
∀x0 ∈ X, vT (x0 ) =supβ t u(xt , xt+1 ) + β T v(xT ) . (A.8){xt }∞
t=1 ∈Π(x0 )t=0

Proof. Note from (2.15) and Remark A.1 with w = v that vn ∈ V for alln ∈ N. For any x0 ∈ X, we havev1 (x0 ) =sup {u(x0 , x1 ) + βv(x1 )}(A.9)

x1 ∈Γ(x0 )

=

sup

sup

{u(x0 , x1 ) + βv(x1 )}(A.10)

x1 ∈Γ(x0 ) {xt }∞t=2 ∈Π(x1 )=sup{u(x0 , x1 ) + βv(x1 )},{xt }∞
t=1 ∈Π(x0 )23(A.11)

17
where (A.10) holds because {u(x0 , x1 ) + βv(x1 )} is independent of {xt }∞t=2 ,and (A.11) follows by combining the two suprema (see Kamihigashi, 2008,
Lemma 1). It follows that (A.8) holds for T = 1.
Now assume (A.8) for T = n ∈ N. For any x0 ∈ X, we havesup {u(x0 , x1 ) + βvn (x1 )}vn+1 (x0 ) =(A.12)

x1 ∈Γ(x0 )(=u(x0 , x1 )sup(A.13)

x1 ∈Γ(x0 )

+β

n−1
nX

sup

{xi+1 }∞
i=1 ∈Π(x1 )

=

sup

sup

i=0
(
n
X

x1 ∈Γ(x0 ) {xi+1 }∞i=1 ∈Π(x1 )

=

( n
X

sup
{xt }∞
t=1 ∈Π(x0 )β i u(xi+1 , xi+2 ) + β n v(xn+1 ))o)

β t u(xt , xt+1 ) + β n+1 v(xn+1 )(A.14)

t=0)
β t u(xt , xt+1 ) + β n+1 v(xn+1 ) ,(A.15)

t=0

where (A.13) uses (A.8) for T = n, (A.14) holds because u(x0 , x1 ) is independent of {xi+1 }∞i=1 , and (A.15) follows by combining the two suprema (seeKamihigashi, 2008, Lemma 1). It follows that (A.8) holds for T = n + 1. By
induction, (A.8) holds for all T ∈ N.
Lemma A.3. Let v, v ∈ V satisfy (2.13)–(2.16). Then v ∗ ≡ limT ↑∞ v T ≥v ∗ .18
Proof. Note from (2.13)–(2.15), (2.11), and Remark A.1 that {v T }∞T =1 is anincreasing sequence in V . Thus for any x0 ∈ X, we havev ∗ (x0 ) = sup v T (x0 )(A.16)

T ∈N

= sup

(T −1
X

sup

T ∈N {xt }∞t=1 ∈Π(x0 )

=

sup

sup

T ∈N
{xt }∞
t=1 ∈Π(x0 )
17
18

t=0
(T −1
X

)
β t u(xt , xt+1 ) + β T v(xT )(A.17))

β t u(xt , xt+1 ) + β T v(xT )t=0This step uses the assumption that Γ is nonempty-valued.
Here v T = B T v for all T ∈ N and v ∗ (x) = limT ↑∞ v T (x) for all x ∈ X.

24

(A.18)

≥

sup

(T −1
X

L

T ↑∞
0
{xt }∞
t=1 ∈Π (x0 )

(
≥

L

sup
0
{xt }∞
t=1 ∈Π (x0 )

≥

sup

T ↑∞

L

{xt }∞ ∈Π0 (x ) T ↑∞
t=1

0

t=0
T
−1
X

)
β t u(xt , xt+1 ) + β T v(xT )(A.19))

β t u(xt , xt+1 ) + lim β T v(xT )(A.20)

T ↑∞

t=0
T
−1
X

β t u(xt , xt+1 ) = v ∗ (x0 ),(A.21)

t=0

where (A.17) uses Lemma A.2, (A.18) follows by interchanging the twosuprema (see Kamihigashi, 2008, Lemma 1), (A.19) holds because Π0 (x0 ) ⊂Π(x0 ) (recall (2.8)) and LT ↑∞ aT ≤ supT ∈N aT for any sequence {aT } in[−∞, ∞), (A.20) follows from the properties of lim and lim,19 and the inequality in (A.21) uses (2.16). It follows that v ∗ ≥ v ∗ .
To complete the proof of Theorem 2.1, suppose that there exist v, v ∈ V
satisfying (2.13)–(2.17). The order interval [v, v] is partially ordered by ≤(recall (2.10)). Given any F ⊂ [v, v], we have sup F ∈ [v, v] because∀x ∈ X,(sup F )(x) = sup{f (x) : f ∈ F } ∈ [v(x), v(x)].

(A.22)

Since B is a monotone operator, and since B([v, v]) ⊂ [v, v] by (2.13)–(2.15)
and (2.11), it follows that B has a fixed point v in [v, v] by the KnasterTarski fixed point theorem (e.g., Aliprantis and Boder, 2006, p. 16). Sincev ≤ v = Bv, we have v n ≤ v for all n ∈ N by Remark A.1; thus v ∗ ≤ v.20
Since v ≤ v ∗ by Lemma A.1 and v ∗ ≤ v ∗ by Lemma A.3, it follows thatv ≤ v ∗ ≤ v ∗ ≤ v. Hence v = v ∗ = v ∗ . Therefore, v ∗ is a unique fixed pointof B in [v, v]; this establishes conclusions (a) and (b). Finally, conclusion (c)holds because v ∗ = v ∗ .

A.2

Proof of Proposition 2.1

Let v ∈ V satisfy (2.17) and (2.18). Then by Lemma A.1, any fixed point v
of B with v ≤ v satisfies v ≤ v ∗ . Since v ∗ ≤ v and v ∗ is a fixed point of B
by Lemma 2.1, it follows that v ∗ is the largest fixed point of B in [−∞, v].
19

We have lim(at +bt ) ≥ lim at +lim bt and lim(at +bt ) ≥ lim at +lim bt for any sequences{at } and {bt } in [−∞, ∞) whenever both sides are well-defined (e.g., Michel, 1990, p. 706).
20
See footnote 18 for the definitions of v n and v ∗ .

25

A.3

Proof of Therem 2.2

Let v ∈ V satisfy (2.14), (2.16), and (2.19). Since Bv ∗ = v ∗ by Lemma
2.1, (2.13)–(2.15) hold with v = v ∗ . Hence, by Lemma A.3, v ∗ ≥ v ∗ . Sincev ≤ v ∗ , we also have v ∗ ≤ v ∗ . Thus v ∗ = v ∗ . We have verified the second
conclusion. If B has a fixed point v ∈ [v, ∞], then v ∗ = v ∗ ≤ v; thus the firstconclusion also holds.

References
Aliprantis, C.D., Border, K.C., 2006, Infinite Dimensional Analysis: A Hitchhiker’s Guide, 3rd Edition, Springer-Verlag, Berlin.
Algan, Y., Challe, E., Ragot, X., 2011, Incomplete markets and the outputinflation tradeoff, Economic Theory 46, 55–84.
Alvarez, F., Stokey, N.L., 1998, Dynamic programming with homogenous functions, Journal of Economic Theory 82, 167–189.
Azariadis, C., Drazen, A., 1990, Threshold externalities in economic development,” Quarterly Journal of Economics 105, 501–26.
Amir, R., Mirman, L.J., Perkins, W.R., 1991, One-sector nonclassical optimal growth: optimality conditions and comparative dynamics, International Economic Review 32, 625–644.
Bertsekas, D.P., Shreve, S.E., 1978, Stochastic Optimal Control: The Discrete Time Case, Academic Press, New York.
Bloch, F., Houy, N., 2012, Optimal assignment of durable objects to successive agents, Economic Theory 51, 13-33.
Durán, J, 2000, On dynamic programming with unbounded returns, Economic Theory 15, 339—352.
Dutta, P.K., Mitra, T., 1989a, On continuity of the utility function in intertemporal allocation models: an example, International Economic Review 30, 527–536.
Dutta, P.K., Mitra, T., 1989b, Maximum theorems for convex structures with
an application to the theory of optimal intertemporal allocation, Journalof Mathematical Economics 18, 77–86.
Dutta, P.K., Radner, R., 2012, Capital growth in a global warming model:
will China and India sign a climate treaty? Economic Theory 49, 411–
443.
26

Goenka, A., Lin, L., 2012, Infectious diseases and endogenous fluctuations,
Economic Theory 50, 125–149.
Herrera, H., Martinelli, C., 2013, Oligarchy, democracy, and state capacity,
Economic Theory 52, 165–186.
Kamihigashi, T., 2008, On the principle of optimality for nonstationary deterministic dynamic programming, International Journal of Economic
Theory 4, 519–525.
Kamihigashi, T., 2013, An order-theoretic approach to dynamic programming: an exposition, Economic Theory Bulletin, forthcoming.
Kamihigashi, T., Furusawa, T., 2010, Global dynamics in repeated gameswith additively separable payoffs, Review of Economic Dynamics 13,
899–918.
Kamihigashi, T., Roy, S., 2006, Dynamic optimization with a nonsmooth,nonconvex technology: the case of a linear objective function, Economic
Theory 29, 325–340.
Kamihigashi, T., Roy, S., 2007, A nonsmooth, nonconvex model of optimal
growth, Journal of Economic Theory 132, 435–460.
Karp, L., Zhang, J., 2012, Taxes versus quantities for a stock pollutant withendogenous abatement costs and asymmetric information, Economic Theory 49, 371–409.
Le Van, C., Morhaim, L, 2002, Optimal growth models with bounded or unbounded returns: a unifying approach, Journal of Economic Theory 105,
158–187.
Llanes, G., Trento, S., 2012, Paten policy, patent pools, and the accumulation of claims in sequential innovation, Economic Theory 50, 703–725.
Martins-da-Rocha, V.F., Vailakis, Y., 2010, Existence and uniqueness of a
fixed point for local contractions, Econometrica 78, 1127–1141.
Matkowski, J., Nowak, A.S., 2011, On discounted dynamic programming withunbounded returns, Economic Theory 46, 455–474.
Michel, P., 1990, Some clarifications on the transversality condition, Econometrica 58, 705–723.
Muradian, R., 2001, Ecological thresholds: a survey, Ecological Economics
38, 7–24.
Nævdal, R., 2003, Optimal regulation of natural resources in the presence ofirreversible threshold effects, Natural Resource Modeling 16, 305–333.
27

Reis, C., 2013, Taxation without commitment, Economic Theory 52, 565–
588.
Rinćon-Zapatero, J.P., Rodrı́guez-Palmero, C., 2003, Existence and uniqueness of solutions to the Bellman equation in the unbounded case, Econometrica 71, 1519–1555.
Rinćon-Zapatero, J.P., Rodrı́guez-Palmero, C., 2007, Recursive utility withunbounded aggregators, Economic Theory 33, 381–391.
Rinćon-Zapatero, J.P., Rodrı́guez-Palmero, C., 2009, Corrigendum to “Existence and uniqueness of solutions to the Bellman equation in the unbounded case” Econometrica, Vol. 71, No. 5 (September, 2003), 1519–
1555, Econometrica 77, 317–318.
Romer, P., 1986, Increasing returns and long-run growth, Journal of Political
Economy 94, 1002–1037.
Roy, S., Zilcha, I., 2012, Stochastic growth with short-run prediction of shocks,
Economic Theory 51, 539–580.
Schaar, M.v.d., Xu, J., Zame, W., 2013, Efficient online exchange via fiat money,
Economic Theory 54, 211-248.
Stokey, N., Lucas, R.E., Jr., 1989, Recursive Methods in Economic Dynamics, Harvard University Press, Cambridge, MA.
Strauch, R.E., 1966, Negative dynamic programming, Annals of Mathematical Statistics 37, 871–890.

28