**1. On Eﬀective Aﬃrmative Action in School Choice**

**1.6 Appendix for Chapter 1: Proofs of Finite Market Results**

**Notations:**(the following notations are used throughout the proofs)

Let*μ*be the matching by SOSM-R in a random market Γ = (C, P,*,*(q, r* ^{m}*)) and ˜

*μ*be the matching outcome after a stronger aﬃrmative action ˜

*r*

*, ˜*

^{m}*r*

^{m}*> r*

*. Denote the market after ˜*

^{m}*r*

*by ˜Γ = (C, P,*

^{m}*,*(q,

*r*˜

*)). Γ*

^{m}*= (C*

^{m}

^{m}*, P*

^{}*,*(

^{o}*,*

*),(q, r*

^{r}*)) and ˜Γ*

^{m}*= (C*

^{m}

^{m}*, P*

^{}*,*(

^{o}*,*

*),(q,˜*

^{r}*r*

*)) are the two respective markets of Γ and ˜Γ after splitting each school into the original sub-school (c*

^{m}*) and the reserve sub-school (c*

^{o}*).*

^{r}*1.6.1* *Proof of Lemma 1.1*

I prove the Lemma by contradiction. Suppose that if ˜*μ(s) is Pareto dominated byμ(s)*
for all*s∈* *S** ^{m}*, there has at least one majority student

*s*

_{0}

*∈S*

*who prefers ˜*

^{M}*μ*to

*μ*in

˜Γ* ^{m}*, ˜

*μ(s*

_{0})P

_{s}_{0}

*μ(s*

_{0}). Let ˜

*μ(s*

_{0}) =

*c*

_{1}and

*μ(s*

_{0}) =

*c*

_{0}. Since

*s*

_{0}is a majority student, she is rejected by a reserve sub-school. Because

*s*

_{0}prefers

*c*

_{1}to

*c*

_{0}, she must have been rejected by

*c*

_{1}in Γ

*(which leads to the matching*

^{m}*μ), at an earlier step befores*

_{0}applies to

*c*

_{0}. Denote the step when

*s*

_{0}is rejected by

*c*

_{1}in Γ

*step*

^{m}*l*of the SOSM algorithm. At that step,

*c*

_{1}must have exhausted its capacity,

*|μ(c*

_{1})

*|*=

*q*

*c*

_{1}, and

*s*

^{x}*c*

_{1}

*s*

_{0},

*x*=

*o, r, for alls*tentatively accepted by

*c*

_{1}at step

*l. Since ˜μ(s*

_{0}) =

*c*

_{1}, there must have another student, denote by

*s*

_{1}, such that

*s*

_{1}is tentatively accepted by

*c*

_{1}at step

*l*(in Γ

*) but matches with another school in ˜Γ*

^{m}*. Recall that at step*

^{m}*l,s*

_{0}is rejected by

*c*

_{1}, it implies that

*s*

_{1}

^{r}*c*

_{1}

*s*

_{0}. I ﬁrst show that

*s*

_{1}must be a majority student who has applied to

*c*

_{1}at a step earlier than

*l*in Γ

*. Otherwise, if*

^{m}*s*

_{1}

*∈S*

*, because ˜*

^{m}*μ*is Pareto dominated by

*μ*for all

*s∈S*

*, while*

^{m}*μ(s*

_{1}) = ˜

*μ(s*

_{1}), it implies that

*μ(s*

_{1})P

_{s}_{1}

*μ(s*˜

_{1}). Also, recall that

*s*

_{1}is tentatively accepted by

*c*

_{1}before her ﬁnal match in Γ

*,*

^{m}*c*

_{1}

*R*

_{s}_{1}

*μ(s*

_{1}), I have

*c*

_{1}

*P*

_{s}_{1}

*μ(s*˜

_{1}). Since the stronger aﬃrmative action ˜

*r*

*only increases the capacity of some*

^{m}*c*

*, (s*

^{r}_{1}

*, c*

_{1}) forms a

blocking pair in ˜Γ* ^{m}*, which contradicts the stability of ˜

*μ*(with minority reserve). Thus,

*s*

_{1}

*∈S*

*. Obviously,*

^{M}*s*

_{1}applies to

*c*

_{1}at a step earlier than

*l.*

