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. Government spending composition, technical change and wage inequality
2. Placentophagia in Nonpregnant Nulliparous Mice: A Genetic Investigation1
3. 09-01 "Resources, Rules and International Political Economy: The Politics of Development in the WTO"
4. A Study of Prospective Ophthalmology Residents’ Career Perceptions
5. A novel selective 11b-hydroxysteroid dehydrogenase type 1 inhibitor prevents human adipogenesis
6. Industrial Employment Growth in Spanish Regions - the Role Played by Size, Innovation, and Spatial Aspects
7. The Folklore of Sorting Algorithms
8. Magnetic Resonance Imaging in patients with ICDs and Pacemakers
9. Feeling Good about Giving: The Benefits (and Costs) of Self-Interested Charitable Behavior
10. Evidence on the Determinants of Foreign Direct Investment: The Case of Three European Regions