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. The Role of Land Retirement Programs for Management of Water Resources
2. Private tutoring at transition points in the English education system: its nature, extent and purpose
3. WP 48 - Population ageing in the Netherlands: Demographic and financial arguments for a balanced approach
4. A simple enquiry on heterogeneous lending rates and lending behaviour
5. The Effects of Attendance on Academic Performance: Panel Data Evidence for Introductory Microeconomics
6. Proceedings of the Fourth International Workshop on Epigenetic Robotics
7. The name is absent
8. Internationalization of Universities as Internationalization of Bildung
9. Olive Tree Farming in Jaen: Situation With the New Cap and Comparison With the Province Income Per Capita.
10. If our brains were simple, we would be too simple to understand them.