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 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 Pk ∈ 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 ECONOMY2. 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