Our solution of the Bellman equation leads to 4 basic questions:

1. Does V (x) exist?

2. Is the solution unique?
3. How do we …nd the solution?
4. What are the characteristics of the solution (di¤erentiatibility, continuity, etc)?

Answering these questions involves developing additional mathematical expertise. Essentially

we want to consider understand how sequences or functions can converge to a particular point
or function. Some foundations for this (basically vector spaces) were discussed in the …rst
recitation.

Some mathematical preliminaries (metric spaces)

We now consider a brief intoduction to functional analysis.

Definition 4. Let C be the set of continuous and bounded real valued function on X (Con-
tinuous functions are automatically bounded if X is compact, but not if X is arbitrary).

For example suppose that X is the closed interval [ 1; 1], then C is the set of contin-
uous functions on this interval. The function f (x) = x is contained in C but the function
1
g (x) = x
is not in C.

Definition 5. Let : C ! C be a mapping so that

(4) ' = max fu (x; a) + E' [f (x; a; ")]g

a2 (x)

takes one function ' 2 C and maps it to another ' 2 C ( ' 2 C based on our restrictions
on f and Feller’s property).

A solution to the problem in equation 4 is a …xed point of . That is the function

V from the Bellman’s equation satis…es V = V: Before we actually try and …nd the …xed
points to this problem we need to understand a little bit about what it means for something
to converge and this requires learning about metric spaces.

32
Definition 6. Let M be an arbitrary non-empty set and let d be a real valued function on
M M (i.e. d : M M ! R) where d has the properties 8'; ; 2M

1. d ('; ) 0 and d ('; ) = 0 i¤ ' =

2. d ('; ) = d ( ; ')
3. d ('; ) d ('; ) + d ( ; )

We can think of M as the underlying set of a metric space, the elements of M are
often called points (in the space of continuous functions they are functions) and d ('; ) is
called the distance (or norm) between ' 2 M and 2 M . It might help to look at a couple
of examples of metric spaces.

Example 6. Euclidean space <n along with the notion of distance

1
2 2 2
d2 ('; ) = ('1 1) + ::: + ('n n)

is a metric space.

Example 7. C and d1 ('; ) = k' k where k'k = supx2X j' (x)j is a metric space.

This particular de…nition of distance is known as the supnorm.

Metric spaces allow us to consider the concept of convergence.

Definition 7. A sequence f'n g converges to ' in M if 8 > 0 there exists N = N ( ) > 0

such that d ('n ; ') < if n > N

Example 8. De…ne a sequence fxn g1

n=1 where xn =
1
n2
. This sequence converges to x = 0.
1
To show this: pick an arbitrary = N2
> 0 we need to show that there exists N so that
d ('n ; ') < if n > N :
" # 12
2
1 1
d2 ('n ; ') = =
n2 n2
1 1
But, 2
< if n > N
n N2

33
Definition 8. A sequence f'n g 2 M is Cauchy if 8 > 0 there exists N = N ( ) > 0 such
that d ('n ; 'm ) < if n; m > N

Proposition 2. If f'n g converges it is Cauchy.

The proof is quite simple. Given a sequence converges pick a 2
then there exists N
such that d ('n ; ') < 2
and d ('m ; ') < 2
if m; n > N . Using the triangle inequality

d ('m ; 'n ) d ('m ; ') + d ('n ; ') <

Example 9. (or Counter-example) to show the converse is not true for all metric spaces, ie.
Not all cauchy sequences converge. Consider the space of continuous functions on the unit
interval, denoted by C [0; 1]. Take the fn (t) = tn on the unit interval with the distance,
d2 ('; ) : This converges to the discontinuous function
8
< 0 0 t<1
f (t) = ;
: 1 t=1

which is obviously not in C [0; 1]. But it is a cauchy sequence with this notion of distance.

Z 1
1
2
m n n m 2
d2 (t ; t ) = (t t ) dt
0
1 1
1 1 2 2 1 2
= +
2n + 1 2m + 1 n+m+1 N

Altering the notion of distance will alter whether the sequence is even Cauchy. For instance,
suppose we used the supnorm notion of distance, d1 ?

It is often easier to check the Cauchy criterion than convergence. So, if we know
that Cauchy sequences converge on a particular space M then showing a sequence is Cauchy
implies the limit point exist.

Definition 9. A metric space is complete if all cauchy sequences converge

Proposition 3. C - the set of continuous and bounded real valued functions on a compact
subset X with the supnorm - is complete

34
Definition 10. Given a metric space (M; d) and a mapping : M ! M if d ( '; )
d ('; ) for all '; 2 M with 2 (0; 1) then is a contraction mapping.

We would like to show that the Bellman Equation, , is a contraction. Let a solve
equation (4) so that

' = u (x; a) + E' [f (x; a; ")]

= u (x; a) + E [f (x; a; ")] + E f' [f (x; a; ")] [f (x; a; ")]g

max fu (x; a) + E [f (x; a; ")] + E f' [f (x; a; ")] [f (x; a; ")]gg

max fu (x; a) + E [f (x; a; ")]g + max E f' [f (x; a; ")] [f (x; a; ")]g

max fu (x; a) + E [f (x; a; ")]g + sup j' j

+ sup j' j

Now if we rearrange terms then

' sup j' j:

If we reverse the roles of ' and then

' sup j 'j = sup j' j;

but then

sup j 'j sup j 'j ;

d( ; ') d ( ; ') ;

which proves that is a contraction.

Theorem 1. (Contraction Mapping Theorem - CMT) If (M; d) is a complete metric space

and : M ! M is a contraction with modulus then:

1. has exactly one …xed point V 2 M

n n
2. for any V0 2 M , d ( V0 ; V ) d (V0 ; V ) for n = 1; 2; :::

35
Proof. To prove (1) we must …nd a …xed point such that V = V and must show that there
is not another Vb 2 M such that Vb = Vb : De…ne n
x= ( n 1
x) for n = 1; 2; :::Choose
V0 2 M and de…ne fVn g1
n=0

Vn+1 = Vn

Iterating we have

n
Vn = V0

Since is a contraction we have that

d (V2 ; V1 ) = d ( V1 ; V0 ) d (V1 ; V0 )
2
d (V3 ; V2 ) = d ( V2 ; V1 ) d (V2 ; V1 ) d (V1 ; V0 )

continuing to iterate
n
d (Vn+1 ; Vn ) d (V1 ; V0 ) for n = 1; 2; :::

For any m > n

d (Vm ; Vn ) d (Vm ; Vm 1 ) + ::: + d (Vn+1 ; Vn )

m 1 n
+ ::: + d (V1 ; V0 )
n m n 1
+ ::: + 1 d (V1 ; V0 )

now as m n 1 ! 1 this term in brackets converges to 1 which implies that

n
d (Vm ; Vn ) d (V1 ; V0 ) ;
1

so that fVn g is a Cauchy sequence. Since M is a complete metric space, it is the case that
Vn converges to V . We still need to show that V = V (it is a …xed point). In order to do

36
this we note that for all n and V0 2 S

n n
d ( V; V ) d ( V; V0 ) + d ( V0 ; V )
n 1 n
d V; V0 + d ( V0 ; V )

But since both terms on the right hand side converge to zero, it is clear that V =V.
To show that there is no other Vb 2 M such that Vb = Vb ;we suppose that Vb = Vb ;
then

0 < a = d Vb ; V =d Vb ; V d Vb ; V = a

which is not possible since < 1.

We still need to prove the second part of the theorem:

n n 1 n 1
d( V0 ; V ) = d V0 ; V d V0 ; V

Continuing on in this way we get

n n
d( V0 ; V ) d (V0 ; V )

The Contraction Mapping Theorem is also known as the Banach Fixed Point Theorem.
A good treatment of it is in Stokey-Lucas 3.2.
Because C with the supnorm is complete the mapping de…ned for previously will
have a …xed point in C so that there exists a unique V 2 C that solves Bellman’s equation.
Additionally, the second part of the Contraction Mapping Theorem implies that a
sequence de…ned by V0 = 0 and Vn+1 = Vn converges to V in the supnorm. As we can
interpret Vn as the value function constructed using the DP algorithm for the …nite horizon
problem with T = n, V is the limit of the sequence of …nite horizon value functions as the
length of time becomes increasingly longer.
Now what can we say about the decision rules? Well, with n periods to go we can apply
the DP algorithm to …nd a = n (x). Under certain circumstances (if n is a single valued

37
function for su¢ ciently large n) then it is possible to show that n (x) converges pointwise
to the optimal stationary policy for the in…nite horizon problem. If the state variable x is
restricted to a compact set the convergence is uniform. Under these conditions, the in…nite
horizon DP problem is an approximation to a long …nite horizon problem. What’s more, we
can …nd the value function V and a decision rule for the in…nite horizon by iterating on
Bellman’s equation.
We now describe a pair of su¢ cient conditions for to be be a contraction.

Theorem 2. Blackwell’s su¢ cient conditions for a contraction: Let X Rm and let M be
the set of bounded real valued functions f : X ! R with the supnorm, if : M ! M satis…es

1. ' ) ' 8'; 2 C (monotonicity)

2. (a + ') a + ' 8a > 0 and 8' 2 C (discounting)

for < 1 then is a contraction.

The proof is straightforward. You should make sure you can do it.

38
Properties of the value function:
The basic argument we use to determine some properties of the value function given
properties of the primitives (the functions u; ; f; and F ) hinge on the proposition that:

Proposition 4. A closed subset of a complete metric space is a complete metric space.

This implies that showing that maps a closed D C into itself allows us to use
the contraction mapping theorem to the restriction of the mapping to the subset D: With
suitable restrictions on the primitives we can show that ' is increasing whenever ' is
increasing ) the …xed point V (x) is increasing. A similar argument can be used to show
that ' is concave whenever ' is concave ) the …xed point V (x) is concave.
Similar (but more complicated) arguments can be used to show that under certain
restrictions V (x) is strictly increasing, strictly concave and di¤erentiable (or twice di¤eren-
tiable) since these sets are not closed. But, we can make the following two step argument
under certain circumstances. Suppose maps increasing functions into strictly increasing
functions. Then we can use the previous argument to …rst establish V is increasing and then
we can observe it must be strictly increasing because maps the increasing functions into
strictly increasing function V and V = V . Likewise, we can show that the value function
is strictly concave. This is useful since it can be used to show there is a unique solution to
the max problem in Bellman’s equation.
To see how this works, suppose that (x) is convex and u and f are increasing. Then
for any increasing function ' for any two points x2 > x1 and any a0 we have

' (x2 ) u (x2 ; a0 ) + E' (f (x2 ; a0 ; "))

u (x1 ; a0 ) + E' (f (x1 ; a0 ; "))

Maximizing the rhs over a0 we have that ' (x2 ) ' (x1 ) so that is increasing and it
N
takes increasing functions to increasing functions. This implies the V = lim ' is increasing.
Similarly we can show that if u and f are concave in (x; a) as well as increasing in x then V
is also concave.
I only mention this to point out that given a set of primitives there is quite a bit
that we can say about the properties of the value function and the optimal policy rules. In

39
our future work, we will concentrate on problems with primitives that lead to well-behaved
value functions. I encourage everyone to examine Chapter 4 of Stokey-Lucas-Prescott to get
a better understanding why these restrictions are so useful.

Unimprovability
We would like to show that to check a policy is optimal we just need to look at a
one period (one-shot) deviation from that policy. If we have the correct value function and
optimal policy then it is unimprovable. Let the value of following the stationary policy be
W (x; ). Consider the BE

(5) W (x; ) = max fu (x; a) + EW [f (x; a; ") j ]g :

a2 (x)

This problem returns the value of choosing the best value of a now and reverting to the
stationary decision rule next period. If the solution to the maximization problem in equation
(5) is a = (x) for all x then the decision rule is unimprovable in a single step, or
unimprovable for short.
An optimal policy is unimprovable. But is an unimprovable policy optimal? In
other words, if I can’t improve my payo¤ with a one-shot deviation is it true that I can’t
improve my payo¤ with any deviation? Well if u (x; a) is bounded below then we just need
to check a one-shot deviation. In other words,

W (x; ) = W (x; ) = V (x) :

Unimprovability is useful because to show a policy is optimal it su¢ ces to show that there
is no incentive to deviate at a single point in time. To check whether a policy a0 = (x) is
optimal we just need to check that an agent can not do better by choosing a 6= a0 at a single
point in time (for any state variable x). We don’t have to check two, three or more period
deviations.
To see why we need the utility function to be bounded below lets consider the following

40
example

x = f1; 2; 3; :::g , (x) = fC; F g ;

u (C; x) = (1= )x . u (F; x) = 0

x0 = x + 1

W (x0 ; ) = sup fu (x; a) + W (x + 1j )g

a2 (x)

The optimal strategy G = F for all x but the strategy B = C for all x is unimprovable.

W (x; B) = 1

The only way to deviate from B is to deviate for all but a …nite number of periods. But,
since unimprovability only checks one shot deviations it passes the test. The reason then
why a bounded below return function is necessary is then a result of the future being really
terrible, but normally since we discount the future this isn’t a problem if the worse outcome
is bounded below.

C. Examples: Search Models

Let us now consider some problems that …t in well with this framework and yield
some interesting insights. We will spend more time on the economics of these questions later
in the course when we return to consider labor market policies. For now, consider this an
application of dynamic programming.

In…nite Horizon Discrete Choice DP Application - Basic Job Search Model

We want to solve the problem of an unemployed worker that maximizes the discounted
present value of wages and unemployment bene…ts.

X
1
t
max E u (xt ) with 0 < <1
t=0

Each period the worker is unemployed he receives a wage o¤er, ". If he accepts the wage then
he is employed at that wage.

41
Let the current wage be the state variable x. The agent has a choice to accept or reject
the wage o¤er. This implies that the control variable a is an element of the set (x) = f0; 1g.
Where a = 1 implies that the agent accepts the wage o¤er of x and the a = 0 implies that
the agent rejects the wage o¤er of x. If an agent accepts a wage of x then the next period
he does not receive a new wage o¤er, but earns the same wage x. Rejected o¤ers are gone
immediately and accepted o¤ers are retained forever.
Instantaneous return function

u (x; a) = aU (x) + (1 a) U (b)

U 0 > 0; U 00 0
8
< " if at = 0
t
xt+1 = f (xt ; at ; "t ) =
: x if at = 1
t

"t is drawn from F

Note that the distribution of wage o¤ers is invariant to the (x; a). b is a constant and can be
interpreted as unemployment bene…ts.
The value function is the unique V 2 C that solves Bellman’s equation

V (x) = max faU (x) + (1 a) U (b) + EV [f (x; a; ")]g

a2f0;1g

EV [f (x; 1; ")] = U1 (x)

R
EV [f (x; 0; ")] = V (") dF (")

V (x) is the lifetime discounted utility of getting a wage o¤er of x: We know that V (x) is
U (b)
bounded below by 1
and if we assume that the support of the distribution of wage o¤ers
is …nite so that there is [xmin ; xmax ], then we know that lifetime discounted utility is bounded
U (xmax )
above by 1
.
Since the agent is making a discrete choice we can rewrite the value function to take
into account this choice
Z
(6) V (x) = max U (x) + V (x) ; U (b) + V (") dF (")

42
The …rst term in brackets represents the value of accepting the current job at a wage of x and
earning x forever while the second term in brackets represents the value of rejecting the job
being o¤ered at a wage of x: The value of rejecting the job o¤er depends on the current utility
from unemployment bene…ts and the expected value of starting the next period unemployed
but with a di¤erent wage quote.
De…ne the optimal policy (x) as
8 R
< 0 if U (x) + V (x) < U (b) + V (") dF (")
(x) R
: 1 if U (x) + V (x) U (b) + V (") dF (")

A very basic argument can be used to demonstrate that there exists a reservation wage
denoted by w which represents the lowest wage an agent is willing to accept. The value
of rejecting a wage o¤er does not depend on the wage o¤er, so we can de…ne the term
R
V0 = U (b) + V (") dF ("). On the other hand the value of accepting a job quote does
U (x)
depend on the wage being o¤ered and is equal to V1 (x) = 1
. Note V1 (x) is an increasing
function whereas V0 does not depend on x. Consequently, at the reservation wage w it will
be the case that V1 (w ) = V0 and we will have the following optimal policy
8
< 0 if x < w
(x)
: 1 if x w

At the reservation wage the agent is indi¤erent between accepting and rejecting a wage o¤er
and this leads to the following condition:

U (w )
V0 = V1 (w ) =
1

43
Cranking through some algebra leads
Z
V0 = U (b) + V (") dF (")
Z w Z xmax
= U (b) + V0 dF (") + V (") dF (")
xmin w
Z xmax
= U (b) + F (w ) V0 + V (") dF (") + (1 F (w )) (V0 V0 )
w
Z xmax
= U (b) + F (w ) V0 + (1 F (w )) V0 + V (") dF (") (1 F (w )) V0
w
Z xmax
= U (b) + V0 + (V (") V0 ) dF (")
w

Z xmax
(1 ) V0 = U (b) + (V (") V0 ) dF (")
Zwxmax
U (w ) = U (b) + (V (") V0 ) dF (")
Zwxmax
U (") U (w )
= U (b) + dF (")
w 1 1
Z xmax
= U (b) + (U (") U (w )) dF (")
1 w

now we apply Integration by parts to get

Z xmax
U (w ) U (b) = (1 F (")) U 0 (") d"
1 w

This equation has a nice interpretation. The left hand side is the gain in ‡ow utility from
accepting the reservation wage, while the term on the right hand side is the expected bene…t
of searching one more time. The gain from searching is the discounted bene…t of getting a
wage above the reservation wage forever. At the margin, these two must be equal.
Based on this equation we can conduct some comparative statics to understand the
impact of an increase in the discount factor and the unemployment compensation on the
reservation wage. To apply the implicit function theorem we need to rearrange terms so that
Z xmax
H (w ; b; ) = U (w ) U (b) (1 F (")) U 0 (") d" = 0
1 w

44
dH
dw db U 0 (b)
= dH
= >0
db dw U 0 (w ) 1 + (1 F (w ))
1
1
R xmax
dw (1 )2 w
(1 F (")) U 0 (") d"
= >0
d U0 (w ) 1 + (1 F (w ))
1

So increasing the unemployment bene…t leads agents to be more selective in the job they
accept as the reservation wage increases. Similarly, a higher discount factor implies that
agents value the future more, again leading agents to be more selective in the job o¤ers they
accept as well.

Can you …gure out the impact of increasing in the dispersion of o¤ers from a mean pre-
serving spread? That is suppose we choose a new distribution F on support [x0min ; x0max ]
with the mean of F being the same?
How would the problem change if there is some probability, ; of getting …red from a
job?
How would the problem change if you received two o¤ers per period?
Consider a version of the basic model with a Pareto distribution of o¤ers: F (") =
1 (w0 =") for w w0 > 0 and > 1 and risk neutral preferences. Derive the
reservation wage equation.
Show that the basic job search problem (equation 6) is a contraction mapping

45