Constrained School Choice

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 ∈ Q^I. 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 v₁ to v_p) in G(Q, l) is an ordered list of agents (v₁, v₂ , . . . , v_p) such that
v_r ∈ V (Q, l) for all r = 1, . . . , p and each v_r points to v_r+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 (v₁, v₂, . . . , v_p) 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

<<   30   31   32   33   34   35   36   >>

More intriguing information