Constrained School Choice



by Cases 1 and 2 and Step 2, this is also the last cycle of sr under TTC(Q). Hence,
s
r V (Q, l) and sr V (Qr, l), and (9) holds trivially.

Case 4: σ(Q, ir) < σ(Qr , ir) < l. From the proof of Case 3, sr V (Q, l) and sr
V (Qr, l). Hence, (9) holds trivially.

Case 5: σ(Qr, ir) = l σ(Q, ir). Since σ(Qr, ir) = σ(Qr, sr) + 1, F(Qr, l - 1, sr) is the
last cycle of s
r under T T C(Qr). By Case 1, this is a cycle of sr under TTC(Q). In fact,
by Case 1 and Step 2, this is also the last cycle of s
r under TTC(Q). Hence, sr V (Q, l)
and s
r V (Qr, l), and (9) holds trivially.

Case 6: σ(Qr, ir) σ(Q, ir) and l > σ(Qr, ir). From the proof of Case 5, sr V (Q, l)
and s
r V(Qr,l). Hence, (9) holds trivially.                                        □□

For each school sh CS , let jh be the student to which school sh points in the last
cycle in which s
h appears under TTC(Q), i.e., jh := argmaxjAsh (Q) fsh (j).

Step 4 For any r {1, . . . , p}, fsr (jr) < fsr (jr+1).

Suppose fsr (jr) > fsr (jr+1). From Step 3, jr Asr (Q) = Asr (Qr) and in particular,
j
r = argmaxjAsr (Qr) fsr (j). So,

σ(Qr, jr+1) <σ(Qr,jr) =σ(Qr,sr) =σ(Qr,ir) -1.                 (10)

We will now prove the following claim to complete the proof of this step.

Claim: σ(Qr, ir) σ(Qr, jr+1).

The claim yields a contradiction to (10). Hence, the assumption fsr (jr) > fsr (jr+1) is
false. Note
jr = jr+ι. So, f3r(jr) < f3r(jr+ι).                                                 

Proof of Claim:

Let j'*be the student to which school sr+1 points in ir’s cycle under TTC(Q), i.e.,
e(Q, σ(Q,
ir), sr+1) = jr+1. We make the following two observations (O1 and O2).

O1. σ(Qr,jr*) σ(Qr,ir).

[Proof: Suppose σ(Qr , jr+1) < σ(Qr, ir).

Assume σ(Qr, ir) σ(Q, ir). Denote yr = σ(Qr, ir). From Lemma B.3(a), V(Q, yr) =
V
(Qr,yrr). Bydefinitionof jr+1, jr+1 V(Q,yr). However, by assumption, σ(Qr, jr+1)
< y
r, and hence, jr+1 V(Qr,yr) = V(Q,yr), a contradiction.

So, σ(Q,ir) < σ(Qr,ir). Also note that y := σ(Q,ir) σ(Qr, jr+1) (otherwise, by
Lemma B.3(a), j
r+1 V(Q,y), contradicting the definition of jr+1). By Lemma

42



More intriguing information

1. On the Existence of the Moments of the Asymptotic Trace Statistic
2. The name is absent
3. On Dictatorship, Economic Development and Stability
4. Tariff Escalation and Invasive Species Risk
5. Poverty transition through targeted programme: the case of Bangladesh Poultry Model
6. Biological Control of Giant Reed (Arundo donax): Economic Aspects
7. The name is absent
8. SLA RESEARCH ON SELF-DIRECTION: THEORETICAL AND PRACTICAL ISSUES
9. The Dictator and the Parties A Study on Policy Co-operation in Mineral Economies
10. The name is absent