Constrained School Choice

Assume Claim(I) is not true, i.e., x := e(Q,l,v) = e(Q',l,v) =: x'. Since v ∈ Pl, x' ∈
Pl. By (2), x' ∈ Pl_-1. By (3) and x' ∈ V(Q', l), x' ∈ V(Q', l — 1). By Consequence(l — 1),
x' ∈ V(Q,l — 1). We distinguish between two cases.

Case 1: Agent x^' is removed at the end of step l — 1 in TTC(Q).

From (2) and (3), x^' ∈ V (Q^', g)\Pg for each step g, p ≤ g < l. From Consequence(g)
(p ≤ g < l), x^' ∈ V(Q, g) and

F(Q, g, x^') = F (Q^', g, x^') for each step g, p ≤ g < l.                 (5)

By (1), (5), and the fact that x^' is removed at the end of step l — 1 in TTC(Q), x^' is also
removed at the end of step l — 1 in TTC(Q^'). Hence, x^' ∈ V(Q^', l), a contradiction with
e(Q^', l, v) = x^'.

Case 2: Agent x^' is not removed at the end of step l — 1 in TTC(Q).

Then, x^' ∈ V(Q, l). Since e(Q, l, v) = x = x^', we have xQvx^' (if v is a student) or
f_v(x) < f_v(x^') (if v is a school). Hence, since e(Q^', l, v) = x^', x ∈ V (Q^', l). So, agent x
was removed at some step g*, 1 ≤ g* ≤ l — 1, in TTC(Q'). In fact, by (1), p ≤ g* ≤ l — 1.
Note that no agent in P_p' is removed before the end of step p' in TTC(Q'). So, x ∈ Pp’.
By (2), x ∈ P_g*. Hence, x ∈ V(Q',g*)∖P_g*. By an argument similar to that of Case 1,
x is also removed at the end of step g* in TTC(Q). Hence, x ∈ V(Q,l), a contradiction
with e(Q, l, v) = x.                                                                        ■

Lemma B.8 Let Q ∈ Q^I . Let i ∈ I and Q^'_i ∈ Q. Define Q^' := (Q^'_i, Q_-i). Suppose there
is a student j ∈ I\i with τ (Q)(j) = τ(Q^')(j). Then,

(a) σ(Q, i) ≤ σ(Q, j) and [σ(Q, i) = σ(Q, j) only if i and j are assigned in the same
cycle in TTC(Q)], and

(b) σ(Q^', i) ≤ σ(Q^', j) and [σ(Q^', i) = σ(Q^', j) only if i and j are assigned in the same
cycle in TTC(Q^')].

Proof By non bossiness of τ, τ (Q)(i) = τ (Q^')(i). Let p := σ(Q, i) and p^' := σ(Q^', i).
Assume, without loss of generality, p ≤ p^'. Then, by definition of p and Lemma B.3(d),
there is a cycle C in G(Q, p) with i ∈ C but not present in G(Q^', p).

We first prove (a). By Lemma B.3(a,b), for each student h ∈ I\i with σ(Q, h) < p or
σ(Q^', h) < p, τ (Q)(h) = τ(Q^')(h). Let r := σ(Q, j) and r^' := σ(Q^', j). Since τ(Q)(j) =
τ (Q^')(j), we have r, r^' ≥ p. So, σ(Q, i) = p ≤ r = σ(Q, j). Suppose σ(Q, i) = σ(Q, j).
We have to show that j ∈ C. Suppose j ∈ C. Then, j ∈ C^* for some cycle C^* ,
C^* = C, in G(Q, p). Note i ∈ C^*. By Lemma B.3(b), V(Q,p) = V (Q^', p). Hence, since

37

<<   34   35   36   37   38   39   40   >>

More intriguing information