Recall Q = (Qi , Qj , Q-ij ). Define Q := (Qi , Qj , Q-ij ) and Q := (Qi, Qj , Q-ij ) . We
can rewrite (6) as
T (Q‘) = T (Qx,(Qj ,Q-ij )Ргт (Qi,Qj ,Q-ij ) = τ (Q). (7)
From Q ∈ Eτ(P, k), Lemma B.2 (Oτ(P, k) ⊆ IR(P)), and Proposition B.5, τ(QQ) =
T(Q) ∈ IR(P). By (7), τ(Q')(i) =: s ∈ S. Since Q = Qi ∈Q(1), Qi = s.
Suppose τ(Q')(j) = τ(Q)(j). Recall (Qj = τ(Q)(j). So, QQj = τ(Q')(j). Hence, Propo-
sition B.5 implies τ(Qi, (Qj, Q-j) = τ(Qi, Qj, Q-j) and τ(Qi, Qj,Q-ij) = τ(Qi, Qj,Q-ij).
Then (7) can be rewritten as τ (Qi, Qj ,Q-ij )Piτ (Qi,Qj ,Q-ij ). So, Q ∈ Eτ (P, k), a con-
tradiction. Hence, τ(Q')(j) = τ(Q)(j).
Next, we prove that τ(Q')(i) = τ(Q')(i). Suppose τ(Q')(i) = τ(Q')(i). Since τ(QQ) =
τ(Q), (7) boils down to τ(Q')Piτ(Q), which implies that Q ∈ Eτ(P, k), a contradiction.
So, τ(Q')(i) = τ(<Q')(i).
Note that for any student h = i, Qh = Qh. So, by Lemma B.8, σ(Q',i) ≤ σ(Q',j).
Note also that for any student h = j, (Qh = Qh So, by Lemma B.8, σ(Q', j) ≤ σ(Q',i).
So, σ(Q',i) = σ(Q', j). From Lemma B.8 it follows that i and j are in the same cycle
in TTC(Q'). So, i is not in a self-cycle. Hence, i is assigned to a school in TTC(Q').
Since Qi = s, τ(Q')(i) = s. By definition, s = τ(Q)')(i). So, τ(Q')(i) = τ(Q)z)(i), a
contradiction. Hence, Q ∈ Eτ(P, k), which completes the proof of the Claim. ■
Proof of Theorem 5.4 Follows from Propositions B.5 and B.9. ■
In order to prove Theorem 6.8 we need the following two lemmas.
Lemma B.10 Let f be a Kesten-cyclic priority structure. Let 1 ≤ k ≤ m. Then, there
is a school choice problem P with an unstable equilibrium outcome in the game Γτ (P, k),
i.e., for some Q ∈ Eτ(P,k), T(Q) ∈ S(P).
Proof By Theorem 1 of Kesten (2006), there is a school choice problem P such that
T(P) is unstable. Since T is strategy-proof, P ∈ Eτ (P, m). Hence, by Theorem 5.4,
T(P) ∈ Oτ (P, m) = Oτ (P, k). So, there is a profile Q ∈ Q(k)I such that Q ∈ Eτ(P, k)
and τ(Q) = τ(P) ∈ S(P). ■
Lemma B.11 Let f be a Kesten-acyclic priority structure. Let 1 ≤ k ≤ m. Then, for
any school choice problem P all equilibrium outcomes in the game Γτ(P, k) are stable, i.e.,
for all Q ∈ Eτ (P, k), T(Q) ∈ S(P). In fact, S(P) = Oτ (P, k).
39