Observation B.1 In the TTC algorithm, once a student points to a school it will keep
on pointing to the school in subsequent steps until he is assigned to a seat at the school
or until the school has no longer available seats. In other words, if i ∈ V (Q, l) ∩ I for
some step l of TTC(Q) and e(Q, l, i) = s ∈ S, then e(Q, r, i) = s for all steps r with
l ≤ r ≤ min{σ(Q, i), σ(Q, s)}. Similarly, once a school points to a student it will keep on
pointing to the student in subsequent steps until the student is assigned to a seat at this
or some other school. In other words, if s ∈ V (Q, l) ∩ S for some step l of TTC(Q) and
e(Q, l, s) = i ∈ I, then e(Q, r, s) = i for all steps r with l ≤ r ≤ σ(Q, i).
We now proceed to establish some preliminary results and slightly technical lemmas
to be able to prove Theorems 5.4 and 7.2. The proof of the next lemma is omitted.
Lemma B.2 For any school choice problem P and any quota k, Oτ (P, k) ⊆ IR(P) .
In order to avoid possible confusion we will sometimes use an additional superindex
Q and write qsQ,r instead of qsr .
Lemma B.3 Let Q ∈ QI. Let i ∈ I and Qi ∈ Q. Define Q' := (Qi,Q-i). Suppose
τ(Q)(i) = τ(Q')(i). Let p := σ(Q,i), p′ := σ(Q',i), and r :=min{p,p'}. Then,
(a) at steps 1,... ,r — 1, the same cycles form in TTC(Q) and TTC(Q');
(b) i ∈ V(Q,r) = V(Q',r) and for each school s ∈ V(Q, r) ∩ S, qQ,r = qQ',r;
(c) e(Q, r, v) = e(Q', r, v) for each agent v ∈ V(Q, r)\i;
(d) there is a cycle C with i ∈ C in either G(Q,r) or G(Q',r) (but not both).26
Proof Item (a) follows from the proof of a result in Abdulkadiroglu and Sonmez (1999,
Lemma 1) or, alternatively, Abdulkadiroglu and Sonmez (2003, Lemma). As for Item (b),
from the definition of r, i ∈ V(Q, r) ∩ V(Q', r). The remainder of Item (b) follows directly
from Item (a). Item (c) follows from Item (b) and the fact that Qj = Qj for all j ∈ I\i.
As for Item (d), by definition of r, there is a cycle C with i ∈ C in G(Q,r) or G(Q',r).
From Item (c) and τ(Q)(i) = τ(Q')(i), e(Q,r, i) = e(Q',r, i). In particular, C is not a
cycle in both G(Q,r) and G(Q',r). This proves Item (d). ■
Lemma B.4 Let φ be a mechanism such that for any Q ∈ QI, any i ∈ I, Qi = φ(Q')(τ) ∈
Q(1) implies φ(Qi,Q-i) = φ(Q). Then, for any school choice problem P and quotas
k < k', Eψ(P,k) ⊆ Eψ(P,kr).
26Note that it is still possible that there is another cycle C (i.e., C = C) with i ∈ C present in the
other graph.
34