Next, since ˜*μ(s*_{1})=*c*_{1}, while*s*_{1}^{r}*c*1*s*_{0}and*s*_{0}*, s*_{1}*∈S** ^{M}*, it implies that ˜

*μ(s*

_{1})P

*s*

_{1}

*c*

_{1}. Oth-erwise, (s

_{1}

*, c*

_{1}) is a blocking pair in ˜Γ

*. Combine with*

^{m}*c*

_{1}

*R*

*s*

_{1}

*μ(s*

_{1}), I have ˜

*μ(s*

_{1})P

*s*

_{1}

*μ(s*

_{1}).

Denote ˜*μ(s*_{1}) =*c*_{2}. Recall that in Γ* ^{m}*,

*s*

_{1}applies to

*c*

_{1}before step

*l. Without loss of*generality, denote this step by

*l−*1. I can repeat the proceeding arguments for

*s*

_{0}and

*s*

_{1}, and construct a set of

*l*majority students who are all better-oﬀ in ˜Γ

*. That is,*

^{m}˜

*μ(s**i*)P*s**i**c**i**R**s**i**μ(s**i*),*i*=*{*0, . . . , l*−*1*}*,*s**i**∈S** ^{M}*.

*c*

*i*belongs to a set of

*l*schools in which for each

*s*

*i*she is tentatively accepted at step

*l−i. In particular, let step 1 be the step that*initiates the matching in market Γ

*when*

^{m}*s*

*applies to*

_{l−1}*c*

*. Because*

_{l−1}*s*

*applies to*

_{l−1}*c*

*at the ﬁrst step, it implies that*

_{l−1}*c*

_{l−1}*P*

*s*

_{l−1}*c, for allc∈C\c*

*. Recall that*

_{l−1}*c*

*= ˜*

_{l−1}*μ(s*

*),*

_{l−1}which contradicts to ˜*μ(s** _{l−1}*)P

*s*

_{l−1}*c*

*.*

_{l−1}*1.6.2* *Proof of Theorem 1.1*

(i)*Type-speciﬁc acyclicity* =*⇒Respect the spirit of reserve-based aﬃrmative action.* I
prove the contrapositive, such that if*μ(s)R**s*˜*μ(s) for alls∈* *S** ^{m}*, and

*μ(s)P*

*s*

*μ(s) for at*˜ least one

*s∈S*

*, there must contain a type-speciﬁc cycle with at least two schools and three students.*

^{m}Lemma 1.1 indicates that if ˜*μ(s) is Pareto dominated byμ(s) for alls∈* *S** ^{m}*, then
there has at least one

*s*

^{}*∈S*

*,*

^{M}*μ(s*

*)P*

^{}*s*

^{}*μ(s*˜

*). Denote ˜*

^{}*S*=

*{s∈S|μ(s)P*

*s*

*μ(s)*˜

*}*be the set of students strictly prefer the matching

*μ. Becauseμ(s)R*

*s*

*μ(s) for all*˜

*s∈S\S, for those*˜ who are not strictly worse oﬀ after implementing ˜

*r*

*, they are matched with the same school under*

^{m}*μ, i.e.,S\S*˜=

*{s∈S|μ(s) = ˜μ(s)}*.

Choose a set of students from ˜*S, ˜S*^{}*⊆S, such that for all*˜ *s∈* *S*˜* ^{}*, ˜

*μ(s)*=

*s. ˜S*

*is nonempty. Otherwise, there has at least one minority student*

^{}*s∈S*˜and ˜

*μ(s) =s, such*that

*s*and

*μ(s) forms a blocking pair after the stronger aﬃrmative action ˜r*

*. Further, ˜*

^{m}*S*

*contains at least one minority student and one majority student. Because if all*

^{}*s*

^{}*∈S*

^{M}*∩S,*˜

˜

*μ(s** ^{}*) =

*s*

*, then for some*

^{}*s∈S*

^{m}*∩S,*˜

*s*and

*μ(s) forms a blocking pair after ˜r*

*. Without loss of generality, denote*

^{m}*s*

*j*

*∈*

*S*

^{M}*∩S*˜

*who is*

^{}*directly*aﬀected by ˜

*r*

*,*

^{m}^{31}

31A majority student*s*who is directly aﬀected by a stronger aﬃrmative action ˜*r** ^{m}*in the sense that if

*μ*(

*s*) =

*c*and ˜

*μ*(

*s*)=

