A PPENDIX [NOT FOR PUBLICATION]

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. SupposeB=∅and letµbe an arbitrary stable matching. For any ˜µwhich dominates it and for any s∈S,|µ(s)|<q_sif and only if|µ(s)|˜ <q_s, and in this case,µ(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 µ(i) and

|µ(s)|<qs, theni∈Bu(B) (otherwiseiwas rejected by sat Round 1 of the TDA algorithm), ands accepts her victim (otherwiseiwas rejected bysat 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 ihas 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 µ(i)}. There are two cases to consider.

Case 1: ˜I \ Bu(B) , ∅. Let µ₁ denote a matching such that µ₁(i) = µ(i) for all i < Bu(B), and µ₁(i) = i for all i ∈ Bu(B). We define ˜µ₁ 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, ˜µ₁ dominates µ₁. Sinceµ₁is a student-optimal stable matching given the modified preferences, there is at least one student i < Bu(B) at ˜µ₁ 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., ˜µ₁(j) ≻_i µ˜₁(i) andi ≻_µ˜1(j) j). Suppose the first possibility holds. By Lemma 1, ifs ∈S has a vacant seat at ˜µ₁, it also has a vacant seat atµ₁. Sinces ≻_i µ˜₁(i)_i µ₁(i), she wishes for the vacant seat atµ₁, which contradicts the stability ofµ₁. Next, suppose the second possibility holds. Then|µ˜₁( ˜µ₁(j))|= q_µ˜1(j)is true for the same reason we discussed above. Since|µ˜₁( ˜µ₁(j))|= qµ˜1(j)implies|µ( ˜˜ µ(j))|= qµ(˜ j)and ˜µ( ˜µ(j))∩Bu(B)= ∅. Hence, i<Bu(B) and she has justified envy toward jat ˜µ, which contradicts the quasi stability of ˜µ.

