Constrained School Choice

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

Let s = s₁, s^′ = s₂, i = j₁ , and i^′ = j₂. We have just shown that f_s′ (i^′) < f_s′ (i). By
Step 4, fs(i) < fs(i’). Define Is := A_s(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’ ⊆ U^f'(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 φ(Pi^k,Q-_i)(i) = φ(Q')(i') for
all Q—i ∈ Q(k)¹¹∖ or φ(P^k,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 P_i^k.)

Suppose φ(P_i^k, Q_-i)(i) = φ(Q')(i') for some Q_-i ∈ Q(k)I∖ⁱ. We have to show that
for some Q-_i ∈ Q(k)I∖ⁱ, φ(P_i^k,Q-_i)Piφ(Qi,Q-_i). Suppose that for some Q- ∈ Q¹'∖^^l,
φ(Qi,Q-i)Piφ(P_i^k, Q-_i). Since φ(P_i^k,Q-i)(i')Rii, we have s := φ(Q_i, Q-i)(i) ∈ S. From
Lemma A.1 (for γ) and Lemma B.5 (for τ), φ(s, Q_-i)(i) = φ(Q_i, Q_-i)(i).

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

where P'^k is the preference relation obtained from Pi^k 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
φ(Q_i, Q-_i)P_iφ(P^k, Q_-i). Hence, ' is not listed in Pi^k.

Let S := {s ∈ S∖s : sQ_is }. The fact that ' is not listed in Pi^k together with the
definition of Pi^k implies that there is a school s ∈ S listed in Pi^k with sP_is. Let s* be the
P_i-best school among the schools s ∈ S listed in Pi^k with sP_is.

Suppose φ = γ. Since φ(Q_i,Q-_i) ∈ NW (Q_i,Q-_i), ∖φ(Qi, Q-i)(s)∣ = qs for all s ∈ S.
Clearly, for all s ∈ S, i ∈ φ(Q_i,Q-_i)(s'). Also, for all s,t ∈ S with s = t, φ(Q_i,Q-_i)(s') ∩
φ(Q_i, Q-_i)(t) = 0. So we can define for j ∈ I∖i,

s if j ∈ φ(Q_i, Q-_i)(s) for some s ∈ S,
0 otherwise.

44

<<   <   41   42   43   44   45   46   47   >   >>