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 p2, 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 f
s(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. Insurance within the firm
2. The name is absent
3. Individual tradable permit market and traffic congestion: An experimental study
4. LOCAL CONTROL AND IMPROVEMENT OF COMMUNITY SERVICE
5. Olive Tree Farming in Jaen: Situation With the New Cap and Comparison With the Province Income Per Capita.
6. Skill and work experience in the European knowledge economy
7. A Unified Model For Developmental Robotics
8. Citizenship
9. The Making of Cultural Policy: A European Perspective
10. What Lessons for Economic Development Can We Draw from the Champagne Fairs?