### A P

ROOF OF### T

HEOREM### 1

Outputs of the TGS mechanism satisfy feasibility, individually rationality, and the separation principle by the flow of the TDA algorithm. To prove other properties, I first introduce the follow-ing lemma which follows from Erdil and Ergin (2008; Lemma 1):

Lemma 1. Suppose*B*=∅and letµbe an arbitrary stable matching. For any ˜µwhich dominates it
and for any *s*∈*S*,|µ(s)|<*q** _{s}*if and only if|µ(s)|˜ <

*q*

*, and in this case,µ(s)= µ(s).˜*

_{s}*Proof of Theorem 1*

*Quasi Stability: Let* µ ≡ ϕ* ^{T GS}*(≻

*,*

_{I}*B). If there exist*

*i*∈

*I*and

*s*∈

*S*such that

*s*≻

*µ(i) and*

_{i}|µ(s)|<*q**s*, then*i*∈*Bu(B) (otherwisei*was rejected by *s*at Round 1 of the TDA algorithm), and*s*
accepts her victim (otherwise*i*was rejected by*s*at Round 2). Hence, inµ, no student wishes for a
vacant seat at some school.

Suppose there exist *i,* *j* ∈ *I* such that µ(*j)* ≻* _{i}* µ(i) and

*i*≻

_{µ(}

_{j)}*j. By its construction of*µ,

*i*∈

*Bu(B) (otherwisei*was rejected byµ(

*j) at Round 1). If*

*j*∈

*Bu(B),*µ(

*j) acceptsi’s victim at*Round 1 (otherwise

*i*was rejected by µ(

*j) at Round 2). Hence, if*

*i*has justified envy toward

*j,*

*i*∈

*Bu(B) and*

*j*<

*Bu(B).*

*Student-optimality: Let*µ ≡ ϕ* ^{T GS}*(≻

*I*,

*B). Suppose that there exists a quasi stable matching ˜*µ that dominatesµ. Let ˜

*I*={i∈

*I*|µ(i)˜ ≻

*µ(i)}. There are two cases to consider.*

_{i}Case 1: ˜*I* \ *Bu(B)* , ∅. Let µ_{1} denote a matching such that µ_{1}(i) = µ(i) for all *i* < *Bu(B),*
and µ_{1}(i) = *i* for all *i* ∈ *Bu(B). We define ˜*µ_{1} in the same way. Consider a preference profile
of bullies such that *i* ≻_{i}*s* for all *s* ∈ *S* and for all *i* ∈ *Bu(B). By assumption, ˜*µ_{1} dominates
µ_{1}. Sinceµ_{1}is a student-optimal stable matching given the modified preferences, there is at least
one student *i* < *Bu(B) at ˜*µ_{1} who (i) wishes for a vacant seat at some school *s* ∈ *S*, or (ii) has
justified envy toward another student *j* < *Bu(B) (i.e., ˜*µ_{1}(*j)* ≻* _{i}* µ˜

_{1}(i) and

*i*≻

_{µ}

_{˜}

_{1}

_{(j)}

*j). Suppose the*first possibility holds. By Lemma 1, if

*s*∈

*S*has a vacant seat at ˜µ

_{1}, it also has a vacant seat atµ

_{1}. Since

*s*≻

*µ˜*

_{i}_{1}(i)

*µ*

_{i}_{1}(i), she wishes for the vacant seat atµ

_{1}, which contradicts the stability ofµ

_{1}. Next, suppose the second possibility holds. Then|µ˜

_{1}( ˜µ

_{1}(

*j))|*=

*q*

_{µ}

_{˜}

_{1}

_{(}

*is true for the same reason we discussed above. Since|µ˜*

_{j)}_{1}( ˜µ

_{1}(

*j))|*=

*q*µ˜1(

*j)*implies|µ( ˜˜ µ(

*j))|*=

*q*µ(˜

*j)*and ˜µ( ˜µ(

*j))*∩

*Bu(B)*= ∅. Hence,

*i*<

*Bu(B) and she has justified envy toward*

*j*at ˜µ, which contradicts the quasi stability of ˜µ.

Case 2: ˜*I* ⊆ *Bu(B). Let* µ_{2} denote a matching such that µ_{2}(i) = µ(i) for all *i* ∈ *Bu(B) and*
µ_{2}(i) = *i* for all*i* < *Bu(B). We define ˜*µ_{2} in the same way. Consider the following modification
of the preference profile of students and school capacities: for all *i* ∈ *Bu(B), if* *s* ∈ *S* accepts
her victim atµ_{1}(= µ˜_{1}), she lowers the preference ranking of *s*below her outside option; for each
*i*< *Bu(B),i*≻_{i}*s*for all *s*∈*S*; each school*s*∈*S* reduces its capacity by|µ_{1}(s)|(=|˜µ_{1}(s)|). Thenµ_{2}
is a student-optimal stable matching and ˜µ_{2}dominatesµ_{2}. Suppose*i* ∈*Bu(B) wishes for a vacant*
seat of*s* ∈*S* at ˜µ_{2}. By Lemma 1,*s*also leaves the seat vacant and does not accept any victims of
*i*at ˜µ. This contradicts the quasi stability of ˜µ. Next, suppose*i* ∈*Bu(B) has justified envy toward*
*j*∈*Bu(B) at ˜*µ_{2}. Since ˜µ_{2}(*j) does not accept any victims ofi*at ˜µ, this assumption also contradicts
the quasi stability of ˜µ.

*Strategy-proofness: Since the GS mechanism is strategy-proof, no one has any incentives to*
misrepresent her preferences at Round 1 and 2. Thus, the TGS mechanism is also strategy-proof.

*Bullying-resistance: Suppose that* *B*and *B*^{′} = *B*∪ {(i, *j)}* are both sets of bullying incidents.

There are two cases to consider.

Case 1: *i* ∈ *Bu(B). Let* ≻^{′}* _{i}* denote

*i’s preference ordering that is used for the DA algorithm*at Round 2 when the set of bullying incidents is

*B. When the set of bullying incidents is*

*B*

^{′},

*i*may further lower the preference ranking ofϕ

^{T GS}*(≻*

_{j}*,*

_{I}*B*

^{′}) below her outside option. Since the GS mechanism is strategy-proof, ϕ

^{T GS}*(≻*

_{i}*,*

_{I}*B)*

^{′}

*ϕ*

_{i}

^{T GS}*(≻*

_{i}*,*

_{I}*B*

^{′}). By the construction of preferences, ϕ

^{T GS}*(≻*

_{i}*,*

_{I}*B*

^{′})

^{′}

_{i}*i. Note that for all*

