Constrained School Choice

by Cases 1 and 2 and Step 2, this is also the last cycle of sr under TTC(Q). Hence,
sr ∈ V (Q, l) and sr ∈ V (Q^r, l), and (9) holds trivially.

Case 4: σ(Q, i_r) < σ(Q^r , i_r) < l. From the proof of Case 3, s_r ∈ V (Q, l) and s_r ∈
V (Q^r, l). Hence, (9) holds trivially.

Case 5: σ(Q^r, ir) = l ≤ σ(Q, ir). Since σ(Q^r, ir) = σ(Q^r, sr) + 1, F(Q^r, l - 1, sr) is the
last cycle of sr under T T C(Q^r). By Case 1, this is a cycle of sr under TTC(Q). In fact,
by Case 1 and Step 2, this is also the last cycle of s_r under TTC(Q). Hence, s_r ∈ V (Q, l)
and s_r ∈ V (Q^r, l), and (9) holds trivially.

Case 6: σ(Q^r, ir) ≤ σ(Q, ir) and l > σ(Q^r, ir). From the proof of Case 5, sr ∈ V (Q, l)
and sr ∈ V(Qr,l). Hence, (9) holds trivially.                                        □□

For each school s_h ∈ C_S , let j_h be the student to which school s_h points in the last
cycle in which sh appears under TTC(Q), i.e., jh := argmax_{j∈Ash (Q)} fs_h (j).

Step 4 For any r ∈ {1, . . . , p}, fs_r (jr) < fs_r (jr+1).

Suppose fs_r (jr) > fs_r (jr+1). From Step 3, jr ∈ As_r (Q) = As_r (Q^r) and in particular,
jr = argmax_{j∈Asr (Q}r₎ fs_r (j). So,

σ(Q^r, jr+1) <σ(Q^r,jr) =σ(Q^r,sr) =σ(Q^r,ir) -1.                 (10)

We will now prove the following claim to complete the proof of this step.

Claim: σ(Q^r, ir) ≤ σ(Q^r, jr+1).

The claim yields a contradiction to (10). Hence, the assumption fs_r (jr) > fs_r (jr+1) is
false. Note jr = jr₊ι. So, f_3r(jr) < f_3r(jr₊ι).                                                 □

Proof of Claim:

Let j'*+ι be the student to which school s_r+1 points in ir’s cycle under TTC(Q), i.e.,
e(Q, σ(Q, ir), s_r+1) = jr₊1. We make the following two observations (O1 and O2).

O1. σ(Q^r,jr*+ι) ≥ σ(Q^r,ir).

[Proof: Suppose σ(Q^r , jr₊₁) < σ(Q^r, ir).

Assume σ(Q^r, ir) ≤ σ(Q, ir). Denote y^r = σ(Q^r, ir). From Lemma B.3(a), V(Q, y^r) =
V(Q^r,y^rr). Bydefinitionof jr₊₁, jr₊₁ ∈ V(Q,y^r). However, by assumption, σ(Q^r, jr₊₁)
< y^r, and hence, jr₊₁ ∈ V(Q^r,y^r) = V(Q,y^r), a contradiction.

So, σ(Q,i_r) < σ(Q^r,i_r). Also note that y := σ(Q,i_r) ≤ σ(Q^r, jr₊₁) (otherwise, by
Lemma B.3(a), jr₊₁ ∈ V(Q,y), contradicting the definition of jr₊₁). By Lemma

42

<<   <   39   40   41   42   43   44   45   >   >>