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. Estimated Open Economy New Keynesian Phillips Curves for the G7
2. The name is absent
3. Fiscal Policy Rules in Practice
4. Innovation and business performance - a provisional multi-regional analysis
5. Passing the burden: corporate tax incidence in open economies
6. Infrastructure Investment in Network Industries: The Role of Incentive Regulation and Regulatory Independence
7. SAEA EDITOR'S REPORT, FEBRUARY 1988
8. Keystone sector methodology:network analysis comparative study
9. Who runs the IFIs?
10. Effects of red light and loud noise on the rate at which monkeys sample the sensory environment