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 CI = {i1 , . . . , ip} and a set of schools CS = {s1 , . . . , sp} such that for each school
s ∈ Cs, ∣^(Q)(s)| = qs and for each ir ∈ CI, srPirsr+1 = φ(Q')(ir), where sp+1 = s1.
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 ∈ Cs, ∣γ(Q)(s)∣ = qs , and for each il ∈ CI, slPil sl+1 = γ(Q)(il). Note
that since a student is assigned to at most one school, for any two schools s, s′ ∈ Cs ,
γ(Q)(s) ∩ γ(Q)(s') = 0. For any two subsets I', I'' ⊆ I with I' ∩ I'' = 0 and any school s
we will write fs(I') < fs(I'') to say that for all students i' ∈ I' and i'' ∈ I'', fs(i') < fs(i'').
Step 1 For each student il ∈ CI, il ∈ γ(Q)(sl+1) and fsl (γ(Q)(sl)) < fsl (il).
By construction, iι ∈ γ(Q)(sz+ι). Let Q' = (sι,Q-il). Since Q ∈ Eγ(P, 1), γ(Q')(iι) = iι.
In particular, f3l(γ(Q')(sι)) < fsl(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
fsι |
fs2 .. |
. fsp-1 |
fsp |
. . γ(Q)(s1) . . |
. . γ(Q)(s2) . . |
. . γ(Q)(sp-1) . . |
. γ(Q)(sp) . . |
. i1 . . . |
. i2 . . . |
. ip-1 . . . |
. ip . . . |
31
More intriguing information
1. Yield curve analysis2. The name is absent
3. WP 48 - Population ageing in the Netherlands: Demographic and financial arguments for a balanced approach
4. The Effects of Attendance on Academic Performance: Panel Data Evidence for Introductory Microeconomics
5. Business Cycle Dynamics of a New Keynesian Overlapping Generations Model with Progressive Income Taxation
6. The name is absent
7. The name is absent
8. Ruptures in the probability scale. Calculation of ruptures’ values
9. The name is absent
10. THE CO-EVOLUTION OF MATTER AND CONSCIOUSNESS1