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. The name is absent
2. Spatial Aggregation and Weather Risk Management
3. Whatever happened to competition in space agency procurement? The case of NASA
4. Conditions for learning: partnerships for engaging secondary pupils with contemporary art.
5. Globalization, Divergence and Stagnation
6. Text of a letter
7. The Distribution of Income of Self-employed, Entrepreneurs and Professions as Revealed from Micro Income Tax Statistics in Germany
8. On s-additive robust representation of convex risk measures for unbounded financial positions in the presence of uncertainty about the market model
9. The East Asian banking sector—overweight?
10. Monetary Discretion, Pricing Complementarity and Dynamic Multiple Equilibria