by Cases 1 and 2 and Step 2, this is also the last cycle of sr under TTC(Q). Hence,
sr ∈ 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 sr 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 sr under TTC(Q). Hence, sr ∈ V (Q, l)
and sr ∈ 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 sr ∈ 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 sh appears under TTC(Q), i.e., jh := argmaxj∈Ash (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,
jr = argmaxj∈Asr (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)
< yr, 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), jr+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 Statistic2. 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