2. A DYNAMIC PROGRAMMING MODEL

We will first collect a few definitions and results from Markovian dynamic programming (see, e.g., [4,10,11] for a general discussion of dynamic programming). Here, we present only a simple type of dynamic programming model sufficient to cover the aircraft routing problem formulated in Section 3.

The model describes a system that is observed at discrete points of time (stages) n = 1,2,…. At each stage, the system is observed to be in a state s ∈ S. Then, an action a ∈ A is taken and the system moves to a new state s′ = g(s,a,z) ∈ S to be observed at the next stage. Here,

is an external event (disturbance) and

is the state transition function. The state–action pair (s,a) causes costs c(s,a), where

is the cost function. Let (Z_n)_n≥1 be an independent and identically distributed (i.i.d.) sequence of external random variables with values in

and with a known distribution.

We will leave aside questions of measurability and assume, in particular, that the action space A is finite.

If we observe the system for a finite number N of stages (finite-horizon case), actions are chosen according to a policy δ = (f_N,…,f₁), where f_n : S → A is the decision rule for the (N − n + 1)st stage. The reverse numbering of the decision rules simplifies the description of the induction below. Given a starting state X₁ = s from S and a policy δ, the sequence of states X₂,…,X_N is then defined recursively by

With A_n := f_N−n+1(X_n), for a measurable set B ⊂ S, we obtain the simple Markovian dependency

The total expected discounted costs for policy δ = (f_N,…,f₁) and starting state s ∈ S are given by

where β ∈ (0,1] is a given discount factor. As our cost function is nonnegative and the action space is finite, it is well known (see, e.g., [11]) that an optimal policy exists; that is, a policy δ*, with

In fact, the min can be taken over a much larger class of policies than defined above. For (measurable) functions

, we define the one-stage cost operator L by

Problem (2.4) can be solved recursively with the help of the so-called optimality equation for dynamic programs, which in the finite-horizon case reads

We assume throughout that V₀ ≡ 0. A policy δ* = (f_N*,…,f₁*) is optimal iff f_n*(s) selects a minimizing action in (2.6) for s ∈ S,1 ≤ n ≤ N (see, e.g., [11, Cor. 6.2]).

In the infinite-horizon case, we only consider stationary policies δ = (f_n)_n≥1 with f_n ≡ f,n ≥ 1, and we write δ = f for short. With A_k = f (X_k),k ≥ 1, we define the total expected discounted costs by

Again, δ* is called optimal if

It is shown in [11] that there exists an optimal stationary policy that can be obtained from the infinite-horizon optimality equation

f* forms an optimal stationary policy iff f*(·) is a minimizer of (2.9). Moreover, value iteration holds; that is,

For the remainder of the article, we use (2.6) to derive properties for the finite-horizon case with arbitrary horizon N using inductive arguments. These properties then carry over to the infinite horizon case using (2.10).

3. OPTIMAL AIRCRAFT ROUTING AS DYNAMIC PROGRAMMING PROBLEM

We will now specify the elements of the dynamic programming model such that we can deal with the problem of optimal aircraft routing.

We start with the external events Z_n. Let S_n,n ≥ 1, denote the arrival times of airplanes at the airport. We assume that the interarrival times T_n := S_n − S_n−1 ≥ 0 for n ≥ 1, with S₀ := 0 are i.i.d.; that is, the arrivals form a renewal process with some distribution F. Let J be the finite set of possible types of airplane and denote by J_n the type of the nth arriving plane. We assume that the J_n,n ≥ 1, are i.i.d. and independent of the arrival process, with

Then,

taking on values in

, describes the type of the nth arriving aircraft and the following interarrival time. (Z_n)_n≥1 is an i.i.d. sequence; it is the external source of randomness in our model.

We assume that if an aircraft of type j is to land immediately behind an aircraft of type i on the same runway, then there must be a safety distance given as separation time b(i,j) ≥ 0, i,j ∈ J. This means that the beginning of the two landing operations (touchdowns) must be b(i,j) time units apart.

