Assume Claim(I) is not true, i.e., x := e(Q,l,v) = e(Q',l,v) =: x'. Since v ∈ Pl, x' ∈
Pl. By (2), x' ∈ Pl-1. By (3) and x' ∈ V(Q', l), x' ∈ V(Q', l — 1). By Consequence(l — 1),
x' ∈ V(Q,l — 1). We distinguish between two cases.
Case 1: Agent x' is removed at the end of step l — 1 in TTC(Q).
From (2) and (3), x' ∈ V (Q', g)\Pg for each step g, p ≤ g < l. From Consequence(g)
(p ≤ g < l), x' ∈ V(Q, g) and
F(Q, g, x') = F (Q', g, x') for each step g, p ≤ g < l. (5)
By (1), (5), and the fact that x' is removed at the end of step l — 1 in TTC(Q), x' is also
removed at the end of step l — 1 in TTC(Q'). Hence, x' ∈ V(Q', l), a contradiction with
e(Q', l, v) = x'.
Case 2: Agent x' is not removed at the end of step l — 1 in TTC(Q).
Then, x' ∈ V(Q, l). Since e(Q, l, v) = x = x', we have xQvx' (if v is a student) or
fv(x) < fv(x') (if v is a school). Hence, since e(Q', l, v) = x', x ∈ V (Q', l). So, agent x
was removed at some step g*, 1 ≤ g* ≤ l — 1, in TTC(Q'). In fact, by (1), p ≤ g* ≤ l — 1.
Note that no agent in Pp' is removed before the end of step p' in TTC(Q'). So, x ∈ Pp’.
By (2), x ∈ Pg*. Hence, x ∈ V(Q',g*)∖Pg*. By an argument similar to that of Case 1,
x is also removed at the end of step g* in TTC(Q). Hence, x ∈ V(Q,l), a contradiction
with e(Q, l, v) = x. ■
Lemma B.8 Let Q ∈ QI . Let i ∈ I and Q'i ∈ Q. Define Q' := (Q'i, Q-i). Suppose there
is a student j ∈ I\i with τ (Q)(j) = τ(Q')(j). Then,
(a) σ(Q, i) ≤ σ(Q, j) and [σ(Q, i) = σ(Q, j) only if i and j are assigned in the same
cycle in TTC(Q)], and
(b) σ(Q', i) ≤ σ(Q', j) and [σ(Q', i) = σ(Q', j) only if i and j are assigned in the same
cycle in TTC(Q')].
Proof By non bossiness of τ, τ (Q)(i) = τ (Q')(i). Let p := σ(Q, i) and p' := σ(Q', i).
Assume, without loss of generality, p ≤ p'. Then, by definition of p and Lemma B.3(d),
there is a cycle C in G(Q, p) with i ∈ C but not present in G(Q', p).
We first prove (a). By Lemma B.3(a,b), for each student h ∈ I\i with σ(Q, h) < p or
σ(Q', h) < p, τ (Q)(h) = τ(Q')(h). Let r := σ(Q, j) and r' := σ(Q', j). Since τ(Q)(j) =
τ (Q')(j), we have r, r' ≥ p. So, σ(Q, i) = p ≤ r = σ(Q, j). Suppose σ(Q, i) = σ(Q, j).
We have to show that j ∈ C. Suppose j ∈ C. Then, j ∈ C* for some cycle C* ,
C* = C, in G(Q, p). Note i ∈ C*. By Lemma B.3(b), V(Q,p) = V (Q', p). Hence, since
37