Case 2: ˜I ⊆ Bu(B). Let µ₂ denote a matching such that µ₂(i) = µ(i) for all i ∈ Bu(B) and µ₂(i) = i for alli < Bu(B). We define ˜µ₂ 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µ₁(= µ˜₁), she lowers the preference ranking of sbelow her outside option; for each i< Bu(B),i≻_i sfor all s∈S; each schools∈S reduces its capacity by|µ₁(s)|(=|˜µ₁(s)|). Thenµ₂ is a student-optimal stable matching and ˜µ₂dominatesµ₂. Supposei ∈Bu(B) wishes for a vacant seat ofs ∈S at ˜µ₂. By Lemma 1,salso leaves the seat vacant and does not accept any victims of iat ˜µ. This contradicts the quasi stability of ˜µ. Next, supposei ∈Bu(B) has justified envy toward j∈Bu(B) at ˜µ₂. Since ˜µ₂(j) does not accept any victims ofiat ˜µ, 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 Band 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^′ impliess_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 assumptioni<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µ. Leti ∈Ibe 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 toi. Thus, for any student jwho is removed earlier thani, ˜µ(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^˜ denotei’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.

(∵ LetC¹,C², ...,Cⁿ, ...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. Supposeiis inCⁿ. Hence whatever preferences ireports, we can removeC¹,C², ...,Cⁿ⁻¹ in the firstn−1 steps. Now supposeireports≻^µ_i. After removingC¹, ...,Cⁿ⁻¹, we can immediately removeCⁿ, followed byCⁿ⁺¹,Cⁿ⁺², ...which results inµ.)

Suppose ϕ^{T T C}_i ( ˜≻_I˜,≻_−I˜,B) _i µ(i) holds for all i ∈ I. Let ˜˜ µ denote ϕ^{T T C}( ˜≻_I˜,≻_−˜I,B). By the previous discussion, ϕ^{T T C}(≻^µ˜_˜

I,≻_−I˜,B) = µ. Let˜ C¹,C², ... 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 cyclesC¹, ...,C^t−1 in the same order under (≻^µ˜_˜

I,≻₋I˜,B) and there is a student inC^t who is a member of ˜I(indeed, ifC^t is the first cycle where a nonempty subset of ˜Iis involved, it is possible to removeC¹,C², ...,C^t−1 in the first 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 studenti. By the construction of the TTC algorithm, after removingC¹, ...,C^t−1there is no remaining school that is preferable foriin terms of≻_i to her outside option and has not accepted any student who victimizes her or is victimized by her. Hence i ≻^µ_i^˜ s holds for all s ∈ S, meaning thatC^t can be removed immediately after C¹, ...,C^t−1 even under the preference profile (≻^µ˜_˜

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^˜ iand i ≻^µ_i^˜ s for all s ∈ S \ {µ(i)}.

As in the previous case, therefore,C^t can be removed immediately afterC¹, ...,C^t−1even under the preference profile (≻^µ˜_˜

I,≻₋I˜).

To summarize, it is possible to removeC¹,C², ...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 thatBandB^′= B∪ {(i, j)}are both sets of bullying incidents. Let µ^′≡ ϕ^{T T C}(≻_I,B^′). Consider the TTC algorithm for (≻_I,B). Ifiand jare removed at the same step, they are also removed simultaneously under (≻I,B^′) and assigned to the same schools acrossµand µ^′. If iis removed earlier than j,µ(i)= µ^′(i). Finally, if jis removed earlier thani, the allocation to those removed earlier thaniis 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₁, ...,i₆}, S = {s₁,s₂,s₃,s₄},q_s1 = q_s2 = q_s3 = 1, q_s4 = 2, B= ∅, and preferences are given by

≻_i1,≻_i2 : s₄,s₁,∅

≻_i3,≻_i4 : s4,s2,∅

≻_i5,≻_i6 : s₄,s₃,∅.

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:

µ=











s1 s2 s3 s4 ∅ ∅

∅ i3 i5 i1 i2 i4 i6











. (1)

If B is replaced by B^′ = {(i₂,i1),(i₄,i1),(i₆,i1)}, i1 or i2 must leave s4. By the group bullying-resistance property, neitheri4 nor i6 enters s4. Then by constrained Pareto efficiency, either i3 or i₅ enters s₄, which induces a transfer of i₄ or i₆ to s₂ or s₃. This contradicts the group bullying-resistance property.

Consider the following possible outcome of a mechanism

µ^′ =











s1 s2 s3 s4 ∅ i₂ i₄ i₅ i₁i₃ i₆









 .

IfBis replaced byB^′′ ={(i2,i1),(i3,i1),(i4,i1),(i6,i1)},i1ori3must leaves4. By the group bullying-resistance property,s₄does not accepti₂,i₄,nori₆. By constrained Pareto efficiency,i₅andi₆enter s₄ and s₃ 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:

≻_s1,≻_s2,≻_s3,≻_s4:i1,i2,i3,i4,i5,i6.

The matchingµ(see (1)) is the unique (quasi) stable matching whenB=∅. Following the argument in the proof of Theorem 3, we observe that ifBis replaced byB^′ ={(i₂,i₁),(i₄,i₁),(i₆,i₁)}, there is at least one student in{i₂,i₄,i₆}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. SupposeB = ∅. 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₂∩Bu(B) = ∅, then by the responsiveness condition, for any student jin 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. Hencei∈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 anyi < 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_s and in this case, ˜µ(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_sandµ(s)≻_s µ(s). This contradicts the assumption that˜

µ˜ 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 I2 ⊆ µ(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₁ and j ∈ I₂, confirming the statement of the proposition. Suppose instead that |µ(s)| = q_s and I₂ , ∅. If I₁∩Bu(B)= ∅, by the responsiveness condition, there is at least one studentiinI₁and one student j in I2 such that i, j < Bu(B), s ≻_i µ(i), and {i} ≻s {j} ≻s ∅. This contradicts stability among non-bullies. HenceI₁∩Bu(B),∅. SinceI₂∩Bu(B)=∅holds by assumption,I₂\Bu(B), ∅and

|I₁∩Bu(B)|>0=|I₂∩Bu(B)|.

Case 2: µ(s)∩Bu(B) , ∅. IfI₁\Bu(B) , ∅, there arei ∈ I₁\Bu(B) such that{i} ≻_s ∅and a vacant seat at sat the end of Round 1 of the TDA algorithm. This contradicts the stability of the outcome of Round 1 among non-bullies. HenceI₁ ⊆ Bu(B).

Suppose there is no (i, j) ∈ B such that i ∈ I1 and j ∈ I2 (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₁ and j ∈ µ(s). Hence for all i ∈ I₁, 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_sand for alli ∈ I₁and all j ∈µ(s)∩Bu(B),{j} ≻_s {i}. Hence, I₂\Bu(B) , ∅ since otherwise|I₁| ≤ |I₂|(by|µ(s)|=q_s),{j} ≻_s{i}for all j∈I₂ andi∈I₁, and the responsiveness condition together imply µ(s) ≻_s (µ(s)\ I2)∪ I1, which contradicts the definition of a blocking group. Moreover, if|I₂∩Bu(B)| ≥ |I₁∩Bu(B)|=|I₁|, then

µ(s) ≻_s µ(s)\(I₂\Bu(B))

≻_s (((µ(s)\(I₂\Bu(B)))\(I₂∩Bu(B)))∪I₁= (µ(s)\I₂)∪I₁.

Thusµ(s)≻_s(µ(s)\I₂)∪I₁, a contradiction. Hence|I₁∩Bu(B)|> |I₂∩Bu(B)|. Q.E.D.

G S

TRONG

Q

UASI

S

TABILITY

In 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 isstrongly quasi stableif 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,s2} and four students{i₁,i₂,i₃,i₄}. The school capacities and a set of bullying incidents are given byq_s1 = 2,q_s2 =1, B= {(i₁,i₂),(i₁,i₃),(i₄,i₃)}. The student and school preferences are such that:

≻_i1 : s1,∅ ≻_s1 :{i3},{i1,i4},{i1},{i2,i4},{i2},{i4},∅

≻_i2 : s₁,s₂,∅ ≻_s2 :{i₂},{i₃},∅

≻_i3 : s₂,s₁,∅

≻_i4 : s1,∅

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

assigned any school seat, the only candidate for a strongly quasi stable matching is described by µ₁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:

µ₁ =











s₁ s₂ ∅ i₂∅ i₃ i₁i₄









 , µ₂ =











s₁ s₂ ∅ i₁i₄ i₂ i₃









 , µ₃=











s₁ s₂ ∅ i₁i₄ i₃ i₂









 , µ₄=











s₁ s₂ ∅ i₂i₄ i₃ i₁









 .

However, every matching accepts a blocking pair that is not strongly permissible (µ₁ : (i4,s1),

µ₂: (i₃,s₁),µ₃: (i₂,s₂),µ₄: (i₁,s₁)). ^

Example 6(No mechanism that is strategy-proof selects a strongly quasi stable matching whenever there exists one). There are two schools{s₁,s₂}and five students{i₁, ...,i₅}. The school capacities and the set of bullying incidents are given by q_s1 = 2,q_s2 = 1, B = {(i₁,i₃),(i₂,i₃),(i₄,i₅)}. The student and school preferences are:

≻_i1 :s₁,∅ ≻_s1 :{i₂},{i₃,i₄},{i₃},{i₁},{i₄},∅

≻_i2 :s2,s1,∅ ≻_s2 :{i3},{i1},{i2},∅

≻_i3 :s₁,s₂,∅

≻_i4 :s₁,∅

≻_i5 :∅

The preference lists for the schools are curtailed suitably. This problem is obtained by addingi₄ andi₅ to the problem in Example 2 and modifying the school preferences accordingly. There are two strongly quasi stable matchings:

µ=











s₁ s₂ ∅ i₁i₂ i₃ i₄i₅











, and µ˜ =











s₁ s₂ ∅ i₃i₄ i₂ i₁i₅









 .

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 ofi₃:

≻^′_i

3:s₁,∅.

Then, ˜µis the unique strongly quasi stable matching under (≻^′_i

3,≻_{i1,i2}). Sincei₃ 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 ofi₁:

≻^′_i

1:s1,s2,∅.

Then,µis the unique strongly quasi stable matching under (≻^′_i

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

H O

THER

S

TABILITY

C

ONCEPTS

In 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αstableif (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_α) wheneverihas justified envy toward j, (i, j)∈B.

Definition 7. A matching isβ stableif (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_β) wheneverihas justified envy toward j,i∈ Bu(B) and j∈Vi(B).

Definition 8. A matching isγ stableif (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_γ) wheneverihas 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γstabilityare defined by replacing the condition (iv) in Definitions 1, 6, 7, and 8 with (iv_w) (wheneveriwishes 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₁, ...,i₈},S = {s₁, ...,s₅},q_s1 = 2,q_s2 = q_s3 = q_s4 = q_s5 = 1, B = {(i₂,i₃),(i₅,i₃),(i₆,i₃),(i₆,i₇)} (Bu(B) = {i₂,i₅,i₆} and Vi(B) = {i₃,i₇}), and preferences and school priorities are such that:

≻_i1 : s1,s2,∅ ≻_s1 :i7,i6,i3,i2,i5,i1,i4,∅

≻_i2 : s₁,s₃,∅ ≻_s2 :i₁,i₃,i₄,∅

≻_i3 : s₂,s₁,s₅,∅ ≻_s3 :i₂,i₆,i₈,∅

≻_i4 : s1,s2,s4,∅ ≻_s4 :i4,i5,i8,∅

≻_i5 : s₄,s₁,∅ ≻_s5 :i₃,i₇,∅

≻_i6 : s₃,s₁,∅

≻_i7 : s5,s1,∅

≻_i8 : s₃,s₄,∅

The priority lists for the schools are curtailed suitably. Suppose that i7 is matched with s5. Then the unique candidate for a weaklyβstable matching is the one marked with ♣in Table 1. In this matching,i₃has justified envy towardi₇andi₃,i₇∈Vi(B), meaning that it is not weaklyβstable.

Next, suppose thati₇is enrolled in s₁. Then,i₃ needs to enter s₅since otherwise i₇wishes for a vacant seat at s₅. To avoid the case wherei₃ wishes for a vacant seat at s₁ or has justified envy towardi7’s buddy,s1 needs to admiti6. However, (i₆,i7)∈ Brequests the separation ofi7fromi6. Hence, ifi7is in s1, the resulting matching is by no means weaklyβstable.

Finally, if i₇ is not enrolled in any school, she would wish for a vacant seat at s₁, or have

justified envy toward a student in it (note that i₆ is the only student who victimizes her). This

completes the proof. Q.E.D.

s₁ s₂ s₃ s₄ Remark

∅∅ - - - i1→ s1

i∅ - - - i₄ → s₁(i, i₄) i₄∅ - - - i₁→ s₁ i1i2 i3 - i^∗₅ i4 → s4(i5) i₁i₂ i₄ - i^∗₅ i₃ → s₂(i₄) i₁i₃ - - - i₃→ s₂ i1i4 - - - i2 → s1(i1) i₁i₅ - - - i₂ → s₁(i₁) i₁i₆ - - - i₂ → s₁(i₁) i2i4 - - - i1 → s1(i4) i₂i₅ - i^∗₆ ∅ i₈→ s₄ i₂i₅ - i^∗₆ i₈ i₅ → s₄(i₈) i2i5 ∅ i^∗₆ i4 i4→ s2

i₂i₅ i₃ i^∗₆ i₄ i₁→ s₂(i₃)♠ i₂i₅ i₁ i^∗₆ i₄ ♣ i2i6 - ∅ - i8→ s3

i₂i₆ - i₈ - i₆ → s₃(i₈) i₃i₄ - - - i₁ → s₁(i₄) i4i5 - - - i1 → s1(i4) i₄i₆ - - - i₁ → s₁(i₄) i₅i₆ - - - i₂ → s₁(i₅)

Table 1: In the Remark column, “i→ s” means “iwishes for a vacant seat at s” or “ihas justified envy toward another student ins”. Especially, “i→ s(j)” means “ihas justified envy toward jwho 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 ins₁.

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,i2,i3,i4}, S = {s1,s2}, q_s1 = 2,q_s2 = 1,B={(i₁,i₃),(i₁,i₄),(i₂,i₃)}(Bu(B)= {i₁,i₂}), and preferences and school priorities are such that:

≻_i1 : s1,∅ ≻_s1 :i2,i3,i1,i4,∅

≻_i2 : s₂,s₁,∅ ≻_s2 :i₃,i₁,i₂,i₄,∅

≻_i3 : s₁,s₂,∅

≻_i4 : s1,∅

Note that this problem is similar to the one in Example 2: differences appear in≻_i4, ≻_s1, and≻_s2. There are two weakly stable matchings in this problem:

µ=











s1 s2 ∅ i₁i₂ i₃ i₄











, and µ˜ =











s1 s2 ∅ i₃i₄ i₂ i₁









 .

Suppose that a mechanism choosesµunder the above preference profile≻_I. Consider the following reported preference ordering≻^′_i

3 ofi₃,

≻^′_i

3:s1,∅.

Then, ˜µis the unique weakly stable matching under (≻^′_i

3,≻_{i1,i2,i4}). Sincei₃ prefers ˜µ(i₃) to µ(i₃), 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 ofi₁,

≻^′_i

1:s₁,s₂,∅.

Then, µ is the unique stable matching under (≻^′_i

1,≻_{i2,i3,i4}). Since i₁ prefers s₁ to her outside op-tion according to her true preferences ≻_i1, she prefers µ(i₁) to ˜µ(i₁), 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₁, ...,i₉}, S = {s₁, ...,s₆},

q_s1 = 2,q_s2 = q_s3 = q_s4 = q_s5 = q_s6 = 1, B = {(i₂,i₃),(i₅,i₃),(i₆,i₃),(i₆,i₇)}(Bu(B)= {i₂,i₅,i₆}and Vi(B)={i₃,i₇}), and preferences and school priorities are such that:

≻_i1 : s₁,s₂,∅ ≻_s1 :i₇,i₆,i₃,i₂,i₅,i₁,i₄,∅

≻_i2 : s1,s3,∅ ≻_s2 :i1,i3,i4,∅

≻_i3 : s₂,s₁,s₃,∅ ≻_s3 :i₂,i₆,i₉,i₃,i₈,∅

≻_i4 : s₁,s₂,s₄,∅ ≻_s4 :i₄,i₅,i₈,∅

≻_i5 : s4,s1,∅ ≻_s5 :i3,i7,∅

≻_i6 : s₃,s₁,∅ ≻_s6 :i₅,i₉,∅

≻_i7 : s₅,s₁,∅

≻_i8 : s3,s4,∅

≻_i9 : s₆,s₃,∅

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 ≻_i3,≻_i9,≻_s3, and≻_s6. Sincei₃ ≻_i3 s₅ andi₅ ≻_i5 s₆, i₇ and i₉ enter s₅ and s₆ 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₃ ≻_i3 i₃, there is another weakly βstable matching in whichi₃ enterss₃. In sum, there are two weaklyβstable matchings in this problem:

µ=











s₁ s₂ s₃ s₄ s₅ s₆ ∅ i₂i₅ i₁ i₆ i₄ i₇ i₉ i₃i₈











, and µ˜ =











s₁ s₂ s₃ s₄ s₅ s₆ ∅ i₂i₆ i₁ i₃ i₄ i₇ i₉ i₅i₈









 .

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 ofi₃,

≻^′_i

3:s₂,s₁,s₃,s₅,∅.

Then, ˜µis the unique weaklyβstable matching under (≻^′_i

3,≻_I\{i3}). To see this is true, suppose that i₃enterss₅. Then,i₇is ins₁and, to avoid the case wherei₃wishes for a vacant seat ats₁or she has justified envy towardi₇’s buddy,i₆has to be in s₁. But this is incompatible with (i₆,i₇)∈B. Hence at any weaklyβstable matching,i₃does not enters₅, meaning that ˜µis the unique one. As a result, i3can 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 ofi₅:

≻^′_i

5:s₄,s₁,s₆,∅.

Then,µis the unique weaklyβstable matching under (≻^′_i

5,≻_I\{i5}). To see this is true, suppose that i5enterss6. Then, the resulting matching is by no means weaklyβstable as it is shown by Table 2.

As a result,i5 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₆ has justified envy towardi₃ at ˜µ, but (i₆,i₃) ∈ B).

Moreover, ˜µisαstable under (≻^′_i

3,≻_I\{i3}) andµisαstable under (≻^′_i

5,≻_I\{i5}). Thus, we have already

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

s₁ s₂ s₃ s₄ s₅ s₆ Remark

∅∅ - - i4 - i5 i4 → s1

i∅ - - i₄ - i₅ i₄ → s₁(i: arbitrary) i₁i₂ - - i₄ - i₅ i₅ → s₁(i₁) i1i3 - - i4 - i5 i3 → s2

i₁i₆ - - i₄ - i₅ i₂ → s₁(i₁) i₂i₆ - ∅ i₄ - i₅ i₃ → s₃ i2i6 - i3 i4 - i5 i9 → s3(i3) i₂i₆ - i₈ i₄ - i₅ i₉ → s₃(i₈) i₂i₆ - i₉ i₄ - i₅ i₆ → s₃(i₉) i2i7 - - i4 - i5 i7 → s5

i₃i₇ - - i₄ - i₅ i₇ → s₅

Table 2: The description follows the same rule as the one for Table 1. Note that ifi4is not in s4,i5

wishes for a vacant at that school. Hence ifi₅enters s₆at some weaklyβstable matching,i₄must enters₄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₁, ...,i₉}, S = {s₁, ...,s₆}, q_s1 = 2,q_s2 = q_s3 = q_s4 = q_s5 = q_s6 = 1, B = {(i₂,i₃),(i₅,i₃),(i₆,i₃),(i₆,i₇)}(Vi(B) = {i₃,i₇}), and preferences and school priorities are such that:

≻_i1 : s1,s2,s6,∅ ≻_s1 :i7,i6,i3,i2,i5,i1,i4,∅

≻_i2 : s₁,s₃,∅ ≻_s2 :i₁,i₃,i₄,∅

≻_i3 : s₂,s₁,s₅,∅ ≻_s3 :i₂,i₆,i₈,∅

≻_i4 : s1,s2,s4,∅ ≻_s4 :i4,i5,i8,∅

≻_i5 : s₄,s₁,∅ ≻_s5 :i₃,i₇,∅

≻_i6 : s₃,s₁,∅ ≻_s6 :i₁,i₉,∅

≻_i7 : s5,s1,∅

≻_i8 : s₃,s₄,∅

≻_i9 : s₆,∅

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 ≻_i1,≻_i9, and≻_s6. Sincei7 ∈Vi(B), she must be enrolled in s5 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♠becausei₃ ∈Vi(B) andi₁ < Vi(B). There is thus a unique weakly γstable

ドキュメント内 Anti bullying 最近の更新履歴 yyasuda's website (ページ 35-50)