is due to B3. Now suppose that x' ≥ y. Then ΓV(y) = C(y-x,y) + D(x) + δV(f(x)) ≤ C(0,y) + D(y) +
δV(f(y)) = C(0,y') + D(y) + δV(f(y)) ≤ C(y'-x',y') + D(x') + δV(f(x')). The first inequality is due to
optimality, the equality follows from B2, and the second inequality is implied by B3 and the fact that V is
nondecreasing. ■
Proof of Lemma 2. a. Let x e X(y) and x' e X(y') for y ≤ y'. Then max[x,x'] ≤ y' and min[x,x'] ≤ y.
Note that D(max[x,x']) + D(min[x,x']) = D(x) + D(x'), and likewise V(f(max[x,x']))+V(f(min[x,x'])) =
V(f(x))+V(f(x')). Since Caa(a,y) + Cay(a,y) ≥ 0 it follows that C(y-x,y) - C(y-min[x,x'],y) ≥
C(y'-max[x,x'],y') - C(y'-x',y'). Hence, 0 ≥C(y-x,y) + D(x) + δV(f(x)) - [C(y-min[x,x'],y) + D(min[x,x']) +
δV(f(min[x,x'])] ≥ C(y'-max[x,x'],y') + D(max[x,x']) + δV(f(max[x,x'])) - [C(y'-x',y') + D(x') + δV(f(x'))]
≥ 0, where the first and last inequalities follow from the principle of optimality. This sequence of
inequalities implies that min[x,x'] e X(y) and max[x,x'] e X(y'). If Caa(a,y) + Cay(a,y) > 0 the middle
inequality above becomes strict when x' < x. This yields a contradiction so it must be that every selection
from the optimal policy correspondence is monotone.
b. The argument is similar to the proof of part a. Let x e X(y) and x' e X(y') < y' for y ≤ y'. We want to
show that max[x,x'] e X(y) and min[x,x'] e X(y'). This follows immediately if x ≥ x' so suppose that
x < x'. Since x' < y' it must be the case that x' ≤ y for all y sufficiently close to y'. The assumption
Caa(a,y) + Cay(a,y) ≤ 0 implies C(y-x,y) + C(y'-x',y') ≥ C(y'-x,y') + C(y-x',y). This is turn yields 0 ≥
C(y-x,y) + D(x) + δV(f(x)) - [C(y-x',y) + D(x') + δV(f(x'))] ≥ C(y'-x,y') + D(x) + δV(f(x')) - [C(y'-x',y') +
D(x') + δV(f(x'))] ≥ 0, where the first and last inequalities follow from optimality. This sequence of
inequalities implies that x' e X(y) and x e X(y'). Hence max[x,x'] e X(y) and min[x,x'] e X(y'). The
assumption that X(y') < y' is necessary to insure that x' is feasible from y e N(y'). ■
22