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 affirmative action ˜r^m, ˜r^m> r^m. Denote the market after ˜r^mby ˜Γ = (C, P,,(q,r˜^m)). Γ^m= (C^m, P,(^o,^r),(q, r^m)) and ˜Γ^m= (C^m, P,(^o ,^r),(q,˜r^m)) are the two respective markets of Γ and ˜Γ after splitting each school into the original sub-school (c^o) and the reserve sub-school (c^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 alls∈ S^m, there has at least one majority students₀∈S^M who prefers ˜μ toμin

˜Γ^m, ˜μ(s₀)P_s0μ(s₀). Let ˜μ(s₀) =c₁andμ(s₀) =c₀. Sinces₀is a majority student, she is rejected by a reserve sub-school. Becauses₀prefersc₁toc₀, she must have been rejected byc₁in Γ^m(which leads to the matchingμ), at an earlier step befores₀applies to c₀. Denote the step whens₀is rejected byc₁in Γ^msteplof the SOSM algorithm. At that step,c₁must have exhausted its capacity,|μ(c₁)|=qc₁, ands^xc₁s₀,x=o, r, for alls tentatively accepted byc₁at stepl. Since ˜μ(s₀) =c₁, there must have another student, denote bys₁, such thats₁is tentatively accepted byc₁at stepl(in Γ^m) but matches with another school in ˜Γ^m. Recall that at stepl,s₀is rejected byc₁, it implies thats₁^rc₁s₀. I first show thats₁must be a majority student who has applied toc₁at a step earlier thanlin Γ^m. Otherwise, ifs₁∈S^m, because ˜μis Pareto dominated byμfor alls∈S^m, while μ(s₁) = ˜μ(s₁), it implies thatμ(s₁)P_s1μ(s˜ ₁). Also, recall that s₁ is tentatively accepted byc₁before her final match in Γ^m, c₁R_s1μ(s₁), I have c₁P_s1μ(s˜ ₁). Since the stronger affirmative action ˜r^m only increases the capacity of some c^r, (s₁, c₁) forms a

blocking pair in ˜Γ^m, which contradicts the stability of ˜μ(with minority reserve). Thus, s₁∈S^M. Obviously,s₁applies toc₁at a step earlier thanl.

Next, since ˜μ(s₁)=c₁, whiles₁^rc1s₀ands₀, s₁∈S^M, it implies that ˜μ(s₁)Ps₁c₁. Oth-erwise, (s₁, c₁) is a blocking pair in ˜Γ^m. Combine withc₁Rs₁μ(s₁), I have ˜μ(s₁)Ps₁μ(s₁).

Denote ˜μ(s₁) =c₂. Recall that in Γ^m, s₁applies toc₁before stepl. Without loss of generality, denote this step byl−1. I can repeat the proceeding arguments fors₀and s₁, and construct a set of l majority students who are all better-off in ˜Γ^m. That is,

˜

μ(si)PsiciRsiμ(si),i={0, . . . , l−1},si∈S^M. cibelongs to a set oflschools in which for eachsishe is tentatively accepted at stepl−i. In particular, let step 1 be the step that initiates the matching in market Γ^mwhens_l−1applies toc_l−1. Becauses_l−1applies toc_l−1 at the first step, it implies thatc_l−1Ps_l−1c, for allc∈C\c_l−1. Recall thatc_l−1= ˜μ(s_l−1),

which contradicts to ˜μ(s_l−1)Ps_l−1c_l−1.

1.6.2 Proof of Theorem 1.1

(i)Type-specific acyclicity =⇒Respect the spirit of reserve-based affirmative action. I prove the contrapositive, such that ifμ(s)Rs˜μ(s) for alls∈ S^m, andμ(s)Psμ(s) for at˜ least ones∈S^m, there must contain a type-specific cycle with at least two schools and three students.

Lemma 1.1 indicates that if ˜μ(s) is Pareto dominated byμ(s) for alls∈ S^m, then there has at least ones∈S^M,μ(s)Psμ(s˜ ). Denote ˜S={s∈S|μ(s)Psμ(s)˜ }be the set of students strictly prefer the matchingμ. Becauseμ(s)Rsμ(s) for all˜ s∈S\S, for those˜ who are not strictly worse off after implementing ˜r^m, they are matched with the same school underμ, 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 students∈S˜and ˜μ(s) =s, such thatsandμ(s) forms a blocking pair after the stronger affirmative action ˜r^m. Further, ˜S contains at least one minority student and one majority student. Because if alls∈S^M∩S,˜

˜

μ(s) =s, then for somes∈S^m∩S,˜ sandμ(s) forms a blocking pair after ˜r^m. Without loss of generality, denotesj ∈ S^M ∩S˜ who is directly affected by ˜r^m,³¹

31A majority studentswho is directly affected by a stronger affirmative action ˜r^min the sense that if μ(s) =cand ˜μ(s)=c,r^mc <r˜^mc, then there is a minority studentssuch thatμ(s)=c,cPsμ(s), ands is tentatively accepted bycat the step whensis rejected. Further, byrc^m<˜r^mc, I know thatμ(s) =c^o,

μ(sj) = c₀. Since c₀Ps_jμ(s˜ j), and ˜μ is stable (Hafalir et al., 2013), this implies that

|μ(c˜ ₀)|=qc₀,|μ(c˜ ₀)∩S^m|= ˜r^m_c0, and for allswho are tentatively accepted byc^x₀,s^xc₀sj, x=o, r. Sincesjis a majority student who is directly affected by the stronger affirmative action ˜r^m, there has a minority student tentatively accepted byc₀, denote bysi, such thatc₀Ps_iμ(si) and sj ^oc₀ si. It implies that si ∈ c^r₀ in ˜Γ^m (because ofsi ^rc₀ sj).

Otherwise, (sj, c₀) forms a blocking pair. However, ˜μ(si)=c₀by assumption (otherwise

˜

μ(si)Ps_iμ(si)). Sincesicannot be rejected by an majority student fromc^r₀, there must have another minority student, denote bysk, such thatsk∈S^m∩S˜, sk∈μ(c˜ ₀)\μ(c₀) ands_k^rc0s_i. Thus, I have

sk^rc₀si^rc₀sj, si, sk∈S^m, sj∈S^M (1.1)

Denoteμ(sk) =ck. BecauseckPs_kc₀and ˜μis stable, it implies that|μ(c˜ k)|=qc_k, and there exists a student in ˜S, denote bysk−1, such that

s_k−1∈μ(c˜ k)\μ(ck), s_k−1^oc_ksk (1.2)

Otherwise, (sk, ck) forms a blocking pair in ˜Γ^m. Apply similar arguments ofsk−1, sk

andc₀, ck for each student in ˜S repeatedly. Because the set of students in ˜S are fi-nite, let{s₀, s₁, . . . , sk−2, sk−1} ∈ S˜\{sk}, I can construct a finite sequence of schools c₁, c₂, . . . , ck−1, cksuch that for eachl={0,1,2, . . . , k−1}

sl∈μ(c˜ _l+1)\μ(c_l+1), μ(sl) =cl, clPs_lc_l+1 (1.3)

|μ(c˜ l)|=qc_l, s^xc_lsl, x=o, r, for eachs∈μ(c˜ l) (1.4)

In particular, I have

s^ocs, andsis tentatively accepted byc^r(beforesapplies toc) after the stronger affirmative action.

The set of majority students that are directly affected by ˜r^mis nonempty; otherwise,μ(Γ^m) =μ(˜Γ^m).

⎧⎪

⎨

⎪⎩

sl^oc_l+1sl+1 ifsl+1∈S^m

sl^rc_l+1s_l+1 ifs_l+1∈S^M, l={0,1,2, . . . , k−1}

(1.5)

It is not difficult to see thats₀≡sj by preceding arguments. Combining (1.1) and (1.5) gives us the cycle condition. The scarcity condition is satisfied by (1.2), (1.3) and (1.4), and the stability of SOSM.

(ii)Respect the spirit of reserve-based affirmative action=⇒Type-specific acyclicity.

Suppose that ˜Γ^m has a type-specific cycle, I use a counter-example to show that the stronger minority reserve policy ˜r^mwill cause all minorities worse off.

Recall Example 1.1 that after implementing ˜r^m_c1= 1, the three studentss₁∈S^M and s₂, s₃∈S^m, and the two schools{c₁, c₂}, constitute a type-specific cycle: Condition (C) is given bys₂^rc1 s₃^rc1 s₁^oc2 s₂, Condition (S) is trivially satisfied because q_cl = 1, l= 1,2. The matching outcome after the stronger affirmative action ˜r^m_c1 isμ(s₁) =c₂ andμ(s₂) =c₁. Compared with the corresponding matching before ˜r^m: μ(s₁) =c₁and μ(s₂) =c₂, it is obviously thats₂is strictly worse off after ˜r_c^m₁whiles₃is indifferent.

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 off in ˜Γ^m compare to Γ^m, but no majority students are strictly worse off after implementing ˜r^m. Let ˜S^mbe the set of minority students who are strictly worse off after ˜r^m,μ(s)Psμ(s), for all˜ s∈S˜^m⊂S^m. And for alls∈S^m\S˜^m, either ˜μ(s)Rsμ(s) or ˜μ(s)Psμ(s).

Suppose that a minority student, denote bys₀, is strictly worse off in ˜Γ^mcompare to Γ^m. Letμ(s₀) =c₁. Sincec₁Ps0μ(s˜ ₀), the capacity ofc₁is full at the step whens₀is rejected byc₁in ˜Γ^m, there is another student, says₁, such thats₁is tentatively accepted byc₁when s₀is rejected. Denote the step when s₁applies toc₁(or equivalently, s₀is rejected byc₁) in ˜Γ^mbe steplof the SOSM algorithm.

I first show that if s₁ is a majority student, then there have a group of minority students, denote by ˜S₁^m, who are strictly worse off in ˜Γ^mcompare to Γ^m, i.e., ˜S^m₁ ∈S˜^m, and apply toc₁at a step earlier thanlin ˜Γ^m. Sinces₁∈S^M, and no majority students

are strictly worse off after implementing ˜r^mby assumption, I know that eitherc₁Ps₁μ(s₁) orc₁Rs₁μ(s₁). Recall thatc₁Ps₀μ(s˜ ₀),s₀∈S^m, and all minorities have higher priorities than any majorities in all reserve sub-schoolsc^r, I know that s₁ ^oc₁ s₀, s₀ ∈ μ(c^r₁) buts₀ ∈μ(c˜ ^o₁). Otherwise (s₀, c₁) would form a blocking pair in ˜Γ^m. Therefore, there must have a group of minority students, denote by ˜S₁^m, who apply to and are tentatively accepted byc₁at a step earlier thanl(whenc₁rejectss₀) in ˜Γ^m, but do not apply toc₁in Γ^m. s^oc1s₀for alls∈S˜₁^m,³²butμ(s)Psc₁for alls∈S˜₁^m. Otherwise, (s, c₁) are blocking pairs in Γ^mfor alls∈S˜^m₁. Without losing of generality, denote the least preferred student in ˜S₁^mbes₂(if|S˜₁^m|= 1, then ˜S₁^m≡s₂), such thats^oc1s₂^oc1s₀for alls∈S˜₁^m\s₂.

Ifs₁is a minority student, I know thats₁must be strictly worse off in ˜Γ^mcompare to Γ^m,μ(s₁)Ps₁c₁. Otherwise, (s₁, c₁) forms a blocking pair in Γ^m. Thus,s₁∈S˜^m, and s₁is rejected byμ(s₁) at a step earlier thanlby another student, denote by ˙s. Sinces₀ is a random minority student who is strictly worse off after ˜r^m, I can equivalently treat s₁as s₀when s₁ ∈ S^m. Therefore, (i) if ˙s ∈ S^m, repeat the same arguments in this paragraph, I know that ˙s∈S˜^m, rewrite ˙sass₂; (ii) if ˙s∈S^M, apply the arguments in the previous paragraph (i.e., equivalently treat ˙sass₁when s₁∈S^M), and I have another set of minority students, denote by ˜S₂^m, who are strictly worse off in ˜Γ^mcompare to Γ^m, write the least preferred minority student in ˜S^m₂ ass₂.

Hence, if there is one minority student,s₀, who is strictly worse off in ˜Γ^mcompare to Γ^m, there must have another minority student,s₂, who is also strictly worse off in ˜Γ^mand is rejected byμ(s₂) at a step earlier thanlin ˜Γ^m. Repeat the preceding arguments I can construct a set oflminority students, denote by ˜Sl, such thatc_i+1Ps_ici, i={1, . . . , l}, si ∈ S˜l ⊂ S˜^m, wherec_i+1= μ(si), andci belongs to a set ofl schools in whichsi is tentatively accepted byciat stepl−i+ 1 of the SOSM algorithm in ˜Γ^m. In particular, sl∈S˜lapplies to and is tentatively accepted byclat step 1. It implies thatclPs_lc, for all c∈C\cl, recallμ(sl)=cl, which contradicts toμ(sl)Ps_lcl.

32i.e., all minority students belong to ˜S1^mhave higher priorities inc1thans0in both the reserve sub-school and the original sub-sub-school (c^o₁). 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-specific acyclicity=⇒Respect the improvement of reserve-based affirma-tive action. Suppose ifμ(s)Psμ(s) for at least one˜ s∈S^m, I show that ˜Γ^mmust have a quasi type-specific cycle with two schools and three students.

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 ones ∈ S^M. Denotes₀ be a minority student who is strictly worse off after the stronger affirmative action ˜r^m. Letμ(s₀) =c₀, and stepk be the step of the SOSM algorithm whens₀is rejected byc₀in ˜Γ^m. Without loss of generality, I can construct a set ofk−1 students,s_l={s₁, s₂, . . . , s_k−1} ∈S, such thatμ(sl)Ps_lμ(s˜ l)=sl,μ(sl) =cl, l={1, . . . , k−1},k ≥2. Let k−lbe the step whenslis rejected byμ(sl) in ˜Γ^m. sl

applies toc_l−1at stepk−l+ 1. In particular, I haves₁is rejected byμ(s₁) =c₁at step k−1 and applies toc₀at stepk. Thus,

(i.a.) if all students ins_lexcepts_k−1are minorities. By my construction ofs_l,s_k−1 is rejected byμ(s_k−1) = c_k−1at step 1 of the SOSM algorithm in ˜Γ^m, and applies to c_k−2in the next step. Obviously,s_k−1isdirectlyaffected by ˜r^m(recall Footnote 31), and s_k−1∈S^M. Thus, there must have another minority student, denote by ˙s, ˙s∈S^m\s_l, who prefers c_k−1 to all the rest schools but is rejected byc_k−1 in Γ^m (i.e., before the stronger affirmative action ˜r^m). That is, c_k−1Ps_˙c, for allc∈ C\c_k−1, s_k−1^oc_k−1 s˙ but

˙

s^rc_k−1 s_k−1. Otherwise, (s_k−1, c_k−1) forms a blocking pair in ˜Γ^m. In addition, I know thatsk−2is rejected byμ(sk−2) =ck−2at step 2, whensk−1applies tock−2. Assk−1∈S^M andsk−2∈S^m, I havesk−1^oc_k−2sk−2. Thus, ˙s^rc_k−1sk−1^oc_k−2sk−2.

(i.b.) ifs₁∈S^m, and there is at least one student ins_lbesidess_k−1is a majority student. Letslbe a minority student ins_l\{s₁}, who is rejected fromμ(sl) =clin ˜Γ^mwhen a majority student ins_lapplies tocl. Denote this majority students_l−1andμ(s_l−1) =c_l−1. Thus,s_l−1^oc_lsl(a minority student can be rejected by a majority student only from an original sub-school). By my construction ofs_l, there is another students_l−2∈s_l, who is tentatively accepted byc_l−1at the step whens_l−1is rejected byc_l−1. Thus,s_l−2^rc_l−1s_l−1 (a majority student can be rejected by another student only from a reserve sub-school).

Withsl−2∈S,sl−1∈S^M, andsl∈S^m, I havesl−2^rc_l−1sl−1^oc_lsl.

(i.c.) ifs₁∈S^M. Sinces₀∈s^m,c₀rejectss₀at stepkof the SOSM algorithm when s₁applies toc₀, I haves₁^oc₀s₀. Similar to the previous cases, by my construction ofs_l,

s₁is rejected byμ(s₁) =c₁at stepk−1 whens₂∈s_lapplies and is tentatively accepted byc₁. Thus,s₂^rc₁s₁, and I haves₂^rc₁s₁^oc₀s₀, withs₂∈S,s₁∈S^Mands₀∈S^m.

Condition (S’) is trivially satisfied through the preceding arguments and the stability of SOSM in all three cases.

(ii) Respect the improvement of reserve-based affirmative action=⇒ Strongly type-specific acyclicity. Suppose that ˜Γ^mhas a quasi type-specific cycle, I argue that there is at least one minority student strictly worse off after implementing the stronger minority reserve policy ˜r^m. Remark 1.2 implies that if (,(q, r^m)) has a type-specific cycle, then it has a quasi type-specific cycle. Example 1.1 used in the Proof of Theorem 1.1 (Appendix 1.6.4), which constructs a type-specific cycle and leavess₂ strictly worse off after ˜r^m,

suffices for my purpose.

1.6.5 Proof of Theorem 1.3

For a given Γ, let|S^m|=mandsjbe a random majority student. Choose two schools c, c∈Cand relabel the minority students with the lowest priority and second lowest pri-ority incasi_m−1andim, and incask_m−1andkmrespectively. I prove the contrapositive for both of the two parts.

Part (i)Suppose thats_jranks higher than two different minority students inc^oand c^o, I will show that Γ contains a type-specific cycle.

Case (i.a.) im=km. Because s^rc im, for alls∈ S^m\im, I havekm ^rc im, and there are otherm−2 minority students who have higher priority thankminc(recall that the priority order are unchanged among the minorities withinc^r andc^o). As I assume qc+qc ≤m, it implies thatqc−1≤m−2. Thus, I can find a set ofqc−1 minority students who have higher priority thanim in c fromS^m\{im, km}, denote bySc. For schoolc, becausem−2−(qc−1)≥m−2−(m−qc−1) =qc−1, I can find a set of minority students that are distinct fromim, kmandScwho are ranked higher thankmin c, denote bySc. Condition (C) is satisfied bykm^rcim^rcsj^ockm,ScandScsuffices Condition (S).

Case (i.b.) i_m=k_m. Without loss of generality, suppose thats_j ^oc k_m−1. Since there arem−2 minority students who have higher priority thank_m−1inc, with similar argument in Case (i.a.), I can find a set ofq_c −1 minority students that are distinct

fromkm, k_m−1, denote bySc, and a set ofqc−1 minority students that are distinct from km, k_m−1andSc, denote bySc. Condition (C) is satisfied byk_m−1^rcim^rcsj^ock_m−1, ScandScsuffices Condition (S).

Part (ii)I have already shown in Part (i) that whens_jranks higher than two different minority students in two schools, there is a type-specific cycle. Recall Remark 1.2, if (,(q, r^m)) has a type-specific cycle, then it has a quasi type-specific cycle. Thus, I only need to discuss the situation when there is only one minority student ranked lower thansjin one (original sub-)school. Without loss of generality, suppose thatsj^ockm. Case (ii.a.) im=km, sinceim^rcsj,im, sjandkmsuffice Condition (C’).Case (ii.b.) im=km, Condition (C’) is given byi_m−1^rcsj^ockm. Condition (S’) is satisfied in both

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

In document Essays on Market Design (Sider 40-47)