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. Moi individuel et moi cosmique Dans la pensee de Romain Rolland
2. The name is absent
3. Nietzsche, immortality, singularity and eternal recurrence1
4. Studies on association of arbuscular mycorrhizal fungi with gluconacetobacter diazotrophicus and its effect on improvement of sorghum bicolor (L.)
5. The name is absent
6. A Consistent Nonparametric Test for Causality in Quantile
7. Workforce or Workfare?
8. The resources and strategies that 10-11 year old boys use to construct masculinities in the school setting
9. The name is absent
10. The name is absent