*c*,

*r*

^{m}*c*

*<*

*r*˜

^{m}*c*, then there is a minority student

*s*

*such that*

^{}*μ*(

*s*

*)=*

^{}*c*,

*cP*

*s*

*μ*(

*s*

*), and*

^{}*s*

*is tentatively accepted by*

^{}*c*at the step when

*s*is rejected. Further, by

*r*

*c*

^{m}*<*˜

*r*

^{m}*c*, I know that

*μ*(

*s*) =

*c*

*,*

^{o}*μ(s**j*) = *c*_{0}. Since *c*_{0}*P**s*_{j}*μ(s*˜ *j*), and ˜*μ* is stable (Hafalir et al., 2013), this implies that

*|μ(c*˜ _{0})*|*=*q**c*_{0},*|μ(c*˜ _{0})*∩S*^{m}*|*= ˜*r*^{m}_{c}_{0}, and for all*s*who are tentatively accepted by*c*^{x}_{0},*s*^{x}*c*_{0}*s**j*,
*x*=*o, r. Sinces**j*is a majority student who is directly aﬀected by the stronger aﬃrmative
action ˜*r** ^{m}*, there has a minority student tentatively accepted by

*c*

_{0}, denote by

*s*

*i*, such that

*c*

_{0}

*P*

*s*

_{i}*μ(s*

*i*) and

*s*

*j*

^{o}*c*

_{0}

*s*

*i*. It implies that

*s*

*i*

*∈*

*c*

^{r}_{0}in ˜Γ

*(because of*

^{m}*s*

*i*

^{r}*c*

_{0}

*s*

*j*).

Otherwise, (s*j**, c*_{0}) forms a blocking pair. However, ˜*μ(s**i*)=*c*_{0}by assumption (otherwise

˜

*μ(s**i*)P*s*_{i}*μ(s**i*)). Since*s**i*cannot be rejected by an majority student from*c*^{r}_{0}, there must
have another minority student, denote by*s**k*, such that*s**k**∈S*^{m}*∩S*˜* ^{}*,

*s*

*k*

*∈μ(c*˜

_{0})

*\μ(c*

_{0}) and

*s*

_{k}

^{r}*c*0

*s*

*. Thus, I have*

_{i}*s**k*^{r}*c*_{0}*s**i*^{r}*c*_{0}*s**j**,* *s**i**, s**k**∈S*^{m}*, s**j**∈S** ^{M}* (1.1)

Denote*μ(s**k*) =*c**k*. Because*c**k**P**s*_{k}*c*_{0}and ˜*μ*is stable, it implies that*|μ(c*˜ *k*)*|*=*q**c** _{k}*, and
there exists a student in ˜

*S*

*, denote by*

^{}*s*

*k*

*−1*, such that

*s*_{k−1}*∈μ(c*˜ *k*)*\μ(c**k*), *s*_{k−1}^{o}*c*_{k}*s**k* (1.2)

Otherwise, (s*k**, c**k*) forms a blocking pair in ˜Γ* ^{m}*. Apply similar arguments of

*s*

*k*

*−1*

*, s*

*k*

and*c*_{0}*, c**k* for each student in ˜*S** ^{}* repeatedly. Because the set of students in ˜

*S*

*are ﬁ-nite, let*

^{}*{s*

_{0}

*, s*

_{1}

*, . . . , s*

*k*

*−2*

*, s*

*k*

*−1*

*} ∈*

*S*˜

^{}*\{s*

*k*

*}*, I can construct a ﬁnite sequence of schools

*c*

_{1}

*, c*

_{2}

*, . . . , c*

*k*

*−1*

*, c*

*k*such that for each

*l*=

*{*0,1,2, . . . , k

*−*1

*}*

*s**l**∈μ(c*˜ * _{l+1}*)

*\μ(c*

*),*

_{l+1}*μ(s*

*l*) =

*c*

*l*

*,*

*c*

*l*

*P*

*s*

_{l}*c*

*(1.3)*

_{l+1}*|μ(c*˜ *l*)*|*=*q**c*_{l}*,* *s*^{x}*c*_{l}*s**l**, x*=*o, r,* for each*s∈μ(c*˜ *l*) (1.4)

In particular, I have

*s*^{o}*c**s** ^{}*, and

*s*is tentatively accepted by

*c*

