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
More intriguing information
1. The name is absent2. The name is absent
3. The economic value of food labels: A lab experiment on safer infant milk formula
4. The name is absent
5. Neural Network Modelling of Constrained Spatial Interaction Flows
6. Improving Business Cycle Forecasts’ Accuracy - What Can We Learn from Past Errors?
7. How to do things without words: Infants, utterance-activity and distributed cognition.
8. Herman Melville and the Problem of Evil
9. The name is absent
10. Nurses' retention and hospital characteristics in New South Wales, CHERE Discussion Paper No 52