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) fs₁(ij) < fs₁(i1) < fs₁(i2) for each j ∈ I1 := {3, . . . , qs₁ + 1} and

(b) fs₂(ij) < fs₂(i2) < fs₂(i1) for each j ∈ I2 := {qs₁ + 2, . . . ,qs₁ + qs₂}.

Consider students’ preferences P defined by P_i1 := s₂, s₁, P_i2 := s₁, s₂, P_ij := s₁ for
j ∈ I1, Pi_j := S2 for j ∈ I2, and Pi_j := 0 for all j ∈ ⅛₁ + qs₂ + 1,. .., n}.

Consider Q ∈ Q(k)^I defined by Qi₁ := s1, Qi₂ := s2, and Qi := Pi for all i ∈ I \{i1 , i2}.
One easily verifies that at τ(Q) all students in {i₃, i₄, . . . , i_{qs1 +qs2} } are assigned to their
favorite school. Also, τ(Q)(i₁) = s₁ and τ (Q)(i₂) = s₂. It is obvious that at τ(Q)
students i1 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, Q_i = τ (Q)(i).
For any school s ∈ S and any profile Q ∈ QI, let A_s(Q) be the set of students to which
school s points whenever school s is part of a cycle, i.e.,

A_s(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 C_I = {i₁ , . . . , i_p}, and a set of schools
C_S = {s₁, . . . , s_p} such that

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

(b) for each school s ∈ CS, ∣A_s(Q)∣ = ∣τ(Q)(s)∣ = q_s, and

(c) for any two distinct schools s, s' ∈ C_s, A_s(Q) ∩ A_s'(Q) = 0.

40

<<   <   37   38   39   40   41   42   43   >   >>