In our model, routing decisions have to be made at the arrival instances S_n of airplanes which define our decision epochs. Let A := {I,II}, where action a = I (a = II) means routing the present airplane to runway I (II). Once an airplane has been routed to a queue, it has to wait there for its service. The queues work on a first-come first-served basis.

To define the “state” of our system, we first consider a single runway, say runway I. Of course, things are completely analogous on runway II. Let ζ_n^I denote the type of airplane that is at the tail of the queue of runway I immediately before the nth arrival takes place. If queue I is empty at that time, then ζ_n^I is the type of the last airplane that landed on I. With ζ₁^I := i₀ (an arbitrary type), the formal definition of ζ_n^I is

For n ≥ 2, ζ_n^I is the type of plane that the nth plane will see as its predecessor if it is routed to runway I. Note that the index n counts arrivals to the airport, not to the particular runway.

Let U_n^I denote the workload on runway I immediately before the arrival of the nth airplane. U_n^I is the time that the last plane at the tail of the queue has to wait until the beginning of its landing operation. If the queue is empty at that time, then U_n^I < 0 denotes the time that has passed since the last plane began its landing on runway I.

Let b* := max_i,j∈J b(i,j). With U₁^I := −b*, the formal definition of the workload is given by

Note that

is the waiting time of the nth plane if it is routed to I. Here, b(ζ_n^I,J_n) can be regarded as the service time of this plane. The definitions of ζ₁^I and U₁^I guarantee that the first aircrafts on each runway have waiting time 0. In Figure 3.1 the load on runway a is shown at the arrival instance of the nth aircraft of type j₄ when two aircrafts of types j₂ and j₃ are already waiting. The black triangles indicate the time at which the landing operation of the aircraft begins. Type j₁ has already landed, but j₂ still has to wait.

The load on runway a when aircrafts of types j1,…,j4 are present.

The state of runway I at the arrival instance of the nth plane is the pair (ζ_n^I,U_n^I) taking on values in

. Note that it is possible to bound the workload from below, as we need not keep track of negative loads that are larger than b* = max_i,j∈J b(i,j).

The state of the second runway is defined in a completely analogous way and the state of the system at the nth arrival instance is then defined as

taking on values in the state space

.

Note that, in this model, the presently arriving type J_n is not part of the state but part of the external event Z_n = (J_n,T_n+1) that drives the system. This follows from our particular restriction that the type J_n is not known to the decision-maker. In Section 6, in the case where J_n is known, we will use (J_n+1,T_n+1) as the external event driving the system.

From (3.2) and (3.3), we now see how the state transition function

must be defined. For

, let

As one-stage cost function

we define for s = (i,u,j,v) ∈ S,

If we denote by

the waiting time of the nth airplane, then we have

Note that c((i,u,j,v),a) depends only on the state of runway a [e.g., on (i,u) for a = I]. The total discounted expected costs now read

and similarly for the infinite horizon. Starting in an empty system means to have X₁ = s₀ := (i₀,−b*,i₀,−b*). As we have only two actions, the optimality equations (2.6) and (2.9) have a particularly simple structure:

Also, (2.5) becomes

where F is the distribution of the interarrival times.

4. MONOTONICITY PROPERTIES OF OPTIMAL POLICIES

In this section, we show that optimal routing policies are monotone with respect to a particular (partial) ordering of the state space. As usual, “increasing” and “decreasing” are used in the nonstrict sense.

Let us first define a partial ordering on the set of types J. For i,j ∈ J, define

In the aircraft setting, i [pr ]_J j could indicate that j is a heavier plane that requires more separation than i. We do not make any assumptions on the ordering of the separation times; hence, in the extreme case, it could happen that i [pr ]_J j only holds for i = j.

Now, let s = (i,u,j,v) and s = (i,u,j,v) ∈ S; then, we define

