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. AGRICULTURAL TRADE LIBERALIZATION UNDER NAFTA: REPORTING ON THE REPORT CARD2. ‘Goodwill is not enough’
3. The name is absent
4. The name is absent
5. Agricultural Policy as a Social Engineering Tool
6. IMMIGRATION AND AGRICULTURAL LABOR POLICIES
7. The name is absent
8. The name is absent
9. Indirect Effects of Pesticide Regulation and the Food Quality Protection Act
10. Managing Human Resources in Higher Education: The Implications of a Diversifying Workforce