*(before*

^{r}*s*

*applies to*

^{}*c*) after the stronger aﬃrmative action.

The set of majority students that are directly aﬀected by ˜*r** ^{m}*is nonempty; otherwise,

*μ*(Γ

*) =*

^{m}*μ*(˜Γ

*).*

^{m}⎧⎪

⎨

⎪⎩

*s**l*^{o}*c*_{l+1}*s**l*+1 if*s**l*+1*∈S*^{m}

*s**l*^{r}*c*_{l+1}*s** _{l+1}* if

*s*

_{l+1}*∈S*

^{M}*,*

*l*=

*{*0,1,2, . . . , k

*−*1

*}*

(1.5)

It is not diﬃcult to see that*s*_{0}*≡s**j* by preceding arguments. Combining (1.1) and
(1.5) gives us the cycle condition. The scarcity condition is satisﬁed by (1.2), (1.3) and
(1.4), and the stability of SOSM.

(ii)*Respect the spirit of reserve-based aﬃrmative action*=*⇒Type-speciﬁc acyclicity.*

Suppose that ˜Γ* ^{m}* has a type-speciﬁc cycle, I use a counter-example to show that the
stronger minority reserve policy ˜

*r*

*will cause all minorities worse oﬀ.*

^{m}Recall Example 1.1 that after implementing ˜*r*^{m}_{c}_{1}= 1, the three students*s*_{1}*∈S** ^{M}* and

*s*

_{2}

*, s*

_{3}

*∈S*

*, and the two schools*

^{m}*{c*

_{1}

*, c*

_{2}

*}*, constitute a type-speciﬁc cycle: Condition (C) is given by

*s*

_{2}

^{r}*c*1

*s*

_{3}

^{r}*c*1

*s*

_{1}

^{o}*c*2

*s*

_{2}, Condition (S) is trivially satisﬁed because

*q*

_{c}*= 1,*

_{l}*l*= 1,2. The matching outcome after the stronger aﬃrmative action ˜

*r*

^{m}

_{c}_{1}is

*μ(s*

_{1}) =

*c*

_{2}and

*μ(s*

_{2}) =

*c*

_{1}. Compared with the corresponding matching before ˜

*r*

*:*

^{m}*μ(s*

_{1}) =

*c*

_{1}and

*μ(s*

_{2}) =

*c*

_{2}, it is obviously that

*s*

_{2}is strictly worse oﬀ after ˜

*r*

_{c}

^{m}_{1}while

*s*

_{3}is indiﬀerent.

*1.6.3* *Proof of Lemma 1.2*

I prove the Lemma by contradiction. Suppose at least one of the minority students is
strictly worse oﬀ in ˜Γ* ^{m}* compare to Γ

*, but no majority students are strictly worse oﬀ after implementing ˜*

^{m}*r*

*. Let ˜*

^{m}*S*

*be the set of minority students who are strictly worse oﬀ after ˜*

^{m}*r*

*,*

^{m}*μ(s)P*

*s*

*μ(s), for all*˜

*s∈S*˜

^{m}*⊂S*

*. And for all*

^{m}*s*

^{}*∈S*

^{m}*\S*˜

*, either ˜*

^{m}*μ(s*

*)R*

^{}*s*

^{}*μ(s*

*) or ˜*

^{}*μ(s*

*)P*

^{}*s*

^{}*μ(s*

*).*

^{}Suppose that a minority student, denote by*s*_{0}, is strictly worse oﬀ in ˜Γ* ^{m}*compare to
Γ

*. Let*

^{m}*μ(s*

_{0}) =

*c*

_{1}. Since

*c*

_{1}

*P*

*s*0

*μ(s*˜

_{0}), the capacity of

*c*

_{1}is full at the step when

*s*

_{0}is rejected by

*c*

_{1}in ˜Γ

*, there is another student, say*

^{m}*s*

_{1}, such that

*s*

_{1}is tentatively accepted by

*c*

_{1}when

*s*

_{0}is rejected. Denote the step when

*s*

_{1}applies to

*c*

_{1}(or equivalently,

*s*

_{0}is rejected by

*c*

_{1}) in ˜Γ

*be step*

^{m}*l*of the SOSM algorithm.

I ﬁrst show that if *s*_{1} is a majority student, then there have a group of minority
students, denote by ˜*S*_{1}* ^{m}*, who are strictly worse oﬀ in ˜Γ