*s,s*

^{′}∈

*S*∪ {

*i*}such that

*s,s*

^{′}

^{′}

_{i}*i,*

*s*

^{′}

_{i}*s*

^{′}implies

*s*

_{i}*s*

^{′}. Hence we haveϕ

^{T GS}*(≻*

_{i}*I*,

*B)*

*ϕ*

_{i}

^{T GS}*(≻*

_{i}*I*,

*B*

^{′}).

Case 2: *i* < *Bu(B). Consider the following variations of the bullies’ preferences: for each*
*k* ∈ *Bu(B),* *k* ≻˜_{k}*s* for all *s* ∈ *S*, and ˜≻* _{i}* places only her assignment ϕ

^{T GS}*( ˜≻*

_{i}*,≻*

_{Bu(B)}_{−Bu(B)},

*B*

^{′}) above her outside option (if ϕ

^{T GS}*( ˜≻*

_{i}*,≻*

_{Bu(B)}_{−Bu(B)},

*B*

^{′}) =

*i, then all the schools in*

*S*move be-low her outside option). Then ϕ

^{T GS}*( ˜≻*

_{i}*,≻*

_{Bu(B)}_{−Bu(B)},

*B*

^{′}) = ϕ

^{T GS}*( ˜≻*

_{i}*′),≻*

_{Bu(B}_{−Bu(B}′),

*B). Since the GS*mechanism is strategy-proof, ϕ

^{T GS}*( ˜≻*

_{i}*,≻*

_{Bu(B)}_{−Bu(B)},

*B)*

*ϕ*

_{i}

^{T GS}*( ˜≻*

_{i}*′),≻*

_{Bu(B}_{−Bu(B}′),

*B), which implies*ϕ

^{T GS}*( ˜≻*

_{i}*,≻*

_{Bu(B)}_{−Bu(B)},

*B)*

*ϕ*

_{i}

^{T GS}*( ˜≻*

_{i}*,≻*

_{Bu(B)}_{−Bu(B)},

*B*

^{′}). By the assumption

*i*<

*Bu(B),*ϕ

^{T GS}*( ˜≻*

_{i}*,≻*

_{Bu(B)}_{−Bu(B)},

*B)*=ϕ

^{T GS}*(≻*

_{i}*,*

_{I}*B). Since*ϕ

^{T GS}*( ˜≻*

_{i}*,≻*

_{Bu(B)}_{−Bu(B)},

*B*

^{′})

*ϕ*

_{i}

^{T GS}*(≻*

_{i}*,*

_{I}*B*

^{′}), we conclude thatϕ

^{T GS}*(≻*

_{i}*,*

_{I}*B)*

_{i}ϕ^{T GS}* _{i}* (≻

*,*

_{I}*B*

^{′}). This completes the proof.

*Q.E.D.*

### B P

ROOF OF### T

HEOREM### 2

*Proof.* Outputs of the TTC mechanism are always feasible, individually rational, and satisfy the
separation principle by the construction of the TTC algorithm. Letµ≡ ϕ* ^{T T C}*(≻

*,*

_{I}*B).*

*Constrained Pareto Efficiency: Suppose that ˜*µis a feasible and individually rational matching
that dominatesµ. Let*i* ∈*I*be a student who prefers ˜µ(i) toµ(i), and suppose that there is no other
student who prefers the assignment under ˜µto the one underµwhile being removed earlier in the
TTC algorithm compared to*i. Thus, for any student* *j*who is removed earlier than*i*, ˜µ(*j)* =µ(*j).*

By the construction of the TTC algorithm, ˜µ(i)≻* _{i}* µ(i) implies that ˜µdoes not satisfy the separation
principle. Hence,µis constrained Pareto efficient.

*Group Strategy-proofness*: For an arbitrary matching ˜µ, let≻^{µ}_{i}^{˜} denote*i’s preferences such that*
*s* ≻^{µ}_{i}^{˜} *i* if and only if *s* = µ(i) and˜ *s* ∈ *S*. Then, µis equivalent to ϕ* ^{T T C}*(≻

^{µ}

*,≻*

_{i}_{−i},

*B) for anyi*∈

*I.*

(∵ Let*C*^{1},*C*^{2}, ...,*C** ^{n}*, ...be a sequence of one-by-one cycle removals given the preference profile

≻* _{I}* where we stretch the interpretation of a “cycle” to include the singletons comprising only one
student. Suppose

*i*is in

*C*

*. Hence whatever preferences*

^{n}*i*reports, we can remove

*C*

^{1},

*C*

^{2}, ...,

*C*

*in the first*

^{n−1}*n*−1 steps. Now suppose

*i*reports≻

^{µ}

*. After removing*

_{i}*C*

^{1}, ...,

*C*

*, we can immediately remove*

^{n−1}*C*

*, followed by*

^{n}*C*

*,*

^{n+1}*C*

*, ...which results inµ.)*

^{n+2}Suppose ϕ^{T T C}* _{i}* ( ˜≻

_{I}_{˜},≻

_{−}

_{I}_{˜},

*B)*

*µ(i) holds for all*

_{i}*i*∈

*I. Let ˜*˜ µ denote ϕ

*( ˜≻*

^{T T C}

_{I}_{˜},≻

_{−˜}

*,*

_{I}*B). By the*previous discussion, ϕ

*(≻*

^{T T C}^{µ}

^{˜}

_{˜}

*I*,≻_{−}_{I}_{˜},*B)* = µ. Let˜ *C*^{1},*C*^{2}, ... be a sequence of one-by-one cycle
re-movals in the TTC algorithm given an input (≻* _{I}*,

*B). Suppose that it is possible to remove the first*

*t*−1 cycles

*C*

^{1}, ...,

*C*

*in the same order under (≻*

^{t−1}^{µ}

^{˜}

_{˜}

*I*,≻_{−}*I*˜,*B) and there is a student inC** ^{t}* who is a
member of ˜

*I*(indeed, if

*C*

*is the first cycle where a nonempty subset of ˜*

^{t}*I*is involved, it is possible to remove

*C*

^{1},

*C*

^{2}, ...,

*C*

*in the first*

^{t−1}*t*− 1 steps no matter what profile of preferences ˜

*I*reports).

There are two cases to consider.

Case 1: *C** ^{t}* is a singleton comprising one student

*i. By the construction of the TTC algorithm,*after removing

*C*

^{1}, ...,

*C*

*there is no remaining school that is preferable for*

^{t−1}*i*in terms of≻

*to her outside option and has not accepted any student who victimizes her or is victimized by her. Hence*

_{i}*i*≻

^{µ}

_{i}^{˜}

*s*holds for all

