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. Human Resource Management Practices and Wage Dispersion in U.S. Establishments2. Optimal Tax Policy when Firms are Internationally Mobile
3. The Impact of Minimum Wages on Wage Inequality and Employment in the Formal and Informal Sector in Costa Rica
4. The name is absent
5. Strategic Policy Options to Improve Irrigation Water Allocation Efficiency: Analysis on Egypt and Morocco
6. The Context of Sense and Sensibility
7. Evidence on the Determinants of Foreign Direct Investment: The Case of Three European Regions
8. Applications of Evolutionary Economic Geography
9. The name is absent
10. The name is absent