*compare to Γ*

^{m}*, i.e., ˜*

^{m}*S*

^{m}_{1}

*∈S*˜

*, and apply to*

^{m}*c*

_{1}at a step earlier than

*l*in ˜Γ

*. Since*

^{m}*s*

_{1}

*∈S*

*, and no majority students*

^{M}are strictly worse oﬀ after implementing ˜*r** ^{m}*by assumption, I know that either

*c*

_{1}

*P*

*s*

_{1}

*μ(s*

_{1}) or

*c*

_{1}

*R*

*s*

_{1}

*μ(s*

_{1}). Recall that

*c*

_{1}

*P*

*s*

_{0}

*μ(s*˜

_{0}),

*s*

_{0}

*∈S*

*, and all minorities have higher priorities than any majorities in all reserve sub-schools*

^{m}*c*

*, I know that*

^{r}*s*

_{1}

^{o}*c*

_{1}

*s*

_{0},

*s*

_{0}

*∈*

*μ(c*

^{r}_{1}) but

*s*

_{0}

*∈μ(c*˜

^{o}_{1}). Otherwise (s

_{0}

*, c*

_{1}) would form a blocking pair in ˜Γ

*. Therefore, there must have a group of minority students, denote by ˜*

^{m}*S*

_{1}

*, who apply to and are tentatively accepted by*

^{m}*c*

_{1}at a step earlier than

*l*(when

*c*

_{1}rejects

*s*

_{0}) in ˜Γ

*, but do not apply to*

^{m}*c*

_{1}in Γ

*.*

^{m}*s*

^{o}*c*1

*s*

_{0}for all

*s∈S*˜

_{1}

*,*

^{m}^{32}but

*μ(s)P*

*s*

*c*

_{1}for all

*s∈S*˜

_{1}

*. Otherwise, (s, c*

^{m}_{1}) are blocking pairs in Γ

*for all*

^{m}*s∈S*˜

^{m}_{1}. Without losing of generality, denote the least preferred student in ˜

*S*

_{1}

*be*

^{m}*s*

_{2}(if

*|S*˜

_{1}

^{m}*|*= 1, then ˜

*S*

_{1}

^{m}*≡s*

_{2}), such that

*s*

^{o}*c*1

*s*

_{2}

^{o}*c*1

*s*

_{0}for all

*s∈S*˜

_{1}

^{m}*\s*

_{2}.

If*s*_{1}is a minority student, I know that*s*_{1}must be strictly worse oﬀ in ˜Γ* ^{m}*compare
to Γ

*,*

^{m}*μ(s*

_{1})P

*s*

_{1}

*c*

_{1}. Otherwise, (s

_{1}

*, c*

_{1}) forms a blocking pair in Γ

*. Thus,*

^{m}*s*

_{1}

*∈S*˜

*, and*

^{m}*s*

_{1}is rejected by

*μ(s*

_{1}) at a step earlier than

*l*by another student, denote by ˙

*s. Sinces*

_{0}is a random minority student who is strictly worse oﬀ after ˜

*r*

*, I can equivalently treat*

^{m}*s*

_{1}as

*s*

_{0}when

*s*

_{1}

*∈*

*S*

*. Therefore, (i) if ˙*

^{m}*s*

*∈*

*S*

*, repeat the same arguments in this paragraph, I know that ˙*

^{m}*s∈S*˜

*, rewrite ˙*

^{m}*s*as

*s*

_{2}; (ii) if ˙

*s∈S*

*, apply the arguments in the previous paragraph (i.e., equivalently treat ˙*

^{M}*s*as

*s*

_{1}when

*s*

_{1}

*∈S*

*), and I have another set of minority students, denote by ˜*

^{M}*S*

_{2}

*, who are strictly worse oﬀ in ˜Γ*

^{m}*compare to Γ*

^{m}*, write the least preferred minority student in ˜*

^{m}*S*

^{m}_{2}as

*s*

_{2}.

Hence, if there is one minority student,*s*_{0}, who is strictly worse oﬀ in ˜Γ* ^{m}*compare to
Γ

*, there must have another minority student,*

^{m}*s*

_{2}, who is also strictly worse oﬀ in ˜Γ

*and is rejected by*

^{m}*μ(s*

_{2}) at a step earlier than

