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 τ(Qi) = τ(Q). By non bossiness of τ,27 it is sufficient to show
that τ(Qi)(i) = τ(Q)(i). If τ(Q)(i) = i, then from the definition of the TTC algorithm,
τ(Qi)(i) = i = τ (Q)(i).
So, suppose τ (Q)(i) =: s ∈ S. Suppose to the contrary that τ(Qi)(i) = τ (Q)(i). Then,
since Qii = τ (Q)(i) = s, student i remains unassigned under Qi, i.e., τ (Qi)(i) = i. Let
p := σ(Q, i), pi := σ(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(Qi, r, i) = e(Q, r, i) and Qii = τ (Q)(i) = s,
e(Qi, 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),
qQ ,r = qQ,r > 0. So, s ∈ V(Qi, r). But then from Qi = s, e(Qi, r, i) = s, a contradiction.
We conclude that τ(Qi)(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 absent2. INTERACTION EFFECTS OF PROMOTION, RESEARCH, AND PRICE SUPPORT PROGRAMS FOR U.S. COTTON
3. Income Growth and Mobility of Rural Households in Kenya: Role of Education and Historical Patterns in Poverty Reduction
4. Langfristige Wachstumsaussichten der ukrainischen Wirtschaft : Potenziale und Barrieren
5. A Duality Approach to Testing the Economic Behaviour of Dairy-Marketing Co-operatives: The Case of Ireland
6. Sex differences in the structure and stability of children’s playground social networks and their overlap with friendship relations
7. Convergence in TFP among Italian Regions - Panel Unit Roots with Heterogeneity and Cross Sectional Dependence
8. Sex-gender-sexuality: how sex, gender, and sexuality constellations are constituted in secondary schools
9. Integration, Regional Specialization and Growth Differentials in EU Acceding Countries: Evidence from Hungary
10. Human Rights Violations by the Executive: Complicity of the Judiciary in Cameroon?