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. Income Taxation when Markets are Incomplete
2. The name is absent
3. The name is absent
4. Land Police in Mozambique: Future Perspectives
5. An alternative way to model merit good arguments
6. The name is absent
7. Notes on an Endogenous Growth Model with two Capital Stocks II: The Stochastic Case
8. Segmentación en la era de la globalización: ¿Cómo encontrar un segmento nuevo de mercado?
9. AN IMPROVED 2D OPTICAL FLOW SENSOR FOR MOTION SEGMENTATION
10. The name is absent