Constrained School Choice

e(Q,p,v) = e(Q',p,v) for each agent v ∈ V (Q,p)∖i, C * is also a cycle in G(Q',p). In
particular, τ(Q)(j) = τ(Q')(j), a contradiction. This completes the proof of (a).

We now prove (b). We distinguish between two cases.

Case 1: j ∈ P(Q',p, i).

Then, (b) follows directly from Lemma B.6 with Q = Q’, v' = j, and v = i.

Case 2: j ∈ P(Q',p,i).

Assume that (b) is not true. In other words, assume that σ(Q', i) > σ(Q', j) or [σ(Q', i) =
σ(Q', j) and i and j are assigned in different cycles in TTC(Q^,)]∙ Then, σ(Q,i) = p ≤
r’ = ^σ(Q^{, j)} ≤ ^σ(Q'^,i)∙

Note that by definition of r', j ∈ V(Q', r’). Suppose j ∈ (P(Q', r’, i) ∪ i). Since j = i,
j ∈ P(Q',r',i). By Lemma B.6, σ(Q',i) ≤ σ(Q,j) and [σ(Q',i) = σ(Q',j) only if i and
j are removed in the same cycle in TTC(Q’)]. This contradicts the assumption that (b)
is not true. So, j ∈ (P(Q',r',i) ∪ i). In other words, j ∈ V(Q',r')∖(P(Q',r',i) ∪ i).
Hence, by Lemma B.7, j ∈ V(Q, r’) and F(Q,r',j) = F(Q',r',j). Since σ(Q',j) = r’,
student j forms part of a cycle, say C', in G(Q',r'). Hence, C' = F(Q',r',j). So, also
C^’ = F(Q, r^’, j). Hence, student j is assigned to the same school (or himself) in TTC(Q)
and TTC(Q'), contradicting τ(Q)(j) = τ(Q')(j). This completes the proof of (b).     ■

Proposition B.9 Let P be a school choice problem. Let 2 ≤ k ≤ m. Let Q ∈ E^τ (P, k).
Define Q_i := τ(Q)(i) for all i ∈ I. Then, Q ∈ E^τ (P, 1) and τ(Q) = τ(Q). In particular,
O^τ(P, k) ⊆ O^τ (P, 1).

Proof It is sufficient to prove the following claim.

Claim: Let P be a school choice problem. Let 2 ≤ k ≤ m, Q ∈ E^τ (P, k), and j ∈ I. Let
Qj := τ(Q)(j). Then, Q := (Qj,Q-j) ∈ E^τ(P,k).

Indeed, if the Claim is true then we can pick students one after another and each time
apply both the Claim and Proposition B.5 to eventually obtain a profile Q ∈ E^τ(P, k)
with τ(Q) = τ(Q) and where for all j ∈ I, Qj = τ(Q)(j). By construction, Q ∈ Q(1)I.
So, Q ∈ E^τ(P, 1).

To prove the Claim, suppose Q ∈/ E^τ(P, k). Then, there is a student i with a profitable
deviation at Q in Γ^τ (P, k). In fact, by Proposition B.5 there is a strategy Q^’_i ∈ Q(1) with

τ (Qi,Q)-i)PiT (Q_i,Q-_i).                                   (6)

We claim i = j . Suppose i = j . Then, Q-i = Q-j = Q-j . So, (6) becomes τ (Q^’_j , Q-j )Pj
τ(Qj , Q_-j ), contradicting Q ∈ E^τ (P, k). So, i = j .

38

<<   35   36   37   38   39   40   41   >>

More intriguing information