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. Großhandel: Steigende Umsätze und schwungvolle Investitionsdynamik
2. Announcement effects of convertible bond loans versus warrant-bond loans: An empirical analysis for the Dutch market
3. Developments and Development Directions of Electronic Trade Platforms in US and European Agri-Food Markets: Impact on Sector Organization
4. Secondary school teachers’ attitudes towards and beliefs about ability grouping
5. The name is absent
6. The name is absent
7. PROFITABILITY OF ALFALFA HAY STORAGE USING PROBABILITIES: AN EXTENSION APPROACH
8. ROBUST CLASSIFICATION WITH CONTEXT-SENSITIVE FEATURES
9. Computational Batik Motif Generation Innovation of Traditi onal Heritage by Fracta l Computation
10. Gianluigi Zenti, President, Academia Barilla SpA - The Changing Consumer: Demanding but Predictable