*s*∈

*S*, meaning that

*C*

*can be removed immediately after*

^{t}*C*

^{1}, ...,

*C*

*even under the preference profile (≻*

^{t−1}^{µ}

^{˜}

_{˜}

*I*,≻_{−˜}* _{I}*).

Case 2: *C** ^{t}* comprises a school. Each student in the cycle points to her best remaining school
among those who have not accepted any student who victimizes her or is victimized by her. Hence
for any student

*i*who is in it and also a member of ˜

*I,*µ(i) ≻

^{µ}

_{i}^{˜}

*i*and

*i*≻

^{µ}

_{i}^{˜}

*s*for all

*s*∈

*S*\ {µ(i)}.

As in the previous case, therefore,*C** ^{t}* can be removed immediately after

*C*

^{1}, ...,

*C*

^{t}^{−1}even under the preference profile (≻

^{µ}

^{˜}

_{˜}

*I*,≻_{−}*I*˜).

To summarize, it is possible to remove*C*^{1},*C*^{2}, ...in the same order under ((≻^{µ}^{˜}_{˜}

*I*,≻_{−˜}* _{I}*),

*B), which*results inµ. Hence ˜µ= µ, which implies that the TTC mechanism is group strategy-proof.

*Bullying-resistance: Suppose thatB*and*B*^{′}= *B*∪ {(i, *j)}*are both sets of bullying incidents. Let
µ^{′}≡ ϕ* ^{T T C}*(≻

*,*

_{I}*B*

^{′}). Consider the TTC algorithm for (≻

*,*

_{I}*B). Ifi*and

*j*are removed at the same step, they are also removed simultaneously under (≻

*I*,

*B*

^{′}) and assigned to the same schools acrossµand µ

^{′}. If

*i*is removed earlier than

*j,*µ(i)= µ

^{′}(i). Finally, if

*j*is removed earlier than

*i, the allocation*to those removed earlier than

*i*is the same acrossµandµ

^{′}. Hence,µ(i) is different fromµ

^{′}(i) only ifµ(i)=µ(

*j), and in this case*µ(i)≻

*µ*

_{i}^{′}(i). This completes the proof.

*Q.E.D.*

### C P

ROOF OF### T

HEOREM### 3

*Proof.* Consider a problem where *I* = {i_{1}, ...,*i*_{6}}, *S* = {s_{1},*s*_{2},*s*_{3},*s*_{4}},*q*_{s}_{1} = *q*_{s}_{2} = *q*_{s}_{3} = 1, *q*_{s}_{4} = 2,
*B*= ∅, and preferences are given by

≻_{i}_{1},≻_{i}_{2} : *s*_{4},*s*_{1},∅

≻_{i}_{3},≻_{i}_{4} : *s*4,*s*2,∅

≻_{i}_{5},≻_{i}_{6} : *s*_{4},*s*_{3},∅.

Suppose in the way of contradiction that there exists a mechanism that produces a feasible, indi-vidually rational, and constrained Pareto efficient matching for any input and is group bullying-resistant. Consider the following possible outcome of a mechanism:

µ=

*s*1 *s*2 *s*3 *s*4 ∅ ∅

∅ *i*3 *i*5 *i*1 *i*2 *i*4 *i*6

. (1)

If *B* is replaced by *B*^{′} = {(i_{2},*i*1),(i_{4},*i*1),(i_{6},*i*1)}, *i*1 or *i*2 must leave *s*4. By the group
bullying-resistance property, neither*i*4 nor *i*6 enters *s*4. Then by constrained Pareto efficiency, either *i*3 or
*i*_{5} enters *s*_{4}, which induces a transfer of *i*_{4} or *i*_{6} to *s*_{2} or *s*_{3}. This contradicts the group
bullying-resistance property.

Consider the following possible outcome of a mechanism

µ^{′} =

*s*1 *s*2 *s*3 *s*4 ∅
*i*_{2} *i*_{4} *i*_{5} *i*_{1}*i*_{3} *i*_{6}

.

If*B*is replaced by*B*^{′′} ={(i2,*i*1),(i3,*i*1),(i4,*i*1),(i6,*i*1)},*i*1or*i*3must leave*s*4. By the group
bullying-resistance property,*s*_{4}does not accept*i*_{2},*i*_{4},nor*i*_{6}. By constrained Pareto efficiency,*i*_{5}and*i*_{6}enter
*s*_{4} and *s*_{3} respectively, which contradicts the group bullying-resistance property. This completes

the proof. *Q.E.D.*

### D P

ROOF OF### T

HEOREM### 4

*Proof.* Suppose that there exists a mechanism that produces a quasi stable matching and is group
bullying-resistant. Consider the problem in the previous proof and the following school priorities:

≻_{s}_{1},≻_{s}_{2},≻_{s}_{3},≻_{s}_{4}:*i*1,*i*2,*i*3,*i*4,*i*5,*i*6.

The matchingµ(see (1)) is the unique (quasi) stable matching when*B*=∅. Following the argument
in the proof of Theorem 3, we observe that if*B*is replaced by*B*^{′} ={(i_{2},*i*_{1}),(i_{4},*i*_{1}),(i_{6},*i*_{1})}, there is
at least one student in{i_{2},*i*_{4},*i*_{6}}who gets better off. This is a contradiction. *Q.E.D.*

### E P

ROOF OF### T

HEOREM### 5

Before proceeding to the proof of the theorem, I introduce a lemma without proof, which will be used subsequently.

Lemma 2. Suppose*B* = ∅. Then any stable matching is (constrained) Pareto efficient in terms of
student and school preferences.

This follows from the fact that when *B* = ∅and school preferences are strict, the set of stable
matchings is equivalent to the weak core. For specific details, the reader is referred to Roth and
Sotomayor (1990; Proposition 5.36).

*Proof of Theorem 5*

*Quasi Stability: Let*µdenote an outcome of the TGS mechanism and suppose that (i,*s) is a*
blocking pair at µ. Let ˜*I* denote an arbitrary subset of µ(s) satisfying the three conditions in the
definition of a blocking pair. It is easy to show that if *i* < *Bu(B) and either ˜I* ∩ *Bu(B)* , ∅ or
*I*˜ = ∅, the outcome of Round 1 is not stable among non-bullies. This is a contradiction. Next if
*i* < *Bu(B), ˜I* , ∅, and *I*_{2}∩*Bu(B)* = ∅, then by the responsiveness condition, for any student *j*in
*I*˜\*Bu(B),*{i} ≻* _{s}* {

*j}. This again contradicts stability. Finally ifi*∈

*Bu(B) and ˜I*⊆

