# A PPENDIX [NOT FOR PUBLICATION]

In document Anti bullying 最近の更新履歴 yyasuda's website (Page 35-50)

ROOF OF

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 sS,|µ(s)|<qsif and only if|µ(s)|˜ <qs, and in this case,µ(s)= µ(s).˜

Proof of Theorem 1

Quasi Stability: Let µ ≡ ϕT GS(≻I,B). If there exist iI and sS such that si µ(i) and

|µ(s)|<qs, theniBu(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, jI such that µ(j)i µ(i) and iµ(j) j. By its construction of µ, iBu(B) (otherwisei was rejected byµ(j) at Round 1). If jBu(B), µ(j) acceptsi’s victim at Round 1 (otherwise i was rejected by µ(j) at Round 2). Hence, if ihas justified envy toward j, iBu(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 µ1 denote a matching such that µ1(i) = µ(i) for all i < Bu(B), and µ1(i) = i for all iBu(B). We define ˜µ1 in the same way. Consider a preference profile of bullies such that ii s for all sS and for all iBu(B). By assumption, ˜µ1 dominates µ1. Sinceµ1is 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 sS, or (ii) has justified envy toward another student j < Bu(B) (i.e., ˜µ1(j)i µ˜1(i) andiµ˜1(j) j). Suppose the first possibility holds. By Lemma 1, ifsS has a vacant seat at ˜µ1, it also has a vacant seat atµ1. Sincesi µ˜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(j)is true for the same reason we discussed above. Since|µ˜1( ˜µ1(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: ˜IBu(B). Let µ2 denote a matching such that µ2(i) = µ(i) for all iBu(B) and µ2(i) = i for alli < Bu(B). We define ˜µ2 in the same way. Consider the following modification of the preference profile of students and school capacities: for all iBu(B), if sS accepts her victim atµ1(= µ˜1), she lowers the preference ranking of sbelow her outside option; for each i< Bu(B),ii sfor all sS; each schoolsS reduces its capacity by|µ1(s)|(=|˜µ1(s)|). Thenµ2 is a student-optimal stable matching and ˜µ2dominatesµ2. SupposeiBu(B) wishes for a vacant seat ofsS at ˜µ2. By Lemma 1,salso leaves the seat vacant and does not accept any victims of iat ˜µ. This contradicts the quasi stability of ˜µ. Next, supposeiBu(B) has justified envy toward jBu(B) at ˜µ2. Since ˜µ2(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: iBu(B). Leti 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 GSj (≻I,B) below her outside option. Since the GS mechanism is strategy-proof, ϕT GSi (≻I,B) i ϕT GSi (≻I,B). By the construction of preferences, ϕT GSi (≻I,B) i i. Note that for all s,sS ∪ {i}such that s,s i i, s i s impliessi s. Hence we haveϕT GSi (≻I,B)i ϕT GSi (≻I,B).

Case 2: i < Bu(B). Consider the following variations of the bullies’ preferences: for each kBu(B), k ≻˜k s for all sS, and ˜≻i places only her assignment ϕT GSi ( ˜≻Bu(B),≻−Bu(B),B) above her outside option (if ϕT GSi ( ˜≻Bu(B),≻−Bu(B),B) = i, then all the schools in S move be-low her outside option). Then ϕT GSi ( ˜≻Bu(B),≻−Bu(B),B) = ϕT GSi ( ˜≻Bu(B),≻−Bu(B),B). Since the GS mechanism is strategy-proof, ϕT GSi ( ˜≻Bu(B),≻−Bu(B),B) i ϕT GSi ( ˜≻Bu(B),≻−Bu(B),B), which implies ϕT GSi ( ˜≻Bu(B),≻−Bu(B),B)i ϕT GSi ( ˜≻Bu(B),≻−Bu(B),B). By the assumptioni<Bu(B),ϕT GSi ( ˜≻Bu(B),≻−Bu(B) ,B)T GSi (≻I,B). SinceϕT GSi ( ˜≻Bu(B),≻−Bu(B),B)i ϕT GSi (≻I,B), we conclude thatϕT GSi (≻I,B)i

ϕT GSi (≻I,B). This completes the proof. Q.E.D.

ROOF OF

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µ. LetiIbe 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˜ sS. Then, µis equivalent to ϕT T C(≻µi,≻−i,B) for anyiI.

(∵ LetC1,C2, ...,Cn, ...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 inCn. Hence whatever preferences ireports, we can removeC1,C2, ...,Cn−1 in the firstn−1 steps. Now supposeireports≻µi. After removingC1, ...,Cn−1, we can immediately removeCn, followed byCn+1,Cn+2, ...which results inµ.)

Suppose ϕT T Ci ( ˜≻I˜,≻I˜,B) i µ(i) holds for all iI. Let ˜˜ µ denote ϕT T C( ˜≻I˜,≻−˜I,B). By the previous discussion, ϕT T C(≻µ˜˜

I,≻I˜,B) = µ. Let˜ C1,C2, ... 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 cyclesC1, ...,Ct−1 in the same order under (≻µ˜˜

I,≻I˜,B) and there is a student inCt who is a member of ˜I(indeed, ifCt is the first cycle where a nonempty subset of ˜Iis involved, it is possible to removeC1,C2, ...,Ct−1 in the first t− 1 steps no matter what profile of preferences ˜I reports).

There are two cases to consider.

Case 1: Ct is a singleton comprising one studenti. By the construction of the TTC algorithm, after removingC1, ...,Ct−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 sS, meaning thatCt can be removed immediately after C1, ...,Ct−1 even under the preference profile (≻µ˜˜

I,≻−˜I).

Case 2: Ct 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 sS \ {µ(i)}.

As in the previous case, therefore,Ct can be removed immediately afterC1, ...,Ct−1even under the preference profile (≻µ˜˜

I,≻I˜).

To summarize, it is possible to removeC1,C2, ...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.

ROOF OF

HEOREM

### 3

Proof. Consider a problem where I = {i1, ...,i6}, S = {s1,s2,s3,s4},qs1 = qs2 = qs3 = 1, qs4 = 2, B= ∅, and preferences are given by

i1,≻i2 : s4,s1,∅

i3,≻i4 : s4,s2,∅

i5,≻i6 : s4,s3,∅.

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 = {(i2,i1),(i4,i1),(i6,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 i5 enters s4, which induces a transfer of i4 or i6 to s2 or s3. This contradicts the group bullying-resistance property.

Consider the following possible outcome of a mechanism

µ =







s1 s2 s3 s4i2 i4 i5 i1i3 i6







 .

IfBis replaced byB′′ ={(i2,i1),(i3,i1),(i4,i1),(i6,i1)},i1ori3must leaves4. By the group bullying-resistance property,s4does not accepti2,i4,nori6. By constrained Pareto efficiency,i5andi6enter s4 and s3 respectively, which contradicts the group bullying-resistance property. This completes

the proof. Q.E.D.

ROOF OF

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 ={(i2,i1),(i4,i1),(i6,i1)}, there is at least one student in{i2,i4,i6}who gets better off. This is a contradiction. Q.E.D.

ROOF OF

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 ˜IBu(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 I2Bu(B) = ∅, then by the responsiveness condition, for any student jin I˜\Bu(B),{i} ≻s {j}. This again contradicts stability. Finally ifiBu(B) and ˜IBu(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. HenceiBu(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: ∀iI \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 sS,|µ(s)˜ \Bu(B)|< qs ⇔ |µ(s)\Bu(B)|< qs 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)|= qsandµ(s)≻s µ(s). This contradicts the assumption that˜

µ˜ dominatesµ. Q.E.D.

ROOF OF

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)| < qs, there is (i, j)B such that iI1 and jI2, confirming the statement of the proposition. Suppose instead that |µ(s)| = qs and I2 , ∅. If I1Bu(B)= ∅, by the responsiveness condition, there is at least one studentiinI1and one student j in I2 such that i, j < Bu(B), si µ(i), and {i} ≻s {j} ≻s ∅. This contradicts stability among non-bullies. HenceI1Bu(B),∅. SinceI2Bu(B)=∅holds by assumption,I2\Bu(B), ∅and

|I1Bu(B)|>0=|I2Bu(B)|.

Case 2: µ(s)∩Bu(B) , ∅. IfI1\Bu(B) , ∅, there areiI1\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. HenceI1Bu(B).

Suppose there is no (i, j)B such that iI1 and jI2 (otherwise, the statement of the proposition is immediately confirmed). By the definition of a blocking group, there is no (i, j)B such that iI1 and j ∈ µ(s). Hence for all iI1, 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)|= qsand for alliI1and all j ∈µ(s)∩Bu(B),{j} ≻s {i}. Hence, I2\Bu(B) , ∅ since otherwise|I1| ≤ |I2|(by|µ(s)|=qs),{j} ≻s{i}for all jI2 andiI1, and the responsiveness condition together imply µ(s) ≻s (µ(s)\ I2)∪ I1, which contradicts the definition of a blocking group. Moreover, if|I2Bu(B)| ≥ |I1Bu(B)|=|I1|, then

µ(s) ≻s µ(s)\(I2\Bu(B))

s (((µ(s)\(I2\Bu(B)))\(I2Bu(B)))I1= (µ(s)\I2)∪I1.

Thusµ(s)≻s(µ(s)\I2)∪I1, a contradiction. Hence|I1Bu(B)|> |I2Bu(B)|. Q.E.D.

TRONG

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 iBu(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{i1,i2,i3,i4}. The school capacities and a set of bullying incidents are given byqs1 = 2,qs2 =1, B= {(i1,i2),(i1,i3),(i4,i3)}. The student and school preferences are such that:

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

i2 : s1,s2,∅ ≻s2 :{i2},{i3},∅

i3 : s2,s1,∅

i4 : s1,∅

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

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







s1 s2i2i3 i1i4







 , µ2 =







s1 s2i1i4 i2 i3







 , µ3=







s1 s2i1i4 i3 i2







 , µ4=







s1 s2i2i4 i3 i1







 .

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

µ2: (i3,s1),µ3: (i2,s2),µ4: (i1,s1)). ^

Example 6(No mechanism that is strategy-proof selects a strongly quasi stable matching whenever there exists one). There are two schools{s1,s2}and five students{i1, ...,i5}. The school capacities and the set of bullying incidents are given by qs1 = 2,qs2 = 1, B = {(i1,i3),(i2,i3),(i4,i5)}. The student and school preferences are:

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

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

i3 :s1,s2,∅

i4 :s1,∅

i5 :∅

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

µ=







s1 s2i1i2 i3 i4i5







, and µ˜ =







s1 s2i3i4 i2 i1i5







 .

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 ofi3:

i

3:s1,∅.

Then, ˜µis the unique strongly quasi stable matching under (≻i

3,≻{i1,i2}). Sincei3 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 ofi1:

i

1:s1,s2,∅.

Then,µis the unique strongly quasi stable matching under (≻i

1,≻{i2,i3}). Note that ifi2is 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 i1 prefers s1 to her outside option according to her true preferences ≻i1, she prefersµ(i1) to ˜µ(i1), meaning that she can profitably misreport her preferences under≻I. ^

THER

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,iBu(B) and jVi(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 jVi(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 (ivw) (wheneveriwishes for a vacant seat at some school,iBu(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 = {i1, ...,i8},S = {s1, ...,s5},qs1 = 2,qs2 = qs3 = qs4 = qs5 = 1, B = {(i2,i3),(i5,i3),(i6,i3),(i6,i7)} (Bu(B) = {i2,i5,i6} and Vi(B) = {i3,i7}), and preferences and school priorities are such that:

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

i2 : s1,s3,∅ ≻s2 :i1,i3,i4,∅

i3 : s2,s1,s5,∅ ≻s3 :i2,i6,i8,∅

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

i5 : s4,s1,∅ ≻s5 :i3,i7,∅

i6 : s3,s1,∅

i7 : s5,s1,∅

i8 : s3,s4,∅

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,i3has justified envy towardi7andi3,i7Vi(B), meaning that it is not weaklyβstable.

Next, suppose thati7is enrolled in s1. Then,i3 needs to enter s5since otherwise i7wishes for a vacant seat at s5. To avoid the case wherei3 wishes for a vacant seat at s1 or has justified envy towardi7’s buddy,s1 needs to admiti6. However, (i6,i7)∈ Brequests the separation ofi7fromi6. Hence, ifi7is in s1, the resulting matching is by no means weaklyβstable.

Finally, if i7 is not enrolled in any school, she would wish for a vacant seat at s1, or have

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

completes the proof. Q.E.D.

s1 s2 s3 s4 Remark

∅∅ - - - i1s1

i∅ - - - i4s1(i, i4) i4∅ - - - i1s1 i1i2 i3 - i5 i4s4(i5) i1i2 i4 - i5 i3s2(i4) i1i3 - - - i3s2 i1i4 - - - i2s1(i1) i1i5 - - - i2s1(i1) i1i6 - - - i2s1(i1) i2i4 - - - i1s1(i4) i2i5 - i6i8s4 i2i5 - i6 i8 i5s4(i8) i2i5i6 i4 i4s2

i2i5 i3 i6 i4 i1s2(i3)♠ i2i5 i1 i6 i4i2i6 - ∅ - i8s3

i2i6 - i8 - i6s3(i8) i3i4 - - - i1s1(i4) i4i5 - - - i1s1(i4) i4i6 - - - i1s1(i4) i5i6 - - - i2s1(i5)

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, “is(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 ins1.

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}, qs1 = 2,qs2 = 1,B={(i1,i3),(i1,i4),(i2,i3)}(Bu(B)= {i1,i2}), and preferences and school priorities are such that:

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

i2 : s2,s1,∅ ≻s2 :i3,i1,i2,i4,∅

i3 : s1,s2,∅

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 s2i1i2 i3 i4







, and µ˜ =







s1 s2i3i4 i2 i1







 .

Suppose that a mechanism choosesµunder the above preference profile≻I. Consider the following reported preference ordering≻i

3 ofi3,

i

3:s1,∅.

Then, ˜µis the unique weakly stable matching under (≻i

3,≻{i1,i2,i4}). Sincei3 prefers ˜µ(i3) to µ(i3), 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 ofi1,

i

1:s1,s2,∅.

Then, µ is the unique stable matching under (≻i

1,≻{i2,i3,i4}). Since i1 prefers s1 to her outside op-tion according to her true preferences ≻i1, she prefers µ(i1) to ˜µ(i1), 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 = {i1, ...,i9}, S = {s1, ...,s6},

qs1 = 2,qs2 = qs3 = qs4 = qs5 = qs6 = 1, B = {(i2,i3),(i5,i3),(i6,i3),(i6,i7)}(Bu(B)= {i2,i5,i6}and Vi(B)={i3,i7}), and preferences and school priorities are such that:

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

i2 : s1,s3,∅ ≻s2 :i1,i3,i4,∅

i3 : s2,s1,s3,∅ ≻s3 :i2,i6,i9,i3,i8,∅

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

i5 : s4,s1,∅ ≻s5 :i3,i7,∅

i6 : s3,s1,∅ ≻s6 :i5,i9,∅

i7 : s5,s1,∅

i8 : s3,s4,∅

i9 : s6,s3,∅

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. Sincei3i3 s5 andi5i5 s6, i7 and i9 enter s5 and s6 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 s3i3 i3, there is another weakly βstable matching in whichi3 enterss3. In sum, there are two weaklyβstable matchings in this problem:

µ=







s1 s2 s3 s4 s5 s6i2i5 i1 i6 i4 i7 i9 i3i8







, and µ˜ =







s1 s2 s3 s4 s5 s6i2i6 i1 i3 i4 i7 i9 i5i8







 .

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 ofi3,

i

3:s2,s1,s3,s5,∅.

Then, ˜µis the unique weaklyβstable matching under (≻i

3,≻I\{i3}). To see this is true, suppose that i3enterss5. Then,i7is ins1and, to avoid the case wherei3wishes for a vacant seat ats1or she has justified envy towardi7’s buddy,i6has to be in s1. But this is incompatible with (i6,i7)∈B. Hence at any weaklyβstable matching,i3does not enters5, 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 ofi5:

i

5:s4,s1,s6,∅.

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; i6 has justified envy towardi3 at ˜µ, but (i6,i3) ∈ B).

Moreover, ˜µisαstable under (≻i

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

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

s1 s2 s3 s4 s5 s6 Remark

∅∅ - - i4 - i5 i4s1

i∅ - - i4 - i5 i4s1(i: arbitrary) i1i2 - - i4 - i5 i5s1(i1) i1i3 - - i4 - i5 i3s2

i1i6 - - i4 - i5 i2s1(i1) i2i6 - ∅ i4 - i5 i3s3 i2i6 - i3 i4 - i5 i9s3(i3) i2i6 - i8 i4 - i5 i9s3(i8) i2i6 - i9 i4 - i5 i6s3(i9) i2i7 - - i4 - i5 i7s5

i3i7 - - i4 - i5 i7s5

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 ifi5enters s6at some weaklyβstable matching,i4must enters4at 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 = {i1, ...,i9}, S = {s1, ...,s6}, qs1 = 2,qs2 = qs3 = qs4 = qs5 = qs6 = 1, B = {(i2,i3),(i5,i3),(i6,i3),(i6,i7)}(Vi(B) = {i3,i7}), and preferences and school priorities are such that:

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

i2 : s1,s3,∅ ≻s2 :i1,i3,i4,∅

i3 : s2,s1,s5,∅ ≻s3 :i2,i6,i8,∅

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

i5 : s4,s1,∅ ≻s5 :i3,i7,∅

i6 : s3,s1,∅ ≻s6 :i1,i9,∅

i7 : s5,s1,∅

i8 : s3,s4,∅

i9 : s6,∅

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. Sincei7Vi(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♠becausei3Vi(B) andi1 < Vi(B). There is thus a unique weakly γstable

In document Anti bullying 最近の更新履歴 yyasuda's website (Page 35-50)