Constrained School Choice

One easily shows that that O^τ (P, 1) ⊆ NW(P) ∩ IR(P). Hence, by Lemma A.7 there
exist a set of students CI = {i1, . . . , ip} and a set of schools CS = {s1, . . . , sp} such that
for each i_r ∈ C_I, s_r P_ir s_r+1 = τ (Q)(i_r). This proves (a). Obviously,

∣As(Q)∣ = ∣τ(Q)(s)∣ for any Q ∈ QI.                          (8)

Hence, by Lemma A.7, for each school s ∈ CS, ∣A_s(Q)∣ = ∣τ(Q)(s)∣ = q_s. Hence, (b)
follows. Since a student is part of exactly 1 cycle, (c) follows.                           □

For any student ir ∈ CI define Q^r := (sr, Q-i_r). By Step 1, τ (Q)(ir) = Qi_r = sr+1

(modulo p). Since Q_i^r_r = s_r P_ir s_r+1 and Q ∈ E^τ (P, 1), τ(Q^r)(i_r) = i_r.

Step 2 Let r ∈ {1, . . . , p}. For each s ∈ S\s_r+1, ∣A_s(Q^r)∣ = ∣A_s(Q)∣, and ∣A_sr+1(Q^r)∣ =
∣Asr+1(Q)∣ - 1.

In view of (8) and i_r ∈ τ (Q)(S_r+1), we are done if we prove that for each s ∈ S\s_r+1,
τ(Q^r)(s) = τ (Q)(s), and τ (Q^r)(sr+1) = τ (Q)(sr+1)\ir.

For each school s = sr, sr+1, only the qs (see Step 1(b)) students in τ (Q)(s) list school
s in Q^r. Note also that only the qs_r+1 - 1 (see Step 1(b)) students in τ (Q)(sr+1)\ir list
school s_r+1 in Q^r. Since Q^r ∈ Q^I (1) and τ(Q^r) ∈ NW (Q^r), τ (Q^r)(s) = τ (Q)(s) for each
school s = s_r. Finally, note that only the q_sr + 1 students in τ (Q)(s_r) ∪ i_r list school s_r
in Qr. Since Qrr = sr, τ(Qr)(ir) = ir, and τ(Qr) ∈ NW(Qr), τ(Qr)(sr) = τ(Q)(sr).    □

Step 3 For any r ∈ {1, . . . ,p}, As_r(Q^r) = As_r(Q).

We are done if we show the following claim.

Claim: For each integer l, we have

[ sr ∈ V(Q, l) if and only if sr ∈ V(Q^r, l) ],                                     1

[ if sr is in a cycle C of G(Q, l) then C is also a cycle of G(Q^r, l)], and (9)
[ if sr is in a cycle C of G(Q^r, l) then C is also a cycle of G(Q, l)].       ^

Proof of Claim: We distinguish among six cases.

Case 1: l < min{σ(Q, i_r), σ(Q^r, i_r)}. Then, (9) follows from Lemma B.3(a).

Case 2: σ(Q,ir) ≤ l < σ(Q^r,ir). Since Q_i^r_r = sr and τ(Q^r)(ir) = ir, sr ∈ P(Q^r,l,ir).

Since σ(Q^r, sr) = σ(Q^r, ir) - 1, sr ∈ V(Q^r, l).  By Lemma B.7, sr ∈ V(Q, l) and

F (Q, l, s_r) = F (Q^r, l, s_r) (as directed paths). So, (9) holds.

Case 3: σ(Q, ir) < l = σ(Q^r, ir). Since σ(Q^r, ir) = σ(Q^r, sr) + 1, F(Q^r, l - 1, sr) is the
last cycle of s_r under TT C(Q^r). By Case 2, this is a cycle of s_r under TT C(Q). In fact,

41

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