*l*in ˜Γ

*. Repeat the preceding arguments I can construct a set of*

^{m}*l*minority students, denote by ˜

*S*

*l*, such that

*c*

_{i+1}*P*

*s*

_{i}*c*

*i*,

*i*=

*{*1, . . . , l

*}*,

*s*

*i*

*∈*

*S*˜

*l*

*⊂*

*S*˜

*, where*

^{m}*c*

*=*

_{i+1}*μ(s*

*i*), and

*c*

*i*belongs to a set of

*l*schools in which

*s*

*i*is tentatively accepted by

*c*

*i*at step

*l−i*+ 1 of the SOSM algorithm in ˜Γ

*. In particular,*

^{m}*s*

*l*

*∈S*˜

*l*applies to and is tentatively accepted by

*c*

*l*at step 1. It implies that

*c*

*l*

*P*

*s*

_{l}*c, for all*

*c∈C\c*

*l*, recall

*μ(s*

*l*)=

*c*

*l*, which contradicts to

*μ(s*

*l*)P

*s*

_{l}*c*

*l*.

32i.e., all minority students belong to ˜*S*1* ^{m}*have higher priorities in

*c*1than

*s*0in both the reserve sub-school and the original sub-sub-school (

*c*

^{o}_{1}). Recall that the point-wise priorities among the minorities do not change in both kinds of sub-schools.

*1.6.4* *Proof of Theorem 1.2*

(i)*Strongly type-speciﬁc acyclicity*=*⇒Respect the improvement of reserve-based *
*aﬃrma-tive action.* Suppose if*μ(s)P**s**μ(s) for at least one*˜ *s∈S** ^{m}*, I show that ˜Γ

*must have a quasi type-speciﬁc cycle with two schools and three students.*

^{m}Lemma 1.2 implies that if*μ(s)P*_{s}*μ(s) for at least one*˜ *s∈S** ^{m}*, then

*μ(s*

*)P*

^{}

_{s}*μ(s*˜

*) for at least one*

^{}*s*

^{}*∈*

*S*

*. Denote*

^{M}*s*

_{0}be a minority student who is strictly worse oﬀ after the stronger aﬃrmative action ˜

*r*

*. Let*

^{m}*μ(s*

_{0}) =

*c*

_{0}, and step

*k*be the step of the SOSM algorithm when

*s*

_{0}is rejected by

*c*

_{0}in ˜Γ

*. Without loss of generality, I can construct a set of*

^{m}*k−*1 students,

**s**

**=**

_{l}*{s*

_{1}

*, s*

_{2}

*, . . . , s*

_{k−1}*} ∈S, such thatμ(s*

*l*)P

*s*

_{l}*μ(s*˜

*l*)=

*s*

*l*,

*μ(s*

*l*) =

*c*

*l*,

*l*=

*{*1, . . . , k

*−*1

*}*,

*k*

*≥*2. Let

*k−l*be the step when

*s*

*l*is rejected by

*μ(s*

*l*) in ˜Γ

*.*

^{m}*s*

*l*

applies to*c** _{l−1}*at step

*k−l*+ 1. In particular, I have

*s*

_{1}is rejected by

*μ(s*

_{1}) =

*c*

_{1}at step

*k−*1 and applies to

*c*

_{0}at step

*k. Thus,*

**(i.a.)** if all students in**s**** _{l}**except

*s*

*are minorities. By my construction of*

_{k−1}**s**

**,**

_{l}*s*

*is rejected by*

_{k−1}*μ(s*

*) =*

_{k−1}*c*

*at step 1 of the SOSM algorithm in ˜Γ*

_{k−1}*, and applies to*

^{m}*c*

*in the next step. Obviously,*

_{k−2}*s*

*is*

_{k−1}*directly*aﬀected by ˜

*r*

*(recall Footnote 31), and*

^{m}*s*

_{k−1}*∈S*

*. Thus, there must have another minority student, denote by ˙*

^{M}*s, ˙s∈S*

^{m}*\*

**s**

**, who prefers**

_{l}*c*

*to all the rest schools but is rejected by*

_{k−1}*c*

*in Γ*

_{k−1}*(i.e., before the stronger aﬃrmative action ˜*

^{m}*r*

*). That is,*

^{m}*c*

_{k−1}*P*

*s*

_{˙}

*c, for allc∈*

