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(kⁱ) 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ⁱ) = τ(Q). By non bossiness of τ,27 it is sufficient to show
that τ(Qⁱ)(i) = τ(Q)(i). If τ(Q)(i) = i, then from the definition of the TTC algorithm,
τ(Qⁱ)(i) = i = τ (Q)(i).

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

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

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

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

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

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

Proof By Observation B.1, each agent in the path from vⁱ 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).

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

35

<<   <   32   33   34   35   36   37   38   >   >>