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. Errors in recorded security prices and the turn-of-the year effect2. The economic value of food labels: A lab experiment on safer infant milk formula
3. Program Semantics and Classical Logic
4. The name is absent
5. The name is absent
6. GROWTH, UNEMPLOYMENT AND THE WAGE SETTING PROCESS.
7. Portuguese Women in Science and Technology (S&T): Some Gender Features Behind MSc. and PhD. Achievement
8. Reputations, Market Structure, and the Choice of Quality Assurance Systems in the Food Industry
9. The name is absent
10. A THEORETICAL FRAMEWORK FOR EVALUATING SOCIAL WELFARE EFFECTS OF NEW AGRICULTURAL TECHNOLOGY