Constrained School Choice



B.3(b,c), j*+1 P(Qr,y,ir). Hence, σ(Qr, j*+1) y = σ(Qr,ir). Again a contra-
diction. So, σ(Q
r,j*+1) σ(Qr, ir).]

O2. For all i A^(Qr) with f^‰) f^(i), σ(Qr,i) σ(Qr,j^).

Suppose jr Asr(Qr). Note fs^(jr*) fs^(jr). From O2 (with i = jr) and
O1, σ(Q
r,jr) σ(Qr,j^ ≥ σ(Qr,ir).

Suppose now jr+1 Asr+1 (Qr). Assume σ(Qr, jr+1) < σ(Qr, ir). Then,

jr+1 = ir.                                          (11)

We consider two cases.

Case 1: σ(Qr, ir) σ(Q, ir).

Then, σ(Qr, jr+1) < min{σ(Qr, ir), σ(Q, ir)}. From Lemma B.3(a) it follows that σ(Q, jr+1)
= σ(Q
r, jr+1). So,

σ(Q, jr+1) <σ(Q,ir).                               (12)

However, under TTC(Q), ir is in a cycle with sr+1 and jr+1 is in the last cycle of sr+1.
So, σ(Q, j
r+1) σ(Q, ir), a contradiction to (12).

Case 2: σ(Q, ir) < σ(Qr, ir).

If σ(Qr, jr+1) < σ(Q, ir), then σ(Qr, jr+1) < min{σ(Qr, ir), σ(Q, ir)} which yields the
same contradiction as in Case 1. Therefore, σ(Q, i
r) σ(Qr, jr+1).

From Observation B.1 and the assumption that σ(Qr, jr+1) < σ(Qr, ir) it follows that
for each l
σ(Qr, jr+1), jr+1 / P(Qr, l, ir). From (11) and Lemma B.7 it follows that for
each l with σ(Q, i
r) l σ(Qr, jr+1), F (Q, l, jr+1) = F (Qr, l, jr+1) (as directed paths).
So, by taking l = σ(Q
r, jr+1), we obtain that jr+1’s cycle under TTC(Q) is the same as
under TTC(Q
r). In particular, jr+1 Asr+1 (Qr), a contradiction.

Since both cases give a contradiction we conclude that σ(Qr,jr+1) ≥ σ(Qr,ir).        □

Step 5 There is an X -cycle.

We can assume, without loss of generality, that among the students in {j1 , . . . , jp} student
j
1 is (one of) the last one(s) to be assigned to a school under TTC(Q), i.e.,

σ(Q, j1) σ(Q,jr) for any r {1, . . . ,p}.                       (13)

Suppose fs2 (j1) < fs2 (j2). By definition of j2, school s2 points to student j2 in the
last, q
s2 -th, cycle of s2 under TTC(Q), which o ccurs at step σ(Q, s2). Hence, j1

43



More intriguing information

1. Impacts of Tourism and Fiscal Expenditure on Remote Islands in Japan: A Panel Data Analysis
2. The name is absent
3. The name is absent
4. The name is absent
5. Towards a framework for critical citizenship education
6. Review of “From Political Economy to Economics: Method, the Social and Historical Evolution of Economic Theory”
7. Bargaining Power and Equilibrium Consumption
8. Sex differences in the structure and stability of children’s playground social networks and their overlap with friendship relations
9. INSTITUTIONS AND PRICE TRANSMISSION IN THE VIETNAMESE HOG MARKET
10. The name is absent