Constrained School Choice

We need the following 2 lemmas for the proof of Theorem 7.5.

Lemma A.7 Let φ be a mechanism such that for some 1 ≤ k ≤ m, O^ψ(P, k) ⊆ NW (P )∩
IR(P). Suppose Q ∈ E^ψ(P,k) with φ(Q) / PE(P). Then, there exist p ≥ 2, a set of
students C_I = {i₁ , . . . , i_p} and a set of schools C_S = {s₁ , . . . , s_p} such that for each school
s ∈ C_s, ∣^(Q)(s)| = q_s and for each i_r ∈ CI, s_rPi_rs_r+₁ = φ(Q')(i_r), where s_p+1 = s₁.

Proof Similar to a part of Step 1 of (iv) ⇒ (i) in Ergin (2002, proof of Theorem 1). ■

Lemma A.8 Let P be a school choice problem. Let μ ∈ S(P). Define Qi := μ(i) for all
i ∈ I. Then, γ(Q) = μ and Q ∈ E^γ(P, 1) ⊆ E^γ(P, k) for all 2 ≤ k ≤ m.

Proof Follows immediately from Theorem 5.3 and Proposition 6.2.               ■

Proof of Theorem 7.5 We show that (i) ⇒ (ii) ⇒ (i) ⇒ (iii) ⇒ (i) ⇒ (iv) ⇒ (i).

(i) ⇒ (ii): Suppose P is a school choice problem with ∣S(P)∣ ≥ 2. Hence, there is a
stable matching μ different from the student-optimal stable matching μI. By optimality
of μI, for each student i ∈ I, μIRiμ, and for at least one student i ∈ I, μIPiμ. So,
μ ∈ PE(P). By Lemma A.8, there exists a profile Q ∈ QI(1) such that (a) for each
student i ∈ I, Qi = μ(i); (b) γ(Q) = μ; and (c) Q ∈ E^γ(P, 1). By Lemmas A.2 and A.7
there exist a set of students CI = {i1 , . . . , ip} and a set of schools Cs = {s1, . . . , sp} such
that for each s ∈ C_s, ∣γ(Q)(s)∣ = q_s , and for each i_l ∈ C_I, s_lP_il s_l+1 = γ(Q)(i_l). Note
that since a student is assigned to at most one school, for any two schools s, s^′ ∈ C_s ,
γ(Q)(s) ∩ γ(Q)(s') = 0. For any two subsets I', I'' ⊆ I with I' ∩ I'' = 0 and any school s
we will write f_s(I') < f_s(I'') to say that for all students i' ∈ I' and i'' ∈ I'', f_s(i') < f_s(i'').
Step 1 For each student il ∈ CI, il ∈ γ(Q)(sl+1) and fs_l (γ(Q)(sl)) < fs_l (il).

By construction, iι ∈ γ(Q)(s_z+ι). Let Q' = (sι,Q-i_l). Since Q ∈ E^γ(P, 1), γ(Q')(iι) = iι.
In particular, f_3l(γ(Q')(sι)) < fs_l(iι). By (a), γ(Q')(sι) = γ(Q)(sι), and Step 1 follows.

Step 2 The priority structure f admits a weak X -cycle.

From Step 1 it follows that the priority structure has the following form

31

<<   <   28   29   30   31   32   33   34   >   >>