If s [pr ] s holds, then, in state s, the load on runway I is at least as high as in state s, and at its tail, there is an aircraft that requires at least as much separation time as in s. For runway II, the opposite relation holds. Hence, the balance of the two queues is more favorable for I in state s than it is in s.

A function f : S → M, where (M, ≤) is a (partially) ordered set, is called s-increasing if s [pr ] s implies f (s) ≤ f (s). For f_n : S → A, we define the order “≤” on A by I ≤ II. Note that

is s-increasing if and only if

Here, monotonicity in i and j is defined w.r.t. the ordering (4.1), whereas monotonicity in u and v is w.r.t. the usual ordering on

.

The following theorem is the main result of this section. It shows that optimal policies are monotone w.r.t. to the ordering (4.2) of the state space. Some implications are described below.

Theorem 4.1:

In fact, any optimal policy is monotone in this sense if we agree to choose the smaller action I in cases where both actions are minimizing the optimality equations. Theorem 4.1 states that if it is optimal to route the next airplane to runway II in a state s = (i,u,j,v), then we should do the same in all states s with s [pr ] s.

Note that f_n is s-increasing if and only if there exists a “level” function

with i [map ] l_n(i,j,v) decreasing and j,v [map ] l_n(i,j,v) increasing such that for s = (i,u,j,v) ∈ S,

(for the “only if” part, put l_n(i,j,v) := inf{u| f_n(i,u,j,v) = II}). In this sense, an s-increasing policy is a “switching policy.”

The proof of Theorem 4.1 is quite lengthy and only its main steps are given here; the remainder is split into several technical lemmata given in Section 7.

Proof:

5. WHEN IS JOIN-THE-LEAST-LOAD OPTIMAL?

A natural simple policy would be to route the next arriving airplane to the runway with the least load; that is, for s = (i,u,j,v), to decide according to δ = (f_N,…,f₁), where

However, due to the structure of the service times b(i,j), one cannot expect this policy to be optimal in general. We now examine some special cases where JLL is optimal. First, we state a simple consequence of the symmetry of the two runways.

Lemma 5.1: Let s := (i,u,j,v) ∈ S and s := (j,v,i,u); then, we have

For finite and infinite horizon it holds that action I is optimal in state s iff action II is optimal in state s.

Proof: From (3.5), we see that c(s,I) = c(s,II). Starting with V₀ ≡ 0, we obtain inductively, using (3.4),

hence,

The corresponding results for the infinite horizon follow from (2.10) and (2.9). █

The following theorem is a direct consequence of Theorem 4.1 and the symmetry of the runways. It shows, in particular, that it is optimal to use JLL in states where both runways have identical types waiting at their tails. Note that we use the ordering defined by (4.1) on the set J of types.

Theorem 5.2:

These statements hold for the finite-horizon as well as for the infinite-horizon problem.

Proof: (a) Let s := (j,v,i,u); then, using Lemma 5.1, we have

The assumptions u ≤ v and i [pr ]_J j imply s [pr ] s, and from Lemma 7.3, we obtain Δ_n(s) ≤ Δ_n(s) = −Δ_n(s). Hence, Δ_n(s) ≤ 0 (i.e., action I is optimal). An analogous argument holds for the infinite-horizon case. The assertion concerning action II follows from symmetry.

Parts (b) and (c) follow from part (a). █

A degenerate special case is obtained if the separation times do not depend on the leading aircraft [i.e., b(i,j) ≡ d(j) for all i,j ∈ J]. In this situation, it is unnecessary to keep track of the type of the last airplanes on the runways and the state space of the problem could be reduced to the load (u,v) on the two runways. Theorem 4.1 then implies that the JLL policy δ is optimal.

Corollary 5.3: If b(i,j) ≡ d(j) for all i,j ∈ J, then it is always optimal to route the next airplane to the runway with least load (for finite as well as infinite horizons).

Proof: We have for all i,j ∈ J,

