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) fs1(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)(i1) = s1 and τ (Q)(i2) = s2. 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, 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 name is absent2. ISSUES AND PROBLEMS OF IMMEDIATE CONCERN
3. The name is absent
4. Changing spatial planning systems and the role of the regional government level; Comparing the Netherlands, Flanders and England
5. Economies of Size for Conventional Tillage and No-till Wheat Production
6. Une Classe de Concepts
7. Moi individuel et moi cosmique Dans la pensee de Romain Rolland
8. PER UNIT COSTS TO OWN AND OPERATE FARM MACHINERY
9. Internationalization of Universities as Internationalization of Bildung
10. The name is absent