Constrained School Choice



Observation B.1 In the TTC algorithm, once a student points to a school it will keep
on pointing to the school in subsequent steps until he is assigned to a seat at the school
or until the school has no longer available seats. In other words, if i
V (Q, l) I for
some step l of TTC(Q) and e(Q, l, i) = s
S, then e(Q, r, i) = s for all steps r with
l
r min{σ(Q, i), σ(Q, s)}. Similarly, once a school points to a student it will keep on
pointing to the student in subsequent steps until the student is assigned to a seat at this
or some other school. In other words, if s
V (Q, l) S for some step l of TTC(Q) and
e(Q, l, s) = i
I, then e(Q, r, s) = i for all steps r with l r σ(Q, i).

We now proceed to establish some preliminary results and slightly technical lemmas
to be able to prove Theorems 5.4 and 7.2. The proof of the next lemma is omitted.

Lemma B.2 For any school choice problem P and any quota k, Oτ (P, k) IR(P) .

In order to avoid possible confusion we will sometimes use an additional superindex
Q and write q
sQ,r instead of qsr .

Lemma B.3 Let Q QI. Let i I and Qi Q. Define Q' := (Qi,Q-i). Suppose
τ
(Q)(i) = τ(Q')(i). Let p := σ(Q,i), p:= σ(Q',i), and r :=min{p,p'}. Then,

(a) at steps 1,... ,r 1, the same cycles form in TTC(Q) and TTC(Q');

(b) i V(Q,r) = V(Q',r) and for each school s V(Q, r)S, qQ,r = qQ',r;

(c) e(Q, r, v) = e(Q', r, v) for each agent v V(Q, r)\i;

(d) there is a cycle C with i C in either G(Q,r) or G(Q',r) (but not both).26

Proof Item (a) follows from the proof of a result in Abdulkadiroglu and Sonmez (1999,
Lemma 1) or, alternatively, Abdulkadiroglu and Sonmez (2003, Lemma). As for Item (b),
from the definition of r, i
V(Q, r) V(Q', r). The remainder of Item (b) follows directly
from Item (a). Item (c) follows from Item (b) and the fact that Q
j = Qj for all j I\i.
As for Item (d), by definition of r, there is a cycle C with i C in G(Q,r) or G(Q',r).
From Item (c) and τ(Q)(i) = τ(Q
')(i), e(Q,r, i) = e(Q',r, i). In particular, C is not a
cycle in both G(Q,r) and G(Q
',r). This proves Item (d).                           

Lemma B.4 Let φ be a mechanism such that for any Q QI, any i I, Qi = φ(Q')(τ)
Q(1) implies φ(Qi,Q-i) = φ(Q). Then, for any school choice problem P and quotas
k < k',
Eψ(P,k) Eψ(P,kr).

26Note that it is still possible that there is another cycle C (i.e., C = C) with i C present in the
other graph.

34



More intriguing information

1. Cryothermal Energy Ablation Of Cardiac Arrhythmias 2005: State Of The Art
2. An alternative way to model merit good arguments
3. Poverty transition through targeted programme: the case of Bangladesh Poultry Model
4. The name is absent
5. The name is absent
6. Developmental Robots - A New Paradigm
7. The name is absent
8. Does South Africa Have the Potential and Capacity to Grow at 7 Per Cent?: A Labour Market Perspective
9. The name is absent
10. The name is absent