hence, all types in J are equal with respect to the ordering given by (4.1). However, then the assertion follows from Theorem 5.2b. █

Finally, we give a crude error bound on how much the waiting times under policy JLL can deviate from the optimum in the general model. With b* = max_i,j∈J b(i,j) as earlier and b_* := min_i,j∈J b(i,j), let

be the span of separation times.

Theorem 5.4: Let δ be the JLL policy as defined in (5.1). For all s ∈ S, it holds that

and for the infinite horizon and β < 1,

For the proof, we have to consider auxiliary systems with the only difference being modified separation times

. Note that, in these systems, we not only have a different cost function

(related to the separation times as given by (3.5)) but also a different transition function

and a different state process

The value functions for the modified system are denoted by

and so on.

Lemma 5.5:

Proof: (a) The proof is done by induction on N. For N = 0, the statement is trivially true. Now, suppose it holds for

; that is,

is valid for all s ∈ S. We know that

and similarly for

. From our assumptions and the induction hypothesis, we obtain (note that s [map ] V_n(s) is obviously increasing in u and v, which can be shown by induction)

and similarly

, which implies the result.

(b) Let

be the kth action under the JLL policy in the original model and in the hat model. Note that we may have

and that

We first prove

Again, for k = 1, nothing has to be shown. Now, assume that (5.5) holds for some k, we have

We see that (5.6) also holds if the outer min is replaced by max; hence, (5.5) is proven. From this, we obtain for all k,

which, in turn, implies

To complete the proof of part (b), we have to show that

Similar to (5.6), we first show that

which, as in (5.7), implies

and, hence, (5.9) follows. To prove (5.10), we first observe that for k = 1, nothing has to be shown. Now, assume (5.10) holds for some k; then,

Again, the same inequalities hold when the outer min is replaced by max. Hence, (5.10) holds and the proof of the lemma is complete for finite horizons. The infinite-horizon case again follows from (2.10). █

For the proof of Theorem 5.4, we consider first an auxiliary system with

whose value function will be denoted by _*V_N(s). Similarly, the system with

has value function *V_N(s). From Corollary 5.3, we know that JLL is optimal in these systems; hence, from Lemma 5.5, we see

Now, we apply Lemma 5.5b to the two value functions _*V_Nδ and *V_Nδ with fixed separation times. We obtain

which, together with (5.12), implies the assertion of Theorem 5.4 for the finite horizon; the infinite-horizon case again follows from (2.10).

6. THE CASE OF COMPLETE INFORMATION: A COUNTEREXAMPLE

In this section, we assume that the controller knows the type of the airplane that has to be routed, in addition to the state of the runways. In this case, the control problem is much more complicated. A simple switching policy as in Section 4 need not be optimal any longer, as we will show by a counterexample.

6.1. The Model

To model the new situation, the type of the newly arrived airplane is now included in the state space; that is, we put

where a state

is denoted by

. k gives the type of the newly arrived airplane and i, u, j, and v are as earlier. As in Section 3, we have an external event z = (l,t), but now l is the type of the airplane to arrive after the next interarrival time t [i.e., Z_n = (J_n+1,T_n+1)]. Using the notation of Section 3, we can write the transition function

for

as

For the cost function

, we now take the (deterministic) waiting time of the newly arrived airplane when routed to runway a; that is,

As in the model of Section 3, the optimality equation of the finite-horizon dynamic program is given by

where for

,

and

6.2. A Counterexample

The following example shows that a monotonicity result similar to that of Theorem 4.1 cannot hold in the present scenario. More precisely, if routing the airplane to runway I in state

is optimal, then it need not be optimal to route the airplane to runway I in a state s = (k,i,u,j,v), where u < u. Hence, with respect to any (partial) ordering “[pr ]” of

, which has

for the above states, monotonicity as in Theorem 4.1 need not hold. As a consequence, Theorem 5.2, Corollary 5.3, and Theorem 5.4 are no longer valid, although Lemmas 5.1 and 5.5 hold.

