Constrained School Choice



Proof By Theorem 1 of Kesten (2006), τ = γ. Hence, Oτ (P, k) = Oγ(P, k). By
Lemma 1 of Kesten (2006), f is Ergin-acyclic. So, from Theorem 6.5, S(P) =
Oγ (P, k) =
Oτ (P,k).                                                                           ■

Proof of Theorem 6.8 Follows from Lemmas B.10 and B.11.

Lemma B.12 Let the priority structure f admit an X-cycle. Let 1 k m. Then,
there is a school choice problem
P with a Pareto inefficient equilibrium outcome in the
game
Γτ(P, k), i.e., for some Q Eτ(P, k), τ(Q) PE(P).

Proof Since f admits an X -cycle, we may assume, without loss of generality, that
(a) f
s1(ij) < fs1(i1) < fs1(i2) for each j I1 := {3, . . . , qs1 + 1} and

(b) fs2(ij) < fs2(i2) < fs2(i1) for each j I2 := {qs1 + 2, . . . ,qs1 + qs2}.

Consider students’ preferences P defined by Pi1 := s2, s1, Pi2 := s1, s2, Pij := s1 for
j I1, Pij := S2 for j I2, and Pij := 0 for all j 1 + qs2 + 1,. .., n}.

Consider Q Q(k)I defined by Qi1 := s1, Qi2 := s2, and Qi := Pi for all i I \{i1 , i2}.
One easily verifies that at τ(Q) all students in
{i3, i4, . . . , iqs1 +qs2 } are assigned to their
favorite school. Also, τ(Q)(i
1) = s1 and τ (Q)(i2) = s2. It is obvious that at τ(Q)
students i
1 and i2 would like to swap their seats, i.e., τ (Q) PE(P). Nevertheless, there
is no unilateral deviation for either of the two students to obtain the other seat. Hence,
Q
Eτ(P,k).                                                              ■

Proposition B.13 Let 1 k m. If for some school choice problem P there exists
Q Eτ (P, k) such that τ (Q) / PE(P) then f admits an X -cycle.

Proof Let Q Eτ(P, k) be such that τ(Q) / PE(P). In view of Proposition B.9 we may
assume without loss of generality that k = 1 and for each student i
I, Qi = τ (Q)(i).
For any school s
S and any profile Q QI, let As(Q) be the set of students to which
school s points whenever school s is part of a cycle,
i.e.,

As(Q) := {i I : there is a step l of TTC(Q) with i = e(Q, l, s) and s F(Q, l, i)} .

Step 1 There exist p 2, a set of students CI = {i1 , . . . , ip}, and a set of schools
CS = {s1, . . . , sp} such that

(a) for each student ir CI, srPir sr+1 = τ (Q)(ir) (where ip+1 = i0),

(b) for each school s CS, As(Q) = τ(Q)(s) = qs, and

(c) for any two distinct schools s, s' Cs, As(Q) As'(Q) = 0.

40



More intriguing information

1. Forecasting Financial Crises and Contagion in Asia using Dynamic Factor Analysis
2. The name is absent
3. The name is absent
4. The Impact of Individual Investment Behavior for Retirement Welfare: Evidence from the United States and Germany
5. Großhandel: Steigende Umsätze und schwungvolle Investitionsdynamik
6. The name is absent
7. The name is absent
8. The name is absent
9. Response speeds of direct and securitized real estate to shocks in the fundamentals
10. American trade policy towards Sub Saharan Africa –- a meta analysis of AGOA