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. Program Semantics and Classical Logic
2. MATHEMATICS AS AN EXACT AND PRECISE LANGUAGE OF NATURE
3. An Attempt to 2
4. Target Acquisition in Multiscale Electronic Worlds
5. An Estimated DSGE Model of the Indian Economy.
6. Return Predictability and Stock Market Crashes in a Simple Rational Expectations Model
7. The name is absent
8. Dual Track Reforms: With and Without Losers
9. What Drives the Productive Efficiency of a Firm?: The Importance of Industry, Location, R&D, and Size
10. Contribution of Economics to Design of Sustainable Cattle Breeding Programs in Eastern Africa: A Choice Experiment Approach