The counterexample has a very small u < 0; that is, the last touchdown on runway I was a long time ago. Then, if the current airplane needs only a small safety distance to the preceding one, it might be better to save runway I for a future airplane that needs a larger separation time.

Example: We assume that there are three types of aircraft, J = {1,2,3}, and that the matrix of separation times is as given in [6]:

Let F(t) := 1 − e^−t; that is, we assume that the arrivals form a Poisson stream with rate λ = 1.

For a planning horizon of 2 (i.e., N = 2), we obtain from (6.3) and (6.4) for the difference of the expected cost between routing to I and routing to II in state

Now, assume that we are in state

. Then, we have

, and from (6.5), singling out type 3,

for a constant C₁ not depending on p₃. For p₃ large enough, we therefore have

; that is, it is optimal to route to runway I.

Now, let s := (1,1,−144,2,−72); then, u = −144 < −96 = u, but

again for a constant C₂ not depending on p₃. This time we have

for p₃ large enough; that is, in state s, it is optimal to route to II. Hence, for any ordering [pr ] on

where u < u implies

need not be s-increasing.

7. THE MONOTONICITY OF s [map ] Δ_n(s)

In this section, we complete the proof of Theorem 4.1. We are using the model of Section 3; that is, s = (i,u,j,k) and Z_n = (J_n,T_n+1).

Let us first introduce some notation that allows one to describe the behavior of the system under fixed sequences of actions and external events. For k ≥ 0, let

be defined by

Let

. We denote the components of the state g^k(s,a,z) in the following way:

g^k(s,a,z) is the state after k stages, starting in state s ∈ S, applying actions a ∈ A^k, and given that the external events

were observed. Then, for example, h_I^k = h_I^k(s,a,z) denotes the load on runway I and τ_II^k = τ_II^k(s,a,z) is the type of airplane at the tail of queue II at that time.

We make extensive use of ideas from [1]. In [1], a more general state transition mechanism is considered. There, the transition function g depends on the action a only via an additional random event y whose distribution q_a is controlled by a. Our approach is the special case where q_I and q_II are distinct one-point measures (cf. Lemma 2.3(i) in [1]). In [1] it is shown inductively that s [map ] Δ_n(s) is increasing with respect to some partial order on S under a number of conditions. Translated into our context the following conditions are used:

C.3. g²(s,I,II,z,z′) ≥ g²(s,II,I,z,z′) for all

.

C.4. s [map ] [c(s,I) + βc(g(s,I,z),II) − c(s,II) − βc(g(s,II,z),I)] is s-increasing for all

.

C.5. s [map ] [c(g^k(g²(s,I,II,z,z′),a,z),a) − c(g^k(g²(s,II,I,z,z′),a,z),a)] is s-increasing for all

.

Note that conditions C.3 and C.5 examine the permutation of actions I and II in the first two stages, with the rest of the actions and all external events fixed.

It turns out that these assumptions do not hold in our context. Instead, we need slightly modified conditions C.3–C.5 which differ from the above only in that we permute the two first actions as well as the two first external events. We therefore use C.1, C.2, and the following:

C.3*. g²(s,I,II,z,z′) ≥ g²(s,II,I,z′,z) for all

.

C.4*. s [map ] [c(s,I) + βc(g(s,I,z),II) − c(s,II) − βc(g(s,II,z′),I)] is s-increasing for all

.

C.5*. s [map ] [c(g^k(g²(s,I,II,z,z′),a,z),a) − c(g^k(g²(s,II,I,z′,z),a,z),a)] is s-increasing for all

.

We will refer to the set {C.1, C.2, C.3*, C.4*, C.5*} of modified conditions as (C*). We now have to show (a) that the conditions (C*) hold in our model and (b) that the conclusions of [1], namely that s [map ] Δ_n(s) is s-increasing, hold under (C*).

7.1. Verifying the Conditions (C*)

We start with a lemma.

