Boston mechansim は過去にボストンのパブリックスクールの入試の際に活用されていたアルゴリズムで、その中身は以下のようなものになります。
DAアルゴリズムと同様に、学生側の選好、学校側の選好、学校の定員を入力したうえで、
ステップ１：ステップ1では学生の選好のうち、1番高いもののみが考慮される。学校側はそれらの申し込みを選好の高い順に、定員を超えないように合格とする。この時点でマッチしたペアはマッチ確定。
ステップk：ステップkでは学生の選好のうち、k番目に高いもののみ考慮される。学校側はこれまでに合格とした生徒が定員に達していなければ、自らをk番目に希望した生徒を選好に応じて、定員がオーバーしないようにとる
このステップを全ての生徒が学校とマッチするまで、もしくは学校とマッチしていない生徒の選好リストの校数の最大値が反復回数となるまで続けます
In [1]:
using MyMatching
ソースコードはこちら
医師臨床研修マッチング協議会の例で比較してみます
In [2]:
prop_prefs = [[2], [2, 1], [2, 1], [1, 2, 3, 4], [2, 1, 4, 3], [2, 3, 1, 4], [2, 1, 4, 3], [4, 2, 1, 3]]
resp_prefs = [[3, 7], [7, 8, 5, 1, 2, 3, 4, 6], [2, 5, 8, 1, 3, 4, 7], [2, 5, 1, 3, 6, 4, 7]]
caps = [2, 2, 2, 2];
In [3]:
my_deferred_acceptance(prop_prefs, resp_prefs, caps)
Out[3]:
In [4]:
my_Boston_school_match(prop_prefs, resp_prefs, caps)
Out[4]:
Boston mechanism の結果では、学校2は生徒5とマッチするのではなく生徒8とマッチしたほうが、学校2も生徒8もより効用が高くなります
したがって、Boston mechanism はDAアルゴリズムとは異なり、必ずしも stable なマッチング結果をもたらしません
Boston mechanism では、選好の順番が重要な役割を果たします。したがって、嘘の選好を提出することで得をすることができます
嘘の選好を提出することで、どれだけ得になるか、DAアルゴリズムと比較しながら、調べていきます
まず全ての学生が真の選好を表明したときに、どうなるかやってみます
In [5]:
real_prop_prefs = fill([1, 2, 3], 90)
prop_points = sort!(randn(90), rev = true)
resp_prefs = fill(collect(1:90), 3)
caps = [30, 30, 30]
Out[5]:
In [6]:
a, b, c = my_deferred_acceptance(real_prop_prefs, resp_prefs, caps)
Out[6]:
In [7]:
x, y, z = my_Boston_school_match(real_prop_prefs, resp_prefs, caps)
Out[7]:
In [8]:
b == collect(1:90)
Out[8]:
In [9]:
b == y
Out[9]:
この場合どちらのマッチング方法でも、点数の高い生徒から順にマッチングしていきます
それでは今度は、点数が平均点を下回っている生徒が正直に選好を表明せず、[2, 3, 1] という選考を表明するとします
In [10]:
is_higher = prop_points .> mean(prop_points)
findfirst(is_higher, false)
Out[10]:
今回の例だと学生42までは [1, 2, 3] という提出し、学生43以降は [2, 1, 3] と提出するとします
In [14]:
fake_prop_prefs = Array{Array{Int, 1}}(90)
for i in 1:42
fake_prop_prefs[i] = [1, 2, 3]
end
for i in 43:90
fake_prop_prefs[i] = [2, 3, 1]
end
In [15]:
a1, b1, c1 = my_deferred_acceptance(fake_prop_prefs, resp_prefs, caps)
Out[15]:
In [16]:
b1 == b
Out[16]:
この例においては、DAアルゴリズムを用いる場合、マッチングの結果は変化しません
In [17]:
x1, y1, z1 = my_Boston_school_match(fake_prop_prefs, resp_prefs, caps)
Out[17]:
In [18]:
y1 == y
Out[18]:
Boston mechanism では結果に変化がありました
嘘の選好を表明することで、得をした人がどれだけいるか確認します
In [19]:
sum(x[43:90] .== 2)
Out[19]:
In [21]:
sum(x[43:90] .== 3)
Out[21]:
In [22]:
sum(x1[43:90] .== 2)
Out[22]:
In [23]:
sum(x1[43:90] .== 3)
Out[23]:
以上から嘘の選好を表明することで、得をした人が12人いることがわかります
正直に選好を表明した人がどうなったかも確認します
In [24]:
sum(x[1:42] .== 1)
Out[24]:
In [25]:
sum(x[1:42] .== 2)
Out[25]:
In [26]:
sum(x1[1:42] .== 1)
Out[26]:
In [27]:
sum(x1[1:42] .== 2)
Out[27]:
In [28]:
sum(x1[1:42] .== 3)
Out[28]:
嘘をつくことで得をした人数分だけ、損をした人がいることが確認できます
A.Abdulkadiroglu, P.Pathak, A.Roth and T.Sonmez (2006). "Changing the Boston School Choice Mechanism: Strategy-proofness as Equal Access"
In [ ]: