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. A COMPARATIVE STUDY OF ALTERNATIVE ECONOMETRIC PACKAGES: AN APPLICATION TO ITALIAN DEPOSIT INTEREST RATES2. Dual Track Reforms: With and Without Losers
3. Insecure Property Rights and Growth: The Roles of Appropriation Costs, Wealth Effects, and Heterogeneity
4. The name is absent
5. GENE EXPRESSION AND ITS DISCONTENTS Developmental disorders as dysfunctions of epigenetic cognition
6. Naïve Bayes vs. Decision Trees vs. Neural Networks in the Classification of Training Web Pages
7. A Consistent Nonparametric Test for Causality in Quantile
8. Program Semantics and Classical Logic
9. Ability grouping in the secondary school: attitudes of teachers of practically based subjects
10. An Empirical Analysis of the Curvature Factor of the Term Structure of Interest Rates