Lemma 7.1: With the preceding notation, we have for s = (i,u,j,v) ∈ S and for any

, the following:

(a) i [map ] τ_I^k(s,a,z) is increasing (with respect to the ordering defined in (4.1)), τ_I^k does not depend on u, j, and v.

(b) i,u [map ] h_I^k(s,a,z) are increasing; h_I^k does not depend on j and v.

(c) j [map ] τ_II^k(s,a,z) is increasing (with respect to the ordering defined in (4.1)); τ_II^k does not depend on i, u, and v.

(d) j,v [map ] h_II^k(s,a,z) are increasing; h_II^k does not depend on i and u.

Note that u [map ] h_I^k(s,a,z) and v [map ] h_II^k(s,a,z) are also convex.

Proof: (a) With s = (i,u,j,v), we have τ_I⁰(s,a,z) = i, and for k ≥ 1,

Hence, i [map ] τ_I^k is increasing and independent of u, j, and v for fixed a and z.

To prove part (b), we proceed by induction on k ≥ 0. Let k = 0. We put

Then, u,b [map ] H(u,b,t,a) are increasing and convex functions, and with z_k+1 = (l_k+1,t_k+1), we see from (7.1) and (3.4) that

Assume that part (a) holds for k. Then, u,i [map ] h_i^k and u,i [map ] b(τ_I^k(s,a,z),l_k+1) are increasing mappings that do not depend on j,v. From (7.3), it is then obvious that part (b) holds for k + 1.

Parts (c) and (d) follow in the same way. █

Now we can show that conditions (C*) hold in our model.

Lemma 7.2:

Proof:

(a) We have that u,i [map ] [u + b(i,j′)]⁺ are increasing for all j′ ∈ J; hence, from (4.3),

is s-increasing.

(b) This follows from Lemma 7.1.

(c) To prove part (c), we look at the components of g²(s,I,II,z,z′) and g²(s,II,I,z′,z). With z = (l,t) and z′ = (l′,t′), we have τ_I² = l and τ_II² = l′ in both cases, and as [x]⁺ − t ≤ [x − t]⁺, we obtain

In the same way, one shows h_II²(s,I,II,z,z′) ≥ h_II²(s,II,I,z′,z). Hence, part (c) (i.e., C.3*) follows. Note that h_I²(s,II,I,z,z′) = [u − t + b(i,l′)]⁺ − t′, which we cannot relate to h_I²(s,I,II,z,z′) without serious restrictions on the separation times b(i,·). Hence, the original condition C.3 as used in [1] need not hold in our model.

(d) From the definition of the one-stage cost function in (3.5), we have for s = (i,u,j,v), z = (l,t), z′ = (l′,t′),

It is not difficult to see that an expression of the form x [map ] r(x) − βr(x − t) with r increasing and convex and 0 < β ≤ 1 is increasing in x. As u,i [map ] u + b(i,j′) and v,j [map ] v + b(j,j′) are increasing, we see from (4.3) that part (d) holds.

(e) Fix

. Define

Let us assume that a = I. From Lemma 7.1b, we see that

is increasing in the first two coordinates of σ₁ and does not depend on the last two; hence, it is increasing in i and u and does not depend on j and v. Similarly, h_I^k(σ₂,a,z) is increasing in i and u and is independent of j and v. Using Lemma 7.1a, we therefore have

It is not difficult to show that if

is an increasing function and

, then

is increasing. With x = u + b(i,l), we obtain that (7.5) is increasing in i and u and independent of j and v, hence, it is s-increasing. Similarly, for a = II, we see that

is independent of i and u and decreasing in j and v, hence s-increasing. █

7.2. Monotonicity of s [map ] Δ_n(s) Under Conditions (C*)

We now show that Δ_n(s) is s-increasing under our modified conditions. For the sake of completeness, we give a streamlined version of the proofs of [1] here.

Lemma 7.3: Let (C*) hold. For any s ∈ S,n ≥ 0,

