Constrained School Choice

Hence, σ(Q,v) ≤ σ(Q,v^,). Suppose σ(Q,v) = σ(Q,v^,). Then, all agents in the path from
v^′ to v form part of a cycle at this step. Since an agent can be part of at most one cycle
at a given step, all agents in the path from v^, to v are in the same cycle.              ■

Lemma B.7 Let Q ∈ QI. Let i ∈ I and Q^t_i ∈ Q. Define Q := (Qi,Q_-i). Suppose
τ(Q)(i) = τ(Q')(i) and σ(Q,i) ≤ σ(Q^,,i). Then, for each step l with σ(Q,i) ≤ l ≤
σ(Q^,,i), if v ∈ V(Q^,,l)∖(P(Q',l,i) ∪ i) then v ∈ V(Q,l) and F(Q,l,v) = F(Q^,,l,v).²8

Proof Let p := σ(Q, i) and p^, := σ(Q', i). From Lemma B.3(b),

V(Q,p) = V(Q^,,p) and q^Q,p = qQ'^,p for each school s ∈ V(Q,p) ∩ S. (1)

With a slight abuse of notation, for each l, p ≤ l ≤ p, denote P_l = P(Q^,, l, i) ∪ i. From
Observation B.1,

Pp ⊆ Pp+1 ⊆∙∙∙⊆ Pp'-1 ⊆ Pp'.                        (2)

Also note

V(Q^,,p^,) ⊆ V(Q',p' - 1) ⊆∙∙∙⊆ V(Q,p + 1) ⊆ V(Q,p).            (3)

We are done if we prove the following Claim(l) for each l, p ≤ l ≤ p^′.

Claim(l): If v ∈ V(Q^,, l)\P_l, then v ∈ V(Q, l) and e(Q, l, v) = e(Q^,, l, v).

Indeed, Claim(l) immediately implies the following Consequence(l):

Consequence(l): Ifv ∈ V (Q^,, l)\Pl, then v ∈ V(Q,l) and F(Q,l,v) = F (Q^,, l, v).

We now prove by induction that Claim(l) is true for each l, p ≤ l ≤ p^,. By Lemma B.3(b,c),
V(Q, p) = V(Q^,, p) and e(Q, p, v) = e(Q^,, p, v) for each agent v ∈ V(Q, p)\i. Hence,
Claim(p) is true.

If p^, = p we are done. So, suppose p^, = p. Let l be a step such that p < l ≤ p^,.
Assume Claim(g) is true for all g, p ≤ g < l ≤ p^,. We prove that Claim(l) is true. Let
v ∈ V(Q^,, l)\P_l. From (2) and (3), v ∈ V(Q^,, g)\P_g for each step g, p ≤ g < l. From
Consequence(g) (p ≤ g < l), v ∈ V(Q, g) and

F(Q, g, v) = F(Q^,, g, v) for each step g, p ≤ g < l.                 (4)

Since v ∈ V (Q^,, l), v is not removed at the end of step l - 1 in TTC(Q^,). Then by (1)
and (4), v is also not removed at the end of step l - 1 in TTC(Q). Hence, v ∈ V(Q, l).

²⁸It follows immediately from the proof that the directed paths associated with F(Q, l, v) and F(Q', l, v)
in V(Q, l) and V(Q', l), respectively, also coincide.

36

<<   33   34   35   36   37   38   39   >>

More intriguing information