*C\c*

*,*

_{k−1}*s*

_{k−1}

^{o}*c*

_{k−1}*s*˙ but

˙

*s*^{r}*c*_{k−1}*s** _{k−1}*. Otherwise, (s

_{k−1}*, c*

*) forms a blocking pair in ˜Γ*

_{k−1}*. In addition, I know that*

^{m}*s*

*k*

*−2*is rejected by

*μ(s*

*k*

*−2*) =

*c*

*k*

*−2*at step 2, when

*s*

*k*

*−1*applies to

*c*

*k*

*−2*. As

*s*

*k*

*−1*

*∈S*

*and*

^{M}*s*

*k*

*−2*

*∈S*

*, I have*

^{m}*s*

*k*

*−1*

^{o}*c*

_{k−2}*s*

*k*

*−2*. Thus, ˙

*s*

^{r}*c*

_{k−1}*s*

*k*

*−1*

^{o}*c*

_{k−2}*s*

*k*

*−2*.

**(i.b.)** if*s*_{1}*∈S** ^{m}*, and there is at least one student in

**s**

**besides**

_{l}*s*

*is a majority student. Let*

_{k−1}*s*

*l*be a minority student in

**s**

_{l}*\{s*

_{1}

*}*, who is rejected from

*μ(s*

*l*) =

*c*

*l*in ˜Γ

*when a majority student in*

^{m}**s**

**applies to**

_{l}*c*

*l*. Denote this majority student

*s*

*and*

_{l−1}*μ(s*

*) =*

_{l−1}*c*

*. Thus,*

_{l−1}*s*

_{l−1}

^{o}*c*

_{l}*s*

*l*(a minority student can be rejected by a majority student only from an original sub-school). By my construction of

**s**

**, there is another student**

_{l}*s*

_{l−2}*∈*

**s**

**, who is tentatively accepted by**

_{l}*c*

*at the step when*

_{l−1}*s*

*is rejected by*

_{l−1}*c*

*. Thus,*

_{l−1}*s*

_{l−2}

^{r}*c*

_{l−1}*s*

*(a majority student can be rejected by another student only from a reserve sub-school).*

_{l−1}With*s**l**−2**∈S,s**l**−1**∈S** ^{M}*, and

*s*

*l*

*∈S*

*, I have*

^{m}*s*

*l*

*−2*

^{r}*c*

_{l−1}*s*

*l*

*−1*

^{o}*c*

_{l}*s*

*l*.

**(i.c.)** if*s*_{1}*∈S** ^{M}*. Since

*s*

_{0}

*∈s*

*,*

^{m}*c*

_{0}rejects

*s*

_{0}at step

*k*of the SOSM algorithm when

*s*

_{1}applies to

*c*

_{0}, I have

*s*

_{1}

^{o}*c*

_{0}

*s*

_{0}. Similar to the previous cases, by my construction of

**s**

**,**

_{l}*s*_{1}is rejected by*μ(s*_{1}) =*c*_{1}at step*k−*1 when*s*_{2}*∈***s**** _{l}**applies and is tentatively accepted
by

*c*

_{1}. Thus,

*s*

_{2}

^{r}*c*

_{1}

*s*

_{1}, and I have

*s*

_{2}

^{r}*c*

_{1}

*s*

_{1}

^{o}*c*

_{0}

*s*

_{0}, with

*s*

_{2}

*∈S,s*

_{1}

*∈S*

*and*

^{M}*s*

_{0}

*∈S*

*.*

^{m}Condition (S’) is trivially satisﬁed through the preceding arguments and the stability of SOSM in all three cases.

(ii) *Respect the improvement of reserve-based aﬃrmative action*=*⇒* *Strongly *
*type-speciﬁc acyclicity.* Suppose that ˜Γ* ^{m}*has a quasi type-speciﬁc cycle, I argue that there is
at least one minority student strictly worse oﬀ after implementing the stronger minority
reserve policy ˜

*r*

*. Remark 1.2 implies that if (*

^{m}*,*(q, r

*)) has a type-speciﬁc cycle, then it has a quasi type-speciﬁc cycle. Example 1.1 used in the Proof of Theorem 1.1 (Appendix 1.6.4), which constructs a type-speciﬁc cycle and leaves*

^{m}*s*

_{2}strictly worse oﬀ after ˜

