Remark 7.4 implies that f admits a weak X-cycle. So, suppose μI ∈ PE(P). Since
γ (Q) ∈ PE(P ), γ(Q) = μI. Since |S (P )| = 1, γ (Q) ∈ S (P ). By Theorem 6.5, f admits
an Ergin-cycle, which by Remark 7.4 implies again that f admits a weak X -cycle.
(iii) ⇒ (i): Suppose that f admits a weak X -cycle. By (ii) ⇒ (i) there exists P with
|S (P )| ≥ 2. So, there exists μ ∈ S (P )\PE (P ). By Lemma A.8, there exists Q ∈ Eγ (P, k)
with γ(Q) = μ.
(i) ⇒ (iv): Let P be a school choice problem with Q ∈ Eβ(P, k) such that β(Q) ∈/ PE(P).
By Theorem 6.1, β(Q) ∈ S (P ). Hence, by Lemma A.8, there exists Q ∈ Eγ (P, 1) with
Y(Q?) = β(Q). Hence, from (i) ⇒ (iii) it follows that f admits a weak X-cycle.
(iv) ⇒ (i): Suppose that f admits a weak X -cycle. From (iii) ⇒ (i) it follows that
there is a school choice problem P with Q ∈ Eγ(P, 1) such that γ(Q) ∈/ PE(P). Since
Γβ(P, 1) = Γγ(P, 1), the result follows. ■
B Appendix: Proofs for TTC
We first introduce some graph-theoretic notation to provide concise proofs of our results.
Let Q ∈ QI. Suppose the TTC algorithm is applied to Q, which we will denote by
TT C(Q), and suppose it terminates in no less than l steps. We denote by G(Q, l) the
(directed) graph that corresponds to step l. In this graph, the set of vertices V (Q, l) is
the set of agents present in step l. For any v ∈ V (Q, l) there is a (unique) directed edge
in G(Q, l) from v to some v′ ∈ V (Q, l) (possibly v′ = v if v ∈ I) if agent v points to agent
v′, which will also be denoted by e(Q, l, v) = v′.
A path (from v1 to vp) in G(Q, l) is an ordered list of agents (v1, v2 , . . . , vp) such that
vr ∈ V (Q, l) for all r = 1, . . . , p and each vr points to vr+1 for all r = 1, . . . , p - 1. A
self-cycle (i) of a student i is a degenerate path, i.e., i points to himself in G(Q, l). An
agent v′ ∈ V (Q, l) is a follower of an agent v ∈ V (Q, l) if there is a path from v to v′
in G(Q, l). The set of followers of v is denoted by F(Q, l, v). An agent v′ ∈ V (Q, l) is a
predecessor of an agent v ∈ V (Q, l) if there is a path from v′ to v in G(Q, l). The set of
predecessors of v is denoted by P(Q, l, v). A cycle in G(Q, l) is a path (v1, v2, . . . , vp) such
that also vp points to v1. Note that a self-cycle is a special case of a cycle. With a slight
abuse of notation we sometimes refer to a cycle as the corresponding non ordered set of
involved agents. Finally, for v ∈ I ∪ S, let σ(Q, v) denote the step of the TTC algorithm
at which agent v is removed.
33