*Bu(B), then by*the construction of Round 2, there must be

*j*∈ µ(s)\

*I*˜such that (i,

*j)*∈

*B. Then (i,s) is by no*means a blocking pair. Hence

*i*∈

*Bu(B) and ˜I*\

*Bu(B)*, ∅, meaningµis quasi stable.

Proofs for other properties going along with the TGS mechanism except constrained Pareto efficiency are the same as those in the proof of Theorem 1. Note that Lemma 1 holds as it is under

the responsive school preferences (domination in the statement of the lemma is defined in terms of student preferences).

*Constrained Pareto Efficiency: Let* µdenote an outcome of the TGS mechanism. Suppose in
the way of contradiction thatµis dominated by another matching ˜µthat is feasible and satisfies the
separation principle. There are two cases to consider.

Case 1: ∀*i* ∈ *I* \*Bu(B), ˜*µ(i) = µ(i). This means that in the hypothetical Round 2 of the TDA
algorithm, after assigning µ(i) = µ(i) to all˜ *i* < *Bu(B), under the modified preferences of bullies*
and reduced numbers of the seats of schools, ˜µgives a description of a matching that dominates a
stable matching in the residual problem. This contradicts Lemma 2.

Case 2: ∃i ∈ *I* \*Bu(B), ˜*µ(i) , µ(i). For any*i* < *Bu(B), ˜*µ(i) * _{i}* µ(i), and at least one of them
holds with a strict relation. By Lemma 1, for any

*s*∈

*S*,|µ(s)˜ \

*Bu(B)|*<

*q*

*⇔ |µ(s)\*

_{s}*Bu(B)|*<

*q*

*and in this case, ˜µ(s)\*

_{s}*Bu(B)*= µ(s)\

*Bu(B). Hence by Lemma 2, there is at least one school*

*s*such that|µ(s)˜ \

*Bu(B)|*=|µ(s)\

*Bu(B)|*=

*q*

*andµ(s)≻*

_{s}*µ(s). This contradicts the assumption that˜*

_{s}µ˜ dominatesµ. *Q.E.D.*

### F P

ROOF OF### P

ROPOSITION### 2

*Proof. Given an output* µ of the TGS mechanism, suppose that (I1,*s) is a blocking group and*
*I*2 ⊆ µ(s) is a set of students satisfying the three conditions in the definition of a blocking group.

There are two cases to consider.

Case 1: µ(s) ∩*Bu(B)* = ∅. If |µ(s)| < *q** _{s}*, there is (i,

*j)*∈

*B*such that

*i*∈

*I*

_{1}and

*j*∈

*I*

_{2}, confirming the statement of the proposition. Suppose instead that |µ(s)| =

*q*

*and*

_{s}*I*

_{2}, ∅. If

*I*

_{1}∩

*Bu(B)*= ∅, by the responsiveness condition, there is at least one student

*i*in

*I*

_{1}and one student

*j*in

*I*2 such that

*i,*

*j*<

*Bu(B),*

*s*≻

*µ(i), and {i} ≻*

_{i}*s*{

*j} ≻*

*s*∅. This contradicts stability among non-bullies. Hence

*I*

_{1}∩

*Bu(B)*,∅. Since

*I*

_{2}∩

*Bu(B)*=∅holds by assumption,

*I*

_{2}\

*Bu(B)*, ∅and

|I_{1}∩*Bu(B)|*>0=|I_{2}∩*Bu(B)|.*

Case 2: µ(s)∩*Bu(B)* , ∅. If*I*_{1}\*Bu(B)* , ∅, there are*i* ∈ *I*_{1}\*Bu(B) such that*{i} ≻* _{s}* ∅and a
vacant seat at

*s*at the end of Round 1 of the TDA algorithm. This contradicts the stability of the outcome of Round 1 among non-bullies. Hence

*I*

_{1}⊆

*Bu(B).*

Suppose there is no (i, *j)* ∈ *B* such that *i* ∈ *I*1 and *j* ∈ *I*2 (otherwise, the statement of the
proposition is immediately confirmed). By the definition of a blocking group, there is no (i, *j)*∈*B*
such that *i* ∈ *I*_{1} and *j* ∈ µ(s). Hence for all *i* ∈ *I*_{1}, *s* is placed above her outside option in
her preference ordering during Round 2 of the TDA algorithm. By the construction of the DA

algorithm,|µ(s)|= *q** _{s}*and for all

*i*∈

*I*

_{1}and all

*j*∈µ(s)∩

*Bu(B),*{

*j} ≻*

*{i}. Hence,*

_{s}*I*

_{2}\

*Bu(B)*, ∅ since otherwise|I

_{1}| ≤ |I

_{2}|(by|µ(s)|=

*q*

*),{*

_{s}*j} ≻*

*{i}for all*

_{s}*j*∈

*I*

_{2}and

*i*∈

*I*

_{1}, and the responsiveness condition together imply µ(s) ≻

*(µ(s)\*

_{s}*I*2)∪

*I*1, which contradicts the definition of a blocking group. Moreover, if|I

_{2}∩

*Bu(B)| ≥ |I*

_{1}∩

*Bu(B)|*=|I

_{1}|, then

µ(s) ≻* _{s}* µ(s)\(I

_{2}\

*Bu(B))*

