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. Globalization and the benefits of trade
4. Regional science policy and the growth of knowledge megacentres in bioscience clusters
5. Ronald Patterson, Violinist; Brooks Smith, Pianist
6. The name is absent
7. Distribution of aggregate income in Portugal from 1995 to 2000 within a SAM (Social Accounting Matrix) framework. Modeling the household sector
8. The name is absent
9. Auction Design without Commitment
10. Placenta ingestion by rats enhances y- and n-opioid antinociception, but suppresses A-opioid antinociception