e(Q,p,v) = e(Q',p,v) for each agent v ∈ V (Q,p)∖i, C * is also a cycle in G(Q',p). In
particular, τ(Q)(j) = τ(Q')(j), a contradiction. This completes the proof of (a).
We now prove (b). We distinguish between two cases.
Case 1: j ∈ P(Q',p, i).
Then, (b) follows directly from Lemma B.6 with Q = Q’, v' = j, and v = i.
Case 2: j ∈ P(Q',p,i).
Assume that (b) is not true. In other words, assume that σ(Q', i) > σ(Q', j) or [σ(Q', i) =
σ(Q', j) and i and j are assigned in different cycles in TTC(Q,)]∙ Then, σ(Q,i) = p ≤
r’ = σ(Q, j) ≤ σ(Q',i)∙
Note that by definition of r', j ∈ V(Q', r’). Suppose j ∈ (P(Q', r’, i) ∪ i). Since j = i,
j ∈ P(Q',r',i). By Lemma B.6, σ(Q',i) ≤ σ(Q,j) and [σ(Q',i) = σ(Q',j) only if i and
j are removed in the same cycle in TTC(Q’)]. This contradicts the assumption that (b)
is not true. So, j ∈ (P(Q',r',i) ∪ i). In other words, j ∈ V(Q',r')∖(P(Q',r',i) ∪ i).
Hence, by Lemma B.7, j ∈ V(Q, r’) and F(Q,r',j) = F(Q',r',j). Since σ(Q',j) = r’,
student j forms part of a cycle, say C', in G(Q',r'). Hence, C' = F(Q',r',j). So, also
C’ = F(Q, r’, j). Hence, student j is assigned to the same school (or himself) in TTC(Q)
and TTC(Q'), contradicting τ(Q)(j) = τ(Q')(j). This completes the proof of (b). ■
Proposition B.9 Let P be a school choice problem. Let 2 ≤ k ≤ m. Let Q ∈ Eτ (P, k).
Define Qi := τ(Q)(i) for all i ∈ I. Then, Q ∈ Eτ (P, 1) and τ(Q) = τ(Q). In particular,
Oτ(P, k) ⊆ Oτ (P, 1).
Proof It is sufficient to prove the following claim.
Claim: Let P be a school choice problem. Let 2 ≤ k ≤ m, Q ∈ Eτ (P, k), and j ∈ I. Let
Qj := τ(Q)(j). Then, Q := (Qj,Q-j) ∈ Eτ(P,k).
Indeed, if the Claim is true then we can pick students one after another and each time
apply both the Claim and Proposition B.5 to eventually obtain a profile Q ∈ Eτ(P, k)
with τ(Q) = τ(Q) and where for all j ∈ I, Qj = τ(Q)(j). By construction, Q ∈ Q(1)I.
So, Q ∈ Eτ(P, 1).
To prove the Claim, suppose Q ∈/ Eτ(P, k). Then, there is a student i with a profitable
deviation at Q in Γτ (P, k). In fact, by Proposition B.5 there is a strategy Q’i ∈ Q(1) with
τ (Qi,Q)-i)PiT (Qi,Q-i). (6)
We claim i = j . Suppose i = j . Then, Q-i = Q-j = Q-j . So, (6) becomes τ (Q’j , Q-j )Pj
τ(Qj , Q-j ), contradicting Q ∈ Eτ (P, k). So, i = j .
38