Constrained School Choice

By the assumption that φ = γ, φ(Q_i,Q_-i) ∈ S(Q_i,Q_-i). Hence, f_s(j) < f_s(i) for all
s ∈ S and all j ∈ φ(Q_i, Q_-i)(s). From φ(Q_i, Q-_i) ∈ S (Qi, Q-_i) and the definition of Q-_i,
φ(Qi,Q-i)(i) = s. Similarly, φ(Pi^k, Q-i)(i) = s*. By definition of s*, φ(Pi^k, Q-i)(i) =
s*Pis = φ(Qi, Q-_i)(i), which completes the proof for the case φ = γ.

Suppose φ = τ. For any s ∈ S define I_s as the set of students j that are assigned a
seat through a cycle (in the TTC algorithm) of which school s is part and such that s
points to j . Formally,

I                                  /                 ∕^∙∙S                                     ∕^∙∙S                            ∖                                     /                 ∕^∙∙S                                     ∕^∙∙S                            ∖ I

Is := {j∙ ∈ I : e ((Qi,Q-i),σ[(Qi,Q-i),j],sJ = j ∈ P ((Qi,Q-i),σ[(Qi,Q-i),j],s)∣.

From Observation B.1 and sQ_is = φ(Qi, Q_-i)(i) for all s ∈ S it follows that for all s ∈ S,

i ∈ I_s and |Is| = q_s. Also, for all s,t ∈ S with s = t, I_s ∩ It = 0. So we can define for
if j ∈ I_s for some s ∈ S ,
otherwise.

Since sQis = φ(Q_i, Q_-i)(i) for all s ∈ S it follows that f_s(j) < f_s(i) for all s ∈ S and all

j ∈ I_s. From the definition of Q-_i and the TTC algorithm, φ(Q_i, Q-_i)(i) = s. Similarly,
φ(P^k, Q-_i)(i) = s*, which completes the case φ = τ and hence the proof.             ■

Proof of Proposition 8.5 BydefinitionoftheDAalgorithm, |M (γ(P^k ))| ≤ |M (γ(P ))|.
We complete the proof by showing that if i ∈ M(γ(P)), then γ(P ^k)R_iγ(P). (Since
γ(P) ∈ IR(P), γ(P ^k)(i) ∈ S. Hence, i ∈ M(γ(P^k)). But then M(γ(P^k)) = M(γ(P)).)

Let i ∈ M(γ(P)). Denote s := γ(P)(i) ∈ S. Suppose to the contrary that sP_iγ(P ^k)(i).
Let Qi := s. By Lemma A.1, γ(Qi, P_-i)(i) = s. By a result of Gale and Sotomayor
(1985b, Theorem 2) extended to the college admissions model (Roth and Sotomayor, 1990,
Theorem 5.34), Qi ranks γ(Qi, P-_i)(i) weakly higher than γ(Qi, P_-i)(i). So, γ(Qi, P-_i)(i) =
s, contradicting the assumption that P^k ∈ E(P, k). So, γ(P^k)(i)R_is = γ(P)(i).        ■

Proof of Proposition 8.6 In Example 8.3, γ(P) = {{i₁, s₁}, {i₂, s₃}, {i₃, s₂}} and
τ(P) = {{iι, sι}, {i3, s3}, {i2}, {s2}}. So, |M(τ(P))| = 2 < 3 = |M(γ(P))|.

In Example 8.4, γ(P) = {{i2, s3}, {i3, s2}, {i1}, {s1}} and τ(P) = {{i1, s2}, {i2, s3},
{i3,s1}}. So, |M(τ(P))| = 3 > 2 = |M(γ(P))|.                                             ■

45

<<   <   42   43   44   45   46   47   48   >   >>