Constrained School Choice



By the assumption that φ = γ, φ(Qi,Q-i) S(Qi,Q-i). Hence, fs(j) < fs(i) for all
s
S and all j φ(Qi, Q-i)(s). From φ(Qi, Q-i) S (Qi, Q-i) and the definition of Q-i,
φ(Qi,Q-i)(i) = s. Similarly, φ(Pik, Q-i)(i) = s*. By definition of s*, φ(Pik, Q-i)(i) =
s*Pis = φ(Qi, Q-i)(i), which completes the proof for the case φ = γ.

Suppose φ = τ. For any s S define Is 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 sQis = φ(Qi, Q-i)(i) for all s S it follows that for all s S,

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

j I\i,


Qj:={ 0


Since sQis = φ(Qi, Q-i)(i) for all s S it follows that fs(j) < fs(i) for all s S and all

j Is. From the definition of Q-i and the TTC algorithm, φ(Qi, Q-i)(i) = s. Similarly,
φ(Pk, Q-i)(i) = s*, which completes the case φ = τ and hence the proof.             

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

Let i M(γ(P)). Denote s := γ(P)(i) S. Suppose to the contrary that sPiγ(P k)(i).
Let Q
i := 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), Q
i 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, γ(Pk)(i)Ris = γ(P)(i).        

Proof of Proposition 8.6 In Example 8.3, γ(P) = {{i1, s1}, {i2, s3}, {i3, s2}} 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



More intriguing information

1. LABOR POLICY AND THE OVER-ALL ECONOMY
2. The economic doctrines in the wine trade and wine production sectors: the case of Bastiat and the Port wine sector: 1850-1908
3. The name is absent
4. Ein pragmatisierter Kalkul des naturlichen Schlieβens nebst Metatheorie
5. Skills, Partnerships and Tenancy in Sri Lankan Rice Farms
6. Synchronisation and Differentiation: Two Stages of Coordinative Structure
7. The name is absent
8. Wage mobility, Job mobility and Spatial mobility in the Portuguese economy
9. The name is absent
10. CURRENT CHALLENGES FOR AGRICULTURAL POLICY