≻* _{s}* (((µ(s)\(I

_{2}\

*Bu(B)))*\(I

_{2}∩

*Bu(B)))*∪

*I*

_{1}= (µ(s)\

*I*

_{2})∪

*I*

_{1}.

Thusµ(s)≻* _{s}*(µ(s)\

*I*

_{2})∪

*I*

_{1}, a contradiction. Hence|I

_{1}∩

*Bu(B)|*> |I

_{2}∩

*Bu(B)|.*

*Q.E.D.*

### G S

TRONG### Q

UASI### S

TABILITYIn this section, I discuss the notion of strong quasi stability for school choice when schools have preferences/priorities over the set of subsets of students.

Given a matching µ, a blocking pair (i,*s) is* *strongly permissible* if *i* ∈ *Bu(B) and for* *any*
set ˜*I* ⊆ µ(s) that satisfies the three conditions in the definition of a blocking pair, ˜*I* , ∅ and
*I*˜∩*Bu(B)*= ∅. A matching is*strongly quasi stable*if it is feasible, individually rational, satisfies
the separation principle, and any blocking pair is strongly permissible.

Strong quasi stability only allows “justified envy” from a bully to non-bullies. One may thus argue that it fits in the notion of social priority manipulation more than quasi stability. However, the following two examples demonstrate that this stability concept has the same drawbacks as the standard stability concept in the priority-based school choice.

Example 5 (Strongly quasi stable matching may not exist). There are two schools {s1,*s*2} and
four students{i_{1},*i*_{2},*i*_{3},*i*_{4}}. The school capacities and a set of bullying incidents are given by*q*_{s}_{1} =
2,*q*_{s}_{2} =1, *B*= {(i_{1},*i*_{2}),(i_{1},*i*_{3}),(i_{4},*i*_{3})}. The student and school preferences are such that:

≻_{i}_{1} : *s*1,∅ ≻_{s}_{1} :{*i*3},{*i*1,*i*4},{*i*1},{*i*2,*i*4},{*i*2},{*i*4},∅

≻_{i}_{2} : *s*_{1},*s*_{2},∅ ≻_{s}_{2} :{i_{2}},{i_{3}},∅

≻_{i}_{3} : *s*_{2},*s*_{1},∅

≻_{i}_{4} : *s*1,∅

The preference lists for the schools are curtailed suitably. This problem is obtained by adding
*i*_{4} to the problem in Example 1 and modifying the school preferences accordingly. If *i*_{4} is not

assigned any school seat, the only candidate for a strongly quasi stable matching is described by
µ_{1}in Example 1 since it is the unique quasi stable matching in the previous framework. Hence we
only need to consider the following four matchings:

µ_{1} =

*s*_{1} *s*_{2} ∅
*i*_{2}∅ *i*_{3} *i*_{1}*i*_{4}

, µ_{2} =

*s*_{1} *s*_{2} ∅
*i*_{1}*i*_{4} *i*_{2} *i*_{3}

, µ_{3}=

*s*_{1} *s*_{2} ∅
*i*_{1}*i*_{4} *i*_{3} *i*_{2}

, µ_{4}=

*s*_{1} *s*_{2} ∅
*i*_{2}*i*_{4} *i*_{3} *i*_{1}

.

However, every matching accepts a blocking pair that is not strongly permissible (µ_{1} : (i4,*s*1),

µ_{2}: (i_{3},*s*_{1}),µ_{3}: (i_{2},*s*_{2}),µ_{4}: (i_{1},*s*_{1})). ^

Example 6(No mechanism that is strategy-proof selects a strongly quasi stable matching whenever
there exists one). There are two schools{s_{1},*s*_{2}}and five students{i_{1}, ...,*i*_{5}}. The school capacities
and the set of bullying incidents are given by *q*_{s}_{1} = 2,*q*_{s}_{2} = 1, *B* = {(i_{1},*i*_{3}),(i_{2},*i*_{3}),(i_{4},*i*_{5})}. The
student and school preferences are:

≻_{i}_{1} :*s*_{1},∅ ≻_{s}_{1} :{i_{2}},{i_{3},*i*_{4}},{i_{3}},{i_{1}},{i_{4}},∅

≻_{i}_{2} :*s*2,*s*1,∅ ≻_{s}_{2} :{i3},{i1},{i2},∅

≻_{i}_{3} :*s*_{1},*s*_{2},∅

≻_{i}_{4} :*s*_{1},∅

≻_{i}_{5} :∅

The preference lists for the schools are curtailed suitably. This problem is obtained by adding*i*_{4}
and*i*_{5} to the problem in Example 2 and modifying the school preferences accordingly. There are
two strongly quasi stable matchings:

µ=

*s*_{1} *s*_{2} ∅
*i*_{1}*i*_{2} *i*_{3} *i*_{4}*i*_{5}

, and µ˜ =

*s*_{1} *s*_{2} ∅
*i*_{3}*i*_{4} *i*_{2} *i*_{1}*i*_{5}

.

We consider a mechanism that chooses a strongly quasi stable matching whenever there exists one.

Suppose that it choosesµunder the above preference profile≻* _{I}*. Consider the following reported
preference ordering≻

^{′}

_{i}3 of*i*_{3}:

≻^{′}_{i}

3:*s*_{1},∅.

Then, ˜µis the unique strongly quasi stable matching under (≻^{′}_{i}

3,≻_{{i}_{1}_{,i}_{2}_{}}). Since*i*_{3} is better offat ˜µ
than atµ, she can profitably misreport her preferences under≻* _{I}*.

Suppose on the other hand that the mechanism chooses ˜µunder≻* _{I}*. Now consider the following
reported preference ordering≻

^{′}

_{i}1 of*i*_{1}:

≻^{′}_{i}

1:*s*1,*s*2,∅.

Then,µis the unique strongly quasi stable matching under (≻^{′}_{i}

1,≻_{{i}_{2}_{,i}_{3}_{}}). Note that if*i*_{2}is replaced
with *i*1 at ˜µ, the resulting matching is quasi stable in the corresponding problem of the previous
framework, but it is not strongly quasi stable since (i2,*s*1) is a blocking pair that is not strongly
permissible. Since *i*_{1} prefers *s*_{1} to her outside option according to her true preferences ≻_{i}_{1}, she
prefersµ(i_{1}) to ˜µ(i_{1}), meaning that she can profitably misreport her preferences under≻* _{I}*. ^

### H O

THER### S

TABILITY### C

ONCEPTSIn this section, I discuss some refinements of the stability concept other than quasi stability, and show that they are all incompatible with anti-bullying school choice mechanism design. Hence in the framework of this paper, the anti-bullying perspective is linked inexorably to quasi stability.

There are three stability concepts,α,β, andγstability, and their variants.

Definition 6. A matching isα*stable*if (i) it is feasible, (ii) individually rational, (iii) satisfies the
separation principle, (iv) there is no student who wishes for a vacant seat at some school, and (v_{α})
whenever*i*has justified envy toward *j, (i,* *j)*∈*B.*

Definition 7. A matching isβ *stable*if (i) it is feasible, (ii) individually rational, (iii) satisfies the
separation principle, (iv) there is no student who wishes for a vacant seat at some school, and (v_{β})
whenever*i*has justified envy toward *j,i*∈ *Bu(B) and* *j*∈*Vi(B).*

Definition 8. A matching isγ *stable*if (i) it is feasible, (ii) individually rational, (iii) satisfies the
separation principle, (iv) there is no student who wishes for a vacant seat at some school, and (v_{γ})
whenever*i*has justified envy toward *j,i*<*Vi(B) and* *j*∈*Vi(B).*

At each variant of stability, bullies, victims, and bystanders are equally treated among them-selves respectively. The α stability concept espouses the principle that the difference in social priorities for two students should be grounded in their own bullying episode. In other words, if two students are in no bully-victim relation, there should be no discord between them. Theβstability concept expands the range of applications of the social priority manipulation. It intends to priori-tize victims at the expense of bullies, but not of others who play no role in the bullying episodes.

Finally, theγstability concept postulates that the victims should be given priority and rights to en-roll in their preferred schools above all requests of non-victims. This may be practically desirable if, besides the policy to separate certain pairs of students, victims call for careful treatments so that they can go to safe schools.

Analogously to weak quasi stability (Definition 5), *weak stability,* *weak* α *stability,* *weak* β
*stability, andweak*γ*stability*are defined by replacing the condition (iv) in Definitions 1, 6, 7, and
8 with (iv* _{w}*) (whenever

*i*wishes for a vacant seat at some school,

*i*∈

*Bu(B)) respectively.*

Claim 1 and 2 below show that the weak stability concept and the β (orα) stability concept, either weak or not, have the same drawbacks as those for the basic stability concept.

Claim 1.*A weakly*β*stable matching does not exist in general.*

*Proof.* Consider a problem where *I* = {i_{1}, ...,*i*_{8}},*S* = {s_{1}, ...,*s*_{5}},*q*_{s}_{1} = 2,*q*_{s}_{2} = *q*_{s}_{3} = *q*_{s}_{4} = *q*_{s}_{5} = 1,
*B* = {(i_{2},*i*_{3}),(i_{5},*i*_{3}),(i_{6},*i*_{3}),(i_{6},*i*_{7})} (Bu(B) = {i_{2},*i*_{5},*i*_{6}} and *Vi(B)* = {i_{3},*i*_{7}}), and preferences and
school priorities are such that:

≻_{i}_{1} : *s*1,*s*2,∅ ≻_{s}_{1} :*i*7,*i*6,*i*3,*i*2,*i*5,*i*1,*i*4,∅

≻_{i}_{2} : *s*_{1},*s*_{3},∅ ≻_{s}_{2} :*i*_{1},*i*_{3},*i*_{4},∅

≻_{i}_{3} : *s*_{2},*s*_{1},*s*_{5},∅ ≻_{s}_{3} :*i*_{2},*i*_{6},*i*_{8},∅

≻_{i}_{4} : *s*1,*s*2,*s*4,∅ ≻_{s}_{4} :*i*4,*i*5,*i*8,∅

≻_{i}_{5} : *s*_{4},*s*_{1},∅ ≻_{s}_{5} :*i*_{3},*i*_{7},∅

≻_{i}_{6} : *s*_{3},*s*_{1},∅

≻_{i}_{7} : *s*5,*s*1,∅

≻_{i}_{8} : *s*_{3},*s*_{4},∅

The priority lists for the schools are curtailed suitably. Suppose that *i*7 is matched with *s*5. Then
the unique candidate for a weaklyβstable matching is the one marked with ♣in Table 1. In this
matching,*i*_{3}has justified envy toward*i*_{7}and*i*_{3},*i*_{7}∈*Vi(B), meaning that it is not weakly*βstable.

Next, suppose that*i*_{7}is enrolled in *s*_{1}. Then,*i*_{3} needs to enter *s*_{5}since otherwise *i*_{7}wishes for
a vacant seat at *s*_{5}. To avoid the case where*i*_{3} wishes for a vacant seat at *s*_{1} or has justified envy
toward*i*7’s buddy,*s*1 needs to admit*i*6. However, (i_{6},*i*7)∈ *B*requests the separation of*i*7from*i*6.
Hence, if*i*7is in *s*1, the resulting matching is by no means weaklyβstable.

Finally, if *i*_{7} is not enrolled in any school, she would wish for a vacant seat at *s*_{1}, or have

justified envy toward a student in it (note that *i*_{6} is the only student who victimizes her). This

completes the proof. *Q.E.D.*

*s*_{1} *s*_{2} *s*_{3} *s*_{4} Remark

∅∅ - - - *i*1→ *s*1

*i∅* - - - *i*_{4} → *s*_{1}(i, *i*_{4})
*i*_{4}∅ - - - *i*_{1}→ *s*_{1}
*i*1*i*2 *i*3 - *i*^{∗}_{5} *i*4 → *s*4(i5)
*i*_{1}*i*_{2} *i*_{4} - *i*^{∗}_{5} *i*_{3} → *s*_{2}(i_{4})
*i*_{1}*i*_{3} - - - *i*_{3}→ *s*_{2}
*i*1*i*4 - - - *i*2 → *s*1(i1)
*i*_{1}*i*_{5} - - - *i*_{2} → *s*_{1}(i_{1})
*i*_{1}*i*_{6} - - - *i*_{2} → *s*_{1}(i_{1})
*i*2*i*4 - - - *i*1 → *s*1(i4)
*i*_{2}*i*_{5} - *i*^{∗}_{6} ∅ *i*_{8}→ *s*_{4}
*i*_{2}*i*_{5} - *i*^{∗}_{6} *i*_{8} *i*_{5} → *s*_{4}(i_{8})
*i*2*i*5 ∅ *i*^{∗}_{6} *i*4 *i*4→ *s*2

*i*_{2}*i*_{5} *i*_{3} *i*^{∗}_{6} *i*_{4} *i*_{1}→ *s*_{2}(i_{3})♠
*i*_{2}*i*_{5} *i*_{1} *i*^{∗}_{6} *i*_{4} ♣
*i*2*i*6 - ∅ - *i*8→ *s*3

*i*_{2}*i*_{6} - *i*_{8} - *i*_{6} → *s*_{3}(i_{8})
*i*_{3}*i*_{4} - - - *i*_{1} → *s*_{1}(i_{4})
*i*4*i*5 - - - *i*1 → *s*1(i4)
*i*_{4}*i*_{6} - - - *i*_{1} → *s*_{1}(i_{4})
*i*_{5}*i*_{6} - - - *i*_{2} → *s*_{1}(i_{5})

Table 1: In the Remark column, “i→ *s” means “i*wishes for a vacant seat at *s” or “i*has justified
envy toward another student in*s”. Especially, “i*→ *s(j)” means “i*has justified envy toward *j*who
belongs to *s”. An asterisk at the upper right of a student’s identity means that she needs to enroll*
in a school specified above so as not to have justified envy toward another student in*s*_{1}.

Claim 2.

1. *There is no mechanism that is strategy-proof and selects a weakly stable matching whenever*
*there exists one.*

2. *There is no mechanism that is strategy-proof and selects an* α *stable matching whenever*
*there exists one.*

3. *There is no mechanism that is strategy-proof and selects a weakly*α*stable matching *
*when-ever there exists one.*

4. *There is no mechanism that is strategy-proof and selects a*β*stable matching whenever there*
*exists one.*

5. *There is no mechanism that is strategy-proof and selects a weakly*β*stable matching *
*when-ever there exists one.*

*Proof.* I first prove the first statement. Consider a problem where *I* = {i1,*i*2,*i*3,*i*4}, *S* = {s1,*s*2},
*q*_{s}_{1} = 2,*q*_{s}_{2} = 1,*B*={(i_{1},*i*_{3}),(i_{1},*i*_{4}),(i_{2},*i*_{3})}(Bu(B)= {i_{1},*i*_{2}}), and preferences and school priorities
are such that:

≻_{i}_{1} : *s*1,∅ ≻_{s}_{1} :*i*2,*i*3,*i*1,*i*4,∅

≻_{i}_{2} : *s*_{2},*s*_{1},∅ ≻_{s}_{2} :*i*_{3},*i*_{1},*i*_{2},*i*_{4},∅

≻_{i}_{3} : *s*_{1},*s*_{2},∅

≻_{i}_{4} : *s*1,∅

Note that this problem is similar to the one in Example 2: differences appear in≻_{i}_{4}, ≻_{s}_{1}, and≻_{s}_{2}.
There are two weakly stable matchings in this problem:

µ=

*s*1 *s*2 ∅
*i*_{1}*i*_{2} *i*_{3} *i*_{4}

, and µ˜ =

*s*1 *s*2 ∅
*i*_{3}*i*_{4} *i*_{2} *i*_{1}

.

Suppose that a mechanism choosesµunder the above preference profile≻* _{I}*. Consider the following
reported preference ordering≻

^{′}

_{i}3 of*i*_{3},

≻^{′}_{i}

3:*s*1,∅.

Then, ˜µis the unique weakly stable matching under (≻^{′}_{i}

3,≻_{{i}_{1}_{,i}_{2}_{,i}_{4}_{}}). Since*i*_{3} prefers ˜µ(i_{3}) to µ(i_{3}),
she can profitably misreport her preferences under≻* _{I}*.

Suppose on the other hand that a mechanism chooses ˜µunder≻* _{I}*. Now consider the following
reported preference ordering≻

^{′}

_{i}1 of*i*_{1},

≻^{′}_{i}

1:*s*_{1},*s*_{2},∅.

Then, µ is the unique stable matching under (≻^{′}_{i}

1,≻_{{i}_{2}_{,i}_{3}_{,i}_{4}_{}}). Since *i*_{1} prefers *s*_{1} to her outside
op-tion according to her true preferences ≻_{i}_{1}, she prefers µ(i_{1}) to ˜µ(i_{1}), meaning she can profitably
misreport her preferences under≻* _{I}*. This completes the proof of the first statement.

Next, I prove the last statement. Consider a problem where *I* = {i_{1}, ...,*i*_{9}}, *S* = {s_{1}, ...,*s*_{6}},

*q*_{s}_{1} = 2,*q*_{s}_{2} = *q*_{s}_{3} = *q*_{s}_{4} = *q*_{s}_{5} = *q*_{s}_{6} = 1, *B* = {(i_{2},*i*_{3}),(i_{5},*i*_{3}),(i_{6},*i*_{3}),(i_{6},*i*_{7})}(Bu(B)= {i_{2},*i*_{5},*i*_{6}}and
*Vi(B)*={i_{3},*i*_{7}}), and preferences and school priorities are such that:

≻_{i}_{1} : *s*_{1},*s*_{2},∅ ≻_{s}_{1} :*i*_{7},*i*_{6},*i*_{3},*i*_{2},*i*_{5},*i*_{1},*i*_{4},∅

≻_{i}_{2} : *s*1,*s*3,∅ ≻_{s}_{2} :*i*1,*i*3,*i*4,∅

≻_{i}_{3} : *s*_{2},*s*_{1},*s*_{3},∅ ≻_{s}_{3} :*i*_{2},*i*_{6},*i*_{9},*i*_{3},*i*_{8},∅

≻_{i}_{4} : *s*_{1},*s*_{2},*s*_{4},∅ ≻_{s}_{4} :*i*_{4},*i*_{5},*i*_{8},∅

≻_{i}_{5} : *s*4,*s*1,∅ ≻_{s}_{5} :*i*3,*i*7,∅

≻_{i}_{6} : *s*_{3},*s*_{1},∅ ≻_{s}_{6} :*i*_{5},*i*_{9},∅

≻_{i}_{7} : *s*_{5},*s*_{1},∅

≻_{i}_{8} : *s*3,*s*4,∅

≻_{i}_{9} : *s*_{6},*s*_{3},∅

The priority lists for the schools are curtailed suitably. Note that this problem is similar to the one
in the proof of Claim 1: differences appear in ≻_{i}_{3},≻_{i}_{9},≻_{s}_{3}, and≻_{s}_{6}. Since*i*_{3} ≻_{i}_{3} *s*_{5} and*i*_{5} ≻_{i}_{5} *s*_{6},
*i*_{7} and *i*_{9} enter *s*_{5} and *s*_{6} respectively in all weaklyβ stable matchings. Hence the only matching
in Table 1 that also gives a description of a weakly βstable matching in this problem is the one
marked with♣. Moreover, since *s*_{3} ≻_{i}_{3} *i*_{3}, there is another weakly βstable matching in which*i*_{3}
enters*s*_{3}. In sum, there are two weaklyβstable matchings in this problem:

µ=

*s*_{1} *s*_{2} *s*_{3} *s*_{4} *s*_{5} *s*_{6} ∅
*i*_{2}*i*_{5} *i*_{1} *i*_{6} *i*_{4} *i*_{7} *i*_{9} *i*_{3}*i*_{8}

, and µ˜ =

*s*_{1} *s*_{2} *s*_{3} *s*_{4} *s*_{5} *s*_{6} ∅
*i*_{2}*i*_{6} *i*_{1} *i*_{3} *i*_{4} *i*_{7} *i*_{9} *i*_{5}*i*_{8}

.

We consider a mechanism that chooses a weakly β stable matching whenever there exists one.

Suppose that it choosesµunder the above preference profile≻* _{I}*. Consider the following reported
preference ordering≻

^{′}

_{i}3 of*i*_{3},

≻^{′}_{i}

3:*s*_{2},*s*_{1},*s*_{3},*s*_{5},∅.

Then, ˜µis the unique weaklyβstable matching under (≻^{′}_{i}

3,≻_{I\{i}_{3}_{}}). To see this is true, suppose that
*i*_{3}enters*s*_{5}. Then,*i*_{7}is in*s*_{1}and, to avoid the case where*i*_{3}wishes for a vacant seat at*s*_{1}or she has
justified envy toward*i*_{7}’s buddy,*i*_{6}has to be in *s*_{1}. But this is incompatible with (i_{6},*i*_{7})∈*B. Hence*
at any weaklyβstable matching,*i*_{3}does not enter*s*_{5}, meaning that ˜µis the unique one. As a result,
*i*3can misrepresent her preferences to her advantage.

Suppose on the other hand that the mechanism chooses ˜µunder≻* _{I}*. Now consider the following
reported preference ordering≻

^{′}

_{i}5 of*i*_{5}:

≻^{′}_{i}

5:*s*_{4},*s*_{1},*s*_{6},∅.

Then,µis the unique weaklyβstable matching under (≻^{′}_{i}

5,≻_{I\{i}_{5}_{}}). To see this is true, suppose that
*i*5enters*s*6. Then, the resulting matching is by no means weaklyβstable as it is shown by Table 2.

As a result,*i*5 can beneficially misrepresent her preferences. To summarize, any mechanism that
selects a weaklyβstable matching whenever there exists one is by no means strategy-proof.

Note that in this problem, the two weaklyβstable matchingsµand ˜µare bothαstable, thus they
are weaklyαstable andβstable (µis stable; *i*_{6} has justified envy toward*i*_{3} at ˜µ, but (i_{6},*i*_{3}) ∈ *B).*

Moreover, ˜µisαstable under (≻^{′}_{i}

3,≻_{I\{i}_{3}_{}}) andµisαstable under (≻^{′}_{i}

5,≻_{I\{i}_{5}_{}}). Thus, we have already

verified the statements 2-4. This completes the proof. *Q.E.D.*

*s*_{1} *s*_{2} *s*_{3} *s*_{4} *s*_{5} *s*_{6} Remark

∅∅ - - *i*4 - *i*5 *i*4 → *s*1

*i∅* - - *i*_{4} - *i*_{5} *i*_{4} → *s*_{1}(i: arbitrary)
*i*_{1}*i*_{2} - - *i*_{4} - *i*_{5} *i*_{5} → *s*_{1}(i_{1})
*i*1*i*3 - - *i*4 - *i*5 *i*3 → *s*2

*i*_{1}*i*_{6} - - *i*_{4} - *i*_{5} *i*_{2} → *s*_{1}(i_{1})
*i*_{2}*i*_{6} - ∅ *i*_{4} - *i*_{5} *i*_{3} → *s*_{3}
*i*2*i*6 - *i*3 *i*4 - *i*5 *i*9 → *s*3(i3)
*i*_{2}*i*_{6} - *i*_{8} *i*_{4} - *i*_{5} *i*_{9} → *s*_{3}(i_{8})
*i*_{2}*i*_{6} - *i*_{9} *i*_{4} - *i*_{5} *i*_{6} → *s*_{3}(i_{9})
*i*2*i*7 - - *i*4 - *i*5 *i*7 → *s*5

*i*_{3}*i*_{7} - - *i*_{4} - *i*_{5} *i*_{7} → *s*_{5}

Table 2: The description follows the same rule as the one for Table 1. Note that if*i*4is not in *s*4,*i*5

wishes for a vacant at that school. Hence if*i*_{5}enters *s*_{6}at some weaklyβstable matching,*i*_{4}must
enter*s*_{4}at the same time.

Contrary to the previous two stability concepts, a γ stable matching always exists and is im-plementable via a strategy-proof mechanism. To see this is true, consider an algorithm, similar to the TDA algorithm, where only the victims participate in the first round, assignment for them is finalized after the first run of the DA algorithm, then each bully puts every school where her victims were accepted in the previous round below her outside option, and finally the second DA algorithm is run for the rest of the students and the school seats. It is easy to show that the output

of this algorithm isγstable and the induced mechanism is strategy-proof.

However, Claim 3 below shows that not only this mechanism, but also any mechanism that produces a (weakly)γstable matching for any input is by no means bullying-resistant. Therefore, if this stability concept is pursued along a school choice mechanism despite its incongruence with the desideratum, a punitive deterrent against school bullying, if any is desired, must be supplemented by other auxiliary policies in the whole anti-bullying program. Given its plausibility and potential usability, I believe that the further examination of the virtues of the γ stability concept must be undertaken as a theoretical enterprise in the future work.

Claim 3. *There is no mechanism that produces a weakly*γ *stable matching for any input and is*
*bullying-resistant.*

*Proof.* Consider a problem where *I* = {i_{1}, ...,*i*_{9}}, *S* = {s_{1}, ...,*s*_{6}}, *q*_{s}_{1} = 2,*q*_{s}_{2} = *q*_{s}_{3} = *q*_{s}_{4} = *q*_{s}_{5} =
*q*_{s}_{6} = 1, *B* = {(i_{2},*i*_{3}),(i_{5},*i*_{3}),(i_{6},*i*_{3}),(i_{6},*i*_{7})}(Vi(B) = {i_{3},*i*_{7}}), and preferences and school priorities
are such that:

≻_{i}_{1} : *s*1,*s*2,*s*6,∅ ≻_{s}_{1} :*i*7,*i*6,*i*3,*i*2,*i*5,*i*1,*i*4,∅

≻_{i}_{2} : *s*_{1},*s*_{3},∅ ≻_{s}_{2} :*i*_{1},*i*_{3},*i*_{4},∅

≻_{i}_{3} : *s*_{2},*s*_{1},*s*_{5},∅ ≻_{s}_{3} :*i*_{2},*i*_{6},*i*_{8},∅

≻_{i}_{4} : *s*1,*s*2,*s*4,∅ ≻_{s}_{4} :*i*4,*i*5,*i*8,∅

≻_{i}_{5} : *s*_{4},*s*_{1},∅ ≻_{s}_{5} :*i*_{3},*i*_{7},∅

≻_{i}_{6} : *s*_{3},*s*_{1},∅ ≻_{s}_{6} :*i*_{1},*i*_{9},∅

≻_{i}_{7} : *s*5,*s*1,∅

≻_{i}_{8} : *s*_{3},*s*_{4},∅

≻_{i}_{9} : *s*_{6},∅

The priority lists for the schools are curtailed suitably. Note that this problem is similar to the
one in the proof of Claim 1: differences appear in ≻_{i}_{1},≻_{i}_{9}, and≻_{s}_{6}. Since*i*7 ∈*Vi(B), she must be*
enrolled in *s*5 at any weaklyγ stable matching for the same reason I described previously. Then
in Table 1, according to the Remark column, the only candidate for a weaklyγstable matching is
the one marked with♠because*i*_{3} ∈*Vi(B) andi*_{1} < *Vi(B). There is thus a unique weakly* γstable