Constrained School Choice

B.3(b,c), j*₊1 ∈ P(Qr,y,i_r). Hence, σ(Q^r, j*₊1) ≥ y = σ(Q^r,i_r). Again a contra-
diction. So, σ(Q^r,j*₊1) ≥ σ(Q^r, i_r).]

O2. For all i ∈ A^(Q^r) with f^‰) ≤ f^(i), σ(Q^r,i) ≥ σ(Q^r,j^).

Suppose jr+ι ∈ Asr+ι(Q^r). Note fs^(j_r*+ι) ≤ fs^(jr+ι). From O2 (with i = jr+ι) and
O1, σ(Q^r,jr+ι) ≥ σ(Q^r,j^ ≥ σ(Q^r,i_r).

Suppose now jr+1 ∈ As_r+1 (Q^r). Assume σ(Q^r, jr+1) < σ(Q^r, ir). Then,

jr+1 = ir.                                          (11)

We consider two cases.

Case 1: σ(Q^r, i_r) ≤ σ(Q, i_r).

Then, σ(Q^r, jr+1) < min{σ(Q^r, ir), σ(Q, ir)}. From Lemma B.3(a) it follows that σ(Q, jr+1)
= σ(Q^r, jr+1). So,

σ(Q, jr+1) <σ(Q,ir).                               (12)

However, under TTC(Q), i_r is in a cycle with s_r+1 and j_r+1 is in the last cycle of s_r+1.
So, σ(Q, jr+1) ≥ σ(Q, ir), a contradiction to (12).

Case 2: σ(Q, ir) < σ(Q^r, ir).

If σ(Q^r, j_r+1) < σ(Q, i_r), then σ(Q^r, j_r+1) < min{σ(Q^r, i_r), σ(Q, i_r)} which yields the
same contradiction as in Case 1. Therefore, σ(Q, i_r) ≤ σ(Q^r, j_r+1).

From Observation B.1 and the assumption that σ(Q^r, jr+1) < σ(Q^r, ir) it follows that
for each l ≤ σ(Q^r, jr+1), jr+1 ∈/ P(Q^r, l, ir). From (11) and Lemma B.7 it follows that for
each l with σ(Q, i_r) ≤ l ≤ σ(Q^r, j_r+1), F (Q, l, j_r+1) = F (Q^r, l, j_r+1) (as directed paths).
So, by taking l = σ(Q^r, j_r+1), we obtain that j_r+1’s cycle under TTC(Q) is the same as
under TTC(Q^r). In particular, jr+1 ∈ As_r+1 (Q^r), a contradiction.

Since both cases give a contradiction we conclude that σ(Q^r,j_r+1) ≥ σ(Q^r,i_r).        □

Step 5 There is an X -cycle.

We can assume, without loss of generality, that among the students in {j₁ , . . . , j_p} student
j1 is (one of) the last one(s) to be assigned to a school under TTC(Q), i.e.,

σ(Q, j1) ≥ σ(Q,jr) for any r ∈ {1, . . . ,p}.                       (13)

Suppose fs₂ (j1) < fs₂ (j2). By definition of j2, school s2 points to student j2 in the
last, q_s2 -th, cycle of s₂ under TTC(Q), which o ccurs at step σ(Q, s₂). Hence, j₁ ∈

43

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