Constrained School Choice



Proof Let Q Eψ(P,k). Suppose Q Eψ(P,k'). Then, there is a student i with a
strategy
Qi Q(ki) such that φ(Qi, Q-i)Piφ(Q). Let Qi := φ(Qi,Q-i)(i). Clearly, Qi
Q
(k). By assumption, φ(Qi,Q-i) = φ(Qi,Q-i). So, φ(Qi,Q-i)Piφ(Q), contradicting
Q
Eψ(P, k). Hence, Q Eψ(P, k').                                                   

Proposition B.5 Forany Q QI, any i I, Qi = τ(Q)(i) Q(1) implies τ(Qi,Q-i) =
τ (Q)
. In particular, for any school choice problem P and quotas k < k, Eτ (P, k)
E
τ (P, k).

Proof Let Q QI. Let i I and define Qi := τ(Q)(i) Q(1). Define Q' := (Qi,Q-i).
We have to show that τ(Q
i) = τ(Q). By non bossiness of τ,27 it is sufficient to show
that τ(Q
i)(i) = τ(Q)(i). If τ(Q)(i) = i, then from the definition of the TTC algorithm,
τ(Q
i)(i) = i = τ (Q)(i).

So, suppose τ (Q)(i) =: s S. Suppose to the contrary that τ(Qi)(i) = τ (Q)(i). Then,
since Q
ii = τ (Q)(i) = s, student i remains unassigned under Qi, i.e., τ (Qi)(i) = i. Let
p := σ(Q, i), p
i := σ(Qi, i), and r := min{p, pi}. By Lemma B.3(d), there is a cycle C
with i
C in either G(Q, r) or G(Qi, r) (but not both).

Suppose cycle C is in G(Q, r) but not in G(Qi, r). Since student i is assigned through
cycle C and τ (Q)(i) = s, e(Q, r, i) = s. Since e(Q
i, r, i) = e(Q, r, i) and Qii = τ (Q)(i) = s,
e(Q
i, r, i) = i. Hence, at the beginning of step r of TTC(Qi), school s has no avail-
able seats,
i.e., qQ ,r = 0. By Lemma B.3(b), qQ,r = qQ ,r = 0. So, e(Q,r, i) = s, a
contradiction.

So, cycle C is in G(Qi, r) but not in G(Q, r). If e(Qi, r, i) = s, then τ (Qi)(i) = s,

a contradiction with τ (Qi)(i) = τ (Q)(i). So by Qii = τ (Q)(i) = s, e(Qi, r, i) = i, i.e.,

C = (i) is a self-cycle. Since i V (Q, r) and τ (Q)(i) = s, qsQ,r > 0. By Lemma B.3(b),
q
Q ,r = qQ,r > 0. So, s V(Qi, r). But then from Qi = s, e(Qi, r, i) = s, a contradiction.
We conclude that τ(Q
i)(i) = τ(Q)(i).                                                  

Lemma B.6 Let Q QI. Let v,vi I S, v = vi. Suppose v' P(Q,l,v) at some
step
l of TTC(<Q). Then, σ(Q,v) σ(Q,vi) and [σ(Q,v) = σ(Q,vi) only if v and v' are
removed in the same cycle].

Proof By Observation B.1, each agent in the path from vi to v will keep on pointing to
its (direct) follower at least until the step in which agent v is removed,
i.e., step σ(Q,v).

27Papai’s (2000) main result implies that τ is group strategy-proof. Group strategy-proofness implies
non bossiness.

35



More intriguing information

1. The name is absent
2. Gender stereotyping and wage discrimination among Italian graduates
3. Iconic memory or icon?
4. Types of Tax Concessions for Promoting Investment in Free Economic and Trade Areas
5. The name is absent
6. The Advantage of Cooperatives under Asymmetric Cost Information
7. Monetary Policy News and Exchange Rate Responses: Do Only Surprises Matter?
8. WP 36 - Women's Preferences or Delineated Policies? The development or part-time work in the Netherlands, Germany and the United Kingdom
9. A Critical Examination of the Beliefs about Learning a Foreign Language at Primary School
10. The Global Dimension to Fiscal Sustainability