Proof: We proceed by induction on n ≥ 0. For n = 0, we have with V₀ ≡ 0 and s = (i,u,j,v)

which is s-increasing by condition C.1. Now, assume that s [map ] Δ_k(s) is s-increasing for all k ≤ n − 1. We will show that the same holds for Δ_n(s). Note that for any

, we have

where we denote

We now obtain for any s ∈ S,n ≥ 1,

From the induction hypotheses and condition C.2, we now infer that s [map ] Δ_n−1(g(s,a,z)) is s-increasing. As [·]⁺ and [·]₋ are monotone functions, we obtain that

is s-increasing. For the proof of the lemma, it is therefore sufficient to show that the remainder of (7.10) is s-increasing; that is,

where ξ is defined in (7.12).

Note that in the second equation of (7.11), we have exchanged Z₁ and Z₂, which is possible because they are i.i.d.. This is a minor change from the derivation in [1] and allows one to use conditions C.3*–C.5*. As Z₁ and Z₂ are also independent of the rest, the monotonicity of (7.11) follows if s [map ] ξ(s,z₁,z₂) is s-increasing for all

, which is shown in the next lemma. █

Lemma 7.4: If s [map ] Δ_k(s) is s-increasing for all k ≤ n, then the following expression is s-increasing for all

:

For the proof of this lemma, we need the following definition: Let R₀(s) := 0, and for

, let

Then, R_k(s,a,z) is the discounted cost over k stages when starting in state s and following a fixed routing policy a, with fixed external events z. Note that g^m depends only on part of the sequences a and z.

Proof of Lemma 7.4:

1. We follow the lines of the proof of Lemma 2.2 in [1]. For

, let

where

are arbitrary fixed sequences. The first half of Φ_k(·) describes the cost from n + 2 stages starting in state s; when in the first k + 2 stages the fixed policy (I,II,a₁,…,a_k) is used, the external events (z,z′,z₁,…,z_k) occur and an optimal policy is used for the remaining n − k stages. The second half of Φ_k(·) interchanges actions I and II and the first two external events z and z′.

2. The main step of the proof is to show that Φ_k is s-increasing for all k = 0,…,n by downward induction on k = n,…,0. The lemma then follows, as Φ₀(s) = ξ(s).

 2.1. For k = n, Φ_n reduces to the expression (7.21) in Lemma 7.5. It is proven there that this expression is s-increasing for any n ≥ 1.

 2.2. Now, assume that Φ_k+1(·) is increasing in s for any sequences

. We want to show that the analogous result holds for Φ_k(·). Let s [pr ] s′ and put

 From C.2 and C.3*, we obtain that σ₁ [pr ] σ₂ and σ₃ [pr ] σ₄. Again, from C.2 follows σ₃ [pr ] σ₁ and σ₄ [pr ] σ₂; hence, we have

 Then,

  2.2.1. We will now show that there is a′ ∈ A with

  To simplify the notation, we put w(s) := V_n−k−1(s). Assume that a ∈ A is optimal in σ₁ and b ∈ A is optimal in σ₄. If a = b, then (7.16) holds for a′ = a. If a ≠ b, then

  Here, the last inequality follows, as it is assumed in this lemma that s [map ] Δ_l(s) is increasing for all l ≤ n; hence, we see from (7.14) that

  In the same way, we obtain

  2.2.2. Inserting the definition of L_a into (7.16), we obtain

  As Φ_k depends only on the first k components of a = (a₁,…,a_k+1), we can choose a_k+1 = a′ to obtain

  and similarly for σ₁,σ₂, and σ₄.

  2.2.3. Returning to (7.15), we obtain from (7.18) and (7.19),

  where the last step follows from the induction hypotheses. █

Lemma 7.5: Let C.4* and C.5* hold. Then, for all k

, the following expression is s-increasing:

Proof: We have from the definition of R_k

The first part of this expression is s-increasing by condition C.4*, the second is a sum of terms which are s-increasing by C.5*. █