Constrained School Choice



V (Q, σ(Q, s2)). Hence, σ(Q, j1) < σ(Q, s2) = σ(Q, j2), contradicting (13). Since j1 = j2,
f
s2 (j2) < fs2 (j1).

Let s = s1, s = s2, i = j1 , and i = j2. We have just shown that fs(i) < fs(i). By
Step 4, f
s(i) < fs(i). Define Is := As(Q)i and Is := As(Q)i'. By Step 1(b,c), Is and
Is are disjoint sets such that |Is| = qs — 1 and Is' | = qs' — 1. Moreover, by definition of
A
s(Q) and i, Is Uf(i). Similarly, Is Uf'(is). Hence, schools s and stogether with
students
i and iconstitute an X-cycle.                                           □■

Proof of Theorem 7.2 Follows from Lemma B.12 and Proposition B.13.         

C Appendix: Proofs of Results in Section 8

Proof of Lemma 8.1 Let φ := γ, τ. We will prove that φ(Pik,Q-i)(i) = φ(Q')(i') for
all
Qi Q(k)11 or φ(Pk,Q-i)Piφ(Qi,Q-i) for some Q-i Q(k)Ii. (This obviously
completes the proof as it implies that no strategy k-dominates P
ik.)

Suppose φ(Pik, Q-i)(i) = φ(Q')(i') for some Q-i Q(k)Ii. We have to show that
for some Q
-i Q(k)Ii, φ(Pik,Q-i)Piφ(Qi,Q-i). Suppose that for some Q- Q1'^l,
φ(Q
i,Q-i)Piφ(Pik, Q-i). Since φ(Pik,Q-i)(i')Rii, we have s := φ(Qi, Q-i)(i) S. From
Lemma A.1 (for γ) and Lemma B.5 (for τ),
φ(s, Q-i)(i) = φ(Qi, Q-i)(i).

Suppose s is also listed in Pik. Then,
φ(Pk,C^-i)(i)Riφ(P k ,Q-i)(i = φ(s,Q-i}(i) = s,                 (14)

where P'k is the preference relation obtained from Pik by putting ' in the first position.
The first relation follows from Lemma 4.2. The second relation follows from the fact that
the assignment by the DA/TTC algorithm does not change if a student makes more schools
acceptable
and puts them below the school he is assigned to. Clearly, (14) contradicts
φ(Qi, Q-i)Piφ(Pk, Q-i). Hence, ' is not listed in Pik.

Let S := {s Ss : sQis }. The fact that ' is not listed in Pik together with the
definition of
Pik implies that there is a school s S listed in Pik with sPis. Let s* be the
P
i-best school among the schools s S listed in Pik with sPis.

Suppose φ = γ. Since φ(Qi,Q-i) NW (Qi,Q-i), φ(Qi, Q-i)(s) = qs for all s S.
Clearly, for all s S, i φ(Qi,Q-i)(s'). Also, for all s,t S with s = t, φ(Qi,Q-i)(s')
φ(Qi, Q-i)(t) = 0. So we can define for j Ii,

Qj:=


s if j φ(Qi, Q-i)(s) for some s S,
0 otherwise.

44



More intriguing information

1. Investment and Interest Rate Policy in the Open Economy
2. EMU's Decentralized System of Fiscal Policy
3. Income Mobility of Owners of Small Businesses when Boundaries between Occupations are Vague
4. Income Growth and Mobility of Rural Households in Kenya: Role of Education and Historical Patterns in Poverty Reduction
5. Technological progress, organizational change and the size of the Human Resources Department
6. Deprivation Analysis in Declining Inner City Residential Areas: A Case Study From Izmir, Turkey.
7. Secondary stress in Brazilian Portuguese: the interplay between production and perception studies
8. The name is absent
9. The name is absent
10. Estimating the Impact of Medication on Diabetics' Diet and Lifestyle Choices