V (Q, σ(Q, s2)). Hence, σ(Q, j1) < σ(Q, s2) = σ(Q, j2), contradicting (13). Since j1 = j2,
fs2 (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, fs(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
As(Q) and i, Is ⊆ Uf(i). Similarly, Is’ ⊆ Uf'(is). Hence, schools s and s’ together with
students i and i’ constitute 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 Q—i ∈ Q(k)11∖ or φ(Pk,Q-i)Piφ(Qi,Q-i) for some Q-i ∈ Q(k)I∖i. (This obviously
completes the proof as it implies that no strategy k-dominates Pik.)
Suppose φ(Pik, Q-i)(i) = φ(Q')(i') for some Q-i ∈ Q(k)I∖i. We have to show that
for some Q-i ∈ Q(k)I∖i, φ(Pik,Q-i)Piφ(Qi,Q-i). Suppose that for some Q- ∈ Q1'∖^l,
φ(Qi,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 ∈ S∖s : 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
Pi-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 ∈ I∖i,
Q’j:=
s if j ∈ φ(Qi, Q-i)(s) for some s ∈ S,
0 otherwise.
44
More intriguing information
1. The Economic Value of Basin Protection to Improve the Quality and Reliability of Potable Water Supply: Some Evidence from Ecuador2. The name is absent
3. The name is absent
4. The name is absent
5. The name is absent
6. Do the Largest Firms Grow the Fastest? The Case of U.S. Dairies
7. Epistemology and conceptual resources for the development of learning technologies
8. On Evolution of God-Seeking Mind
9. Computational Experiments with the Fuzzy Love and Romance
10. The constitution and evolution of the stars