*r*

*,*

^{m}suﬃces for my purpose.

*1.6.5* *Proof of Theorem 1.3*

For a given Γ, let*|S*^{m}*|*=*m*and*s**j*be a random majority student. Choose two schools
*c, c*^{}*∈C*and relabel the minority students with the lowest priority and second lowest
pri-ority in*c*as*i** _{m−1}*and

*i*

*m*, and in

*c*

*as*

^{}*k*

*and*

_{m−1}*k*

*m*respectively. I prove the contrapositive for both of the two parts.

**Part (i)**Suppose that*s** _{j}*ranks higher than two diﬀerent minority students in

*c*

*and*

^{o}*c*

*, I will show that Γ contains a type-speciﬁc cycle.*

^{o}**Case (i.a.)** *i**m*=*k**m*. Because *s*^{r}*c* *i**m*, for all*s∈* *S*^{m}*\i**m*, I have*k**m* ^{r}*c* *i**m*, and
there are other*m−*2 minority students who have higher priority than*k**m*in*c*(recall that
the priority order are unchanged among the minorities within*c** ^{r}* and

*c*

*). As I assume*

^{o}*q*

*c*+

*q*

*c*

^{}*≤m, it implies thatq*

*c*

*−*1

*≤m−*2. Thus, I can ﬁnd a set of

*q*

*c*

*−*1 minority students who have higher priority than

*i*

*m*in

*c*from

*S*

^{m}*\{i*

*m*

*, k*

*m*

*}*, denote by

*S*

*c*. For school

*c*

*, because*

^{}*m−*2

*−*(q

*c*

*−*1)

*≥m−*2

*−*(m

*−q*

*c*

^{}*−*1) =

*q*

*c*

^{}*−*1, I can ﬁnd a set of minority students that are distinct from

*i*

*m*

*, k*

*m*and

*S*

*c*who are ranked higher than

*k*

*m*in

*c*

*, denote by*

^{}*S*

*c*

*. Condition (C) is satisﬁed by*

^{}*k*

*m*

^{r}*c*

*i*

*m*

^{r}*c*

*s*

*j*

^{o}*c*

*k*

*m*,

*S*

*c*and

*S*

*c*

*suﬃces Condition (S).*

^{}**Case (i.b.)** *i** _{m}*=

*k*

*. Without loss of generality, suppose that*

_{m}*s*

_{j}

^{o}*c*

^{}*k*

*. Since there are*

_{m−1}*m−*2 minority students who have higher priority than

*k*

*in*

_{m−1}*c*

*, with similar argument in Case (i.a.), I can ﬁnd a set of*

^{}*q*

_{c}*−*1 minority students that are distinct

from*k**m**, k** _{m−1}*, denote by

*S*

*c*

*, and a set of*

^{}*q*

*c*

*−*1 minority students that are distinct from

*k*

*m*

*, k*

*and*

_{m−1}*S*

*c*

*, denote by*

^{}*S*

*c*. Condition (C) is satisﬁed by

*k*

_{m−1}

^{r}*c*

*i*

*m*

^{r}*c*

*s*

*j*

^{o}*c*

^{}*k*

*,*

_{m−1}*S*

*c*and

*S*

*c*

*suﬃces Condition (S).*

^{}**Part (ii)**I have already shown in Part (i) that when*s** _{j}*ranks higher than two diﬀerent
minority students in two schools, there is a type-speciﬁc cycle. Recall Remark 1.2, if
(

*,*(q, r

*)) has a type-speciﬁc cycle, then it has a quasi type-speciﬁc cycle. Thus, I only need to discuss the situation when there is only one minority student ranked lower than*

^{m}*s*

*j*in one (original sub-)school. Without loss of generality, suppose that

*s*

*j*

^{o}*c*

^{}*k*

*m*.

**Case (ii.a.)**

*i*

*m*=

*k*

*m*, since

*i*

*m*

^{r}*c*

*s*

*j*,

*i*

*m*

*, s*

*j*and

*k*

*m*suﬃce Condition (C’).

**Case (ii.b.)**

*i*

*m*=

*k*

*m*, Condition (C’) is given by

*i*

_{m−1}

^{r}*c*

*s*

*j*

^{o}*c*

^{}*k*

*m*. Condition (S’) is satisﬁed in both

of the two cases with the same arguments in (i.a.).