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'
P
l. 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 l1 in TTC(Q).

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

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

By (1), (5), and the fact that x' is removed at the end of step l1 in TTC(Q), x' is also
removed at the end of step
l1 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 l1 in TTC(Q).

Then, x' V(Q, l). Since e(Q, l, v) = x = x', we have xQvx' (if v is a student) or
fv(x) < fv(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
Pg*. Hence, x V(Q',g*)Pg*. 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 QI . 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



More intriguing information

1. AGRICULTURAL TRADE IN THE URUGUAY ROUND: INTO FINAL BATTLE
2. The name is absent
3. How does an infant acquire the ability of joint attention?: A Constructive Approach
4. The name is absent
5. The name is absent
6. Chebyshev polynomial approximation to approximate partial differential equations
7. The Making of Cultural Policy: A European Perspective
8. EU Preferential Partners in Search of New Policy Strategies for Agriculture: The Case of Citrus Sector in Trinidad and Tobago
9. Markets for Influence
10. Strategic monetary policy in a monetary union with non-atomistic wage setters