In [2]:
using MyMatching
とりあえず多対一、一対一のテストに通るかを試してみる。
In [3]:
Pkg.test("MyMatching")
通った。
多対多はランダムな選好表を生成する関数で例を用いてテストしてみた。
In [4]:
using MatchingMarkets
In [5]:
function mat2vecs{T<:Integer}(prefs::Matrix{T})
return [prefs[1:findfirst(prefs[:, j], 0)-1, j] for j in 1:size(prefs, 2)]
end
Out[5]:
In [4]:
prop_prefs, resp_prefs = mat2vecs.(random_prefs(5, 3, allow_unmatched = false))
Out[4]:
(Array{Int64,1}[[2, 1, 3], [3, 1, 2], [1, 3, 2], [1, 3, 2], [1, 2, 3]], Array{Int64,1}[[1, 3, 2, 5, 4], [5, 1, 3, 2, 4], [3, 5, 2, 4, 1]])
In [5]:
p_caps = [1, 1, 1, 2, 2]
r_caps = [2, 2, 3];
In [6]:
my_deferred_acceptance(prop_prefs, resp_prefs, p_caps, r_caps)
Out[6]:
([2, 3, 1, 3, 0, 1, 2], [5, 3, 5, 1, 0, 4, 2], [1, 2, 3, 4, 6, 8], [1, 3, 5, 8])受入側の枠が提案側の枠の分だけあっても選好次第でマッチングが成立しない。
In [7]:
prop_prefs, resp_prefs = mat2vecs.(random_prefs(5, 3, allow_unmatched = false))
Out[7]:
(Array{Int64,1}[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 1, 3], [2, 1, 3]], Array{Int64,1}[[2, 1, 5, 4, 3], [4, 2, 1, 5, 3], [3, 2, 4, 1, 5]])
In [8]:
p_caps = [1, 1, 1, 2, 2]
r_caps = [2, 2, 3];
In [9]:
my_deferred_acceptance(prop_prefs, resp_prefs, p_caps, r_caps)
Out[9]:
([1, 1, 3, 2, 3, 2, 3], [2, 1, 4, 5, 5, 4, 3], [1, 2, 3, 4, 6, 8], [1, 3, 5, 8])In [10]:
prop_prefs, resp_prefs = mat2vecs.(random_prefs(7, 4))
Out[10]:
(Array{Int64,1}[[4, 3], [2, 3, 4, 1], [3, 1], [1], [1, 3], [4, 3, 1], [1, 2, 3]], Array{Int64,1}[[6, 2, 5, 4, 1], [3, 6, 5, 2, 7, 1, 4], [2, 3], [5, 3]])
In [11]:
p_caps = [1, 1, 2, 1, 1, 2, 1]
r_caps = [3, 3, 1, 2];
In [12]:
my_deferred_acceptance(prop_prefs, resp_prefs, p_caps, r_caps)
Out[12]:
([0, 2, 3, 0, 1, 1, 1, 0, 2], [6, 5, 4, 0, 7, 2, 3, 0, 0], [1, 2, 3, 5, 6, 7, 9, 10], [1, 4, 7, 8, 10])いずれも望ましい結果が得られた。
以下ではランダムな選好表を生成する関数で生成された選好表に対して、受入側が真の選好とは異なる「ウソのリスト」を示した時、その人が得をするマッチング結果を得られるかを調べたい。
ここでは提案側と受入側が一対一のマッチングという状況を仮定する。
受入側の一人一人が実際に「ウソのリスト」を示した時に得られるマッチング結果が当人にとってより望ましいものになるかを逐一調べる関数を作る。
この関数には提案側の人数、受入側の人数、ランダムな選好表を生成する回数を入力することで、「ウソのリスト」を示した時に得られるマッチング結果が当人にとってより望ましいものになったときの全員の真の選好表、得をした人、その人の真の選好表、真の選好表でマッチングした相手、「ウソのリスト」、「ウソのリスト」を示した結果マッチングした相手を列挙する。また、提案側と受入側を入れ替えたときに受入側のマッチング結果が変わる確率と受入側が「ウソのリスト」を示すことで得をする確率(受入側が自分の選好表の情報しか持っておらず、一人一人がランダムに「ウソのリスト」を示した総回数に対して、得をする結果が得られた総回数で表現する)を出力する。
ここではまず、受入側全体が「ウソのリスト」を示す誘因があるかどうかを吟味するために提案側と受入側を入れ替えたときに受入側のマッチング結果が変わるかを調べる。
そして、受入側各個人に対して①真の選好リストでのマッチング結果に不満があるか(選好リストで一番の人とマッチングできていない状況)②マッチングの過程で(受入、拒否どちらも含めて)提案された回数が複数回あるか調べることで「ウソのリスト」でマッチングさせる試行回数を絞っている。
「ウソのリスト」(false_prefs)を生成する関数には、順列を列挙するパッケージ(Combinatorics.jl)を用いている。
In [6]:
function strategic_pref(m_num::Int,
f_num::Int,
num_trials::Int,
print_option::Bool)
no_opt_count = 0
benefit_count = 0
for k in 1:num_trials
m_prefs, f_prefs = mat2vecs.(random_prefs(m_num, f_num, allow_unmatched = false))
#p_countは受入側が真の選好リストのマッチングの過程で提案された回数（受入、拒否どちらも含む）
m_matched, f_matched, p_count = my_deferred_acceptance(m_prefs, f_prefs)
f_matched2, m_matched2, p_count2 = my_deferred_acceptance(f_prefs, m_prefs)
if f_matched != f_matched2 #「ウソのリスト」を示す誘因を持つ
no_opt_count+=1
#「ウソのリスト」を示すことでより望ましい結果を得るための受入側個人の必要条件
f_require = zeros(Int64, f_num)
for i in 1:f_num
if f_matched[i] == f_prefs[i][1] #選好リストで一番の人とマッチングしているか
f_require[i] = 1
end
if p_count[i] <= 1 #マッチングの過程で(受入、拒否どちらも含めて)提案された回数が複数回あるか
f_require[i] = 1
end
end
for i in 1:f_num
if f_require[i] == 0
f_new_prefs = copy(f_prefs)
false_prefs = collect(permutations(collect(1:1:m_num)))
for l in 1:length(false_prefs)
f_new_prefs[i] = false_prefs[l] #「ウソのリスト」一つ一つに対してマッチング結果がどう変わるか
m_new_matched, f_new_matched = my_deferred_acceptance(m_prefs, f_new_prefs)
if findfirst(f_prefs[i], f_new_matched[i]) < findfirst(f_prefs[i], f_matched[i])
benefit_count+=1
if print_option == true
print(m_prefs, f_prefs, i, f_prefs[i], f_matched[i], false_prefs[l], f_new_matched[i], "// ")
end
end
end
end
end
end
end
return no_opt_count/num_trials, benefit_count/((factorial(m_num)-1) * f_num * num_trials)
end
Out[6]:
In [7]:
function strategic_pref2(m_num::Int,
f_num::Int,
num_trials::Int,
print_option::Bool)
no_opt_count = 0
benefit_count = 0
total_list = 0
for i in m_num
total_list+=factorial(i)
end
for k in 1:num_trials
m_prefs, f_prefs = mat2vecs.(random_prefs(m_num, f_num))
#p_countは受入側が真の選好リストのマッチングの過程で提案された回数（受入、拒否どちらも含む）
m_matched, f_matched, p_count = my_deferred_acceptance(m_prefs, f_prefs)
f_matched2, m_matched2, p_count2 = my_deferred_acceptance(f_prefs, m_prefs)
if f_matched != f_matched2 #「ウソのリスト」を示す誘因を持つ
no_opt_count+=1
#「ウソのリスト」を示すことでより望ましい結果を得るための受入側個人の必要条件
f_require = zeros(Int64, f_num)
for i in 1:f_num
if f_matched[i] == f_prefs[i][1]#選好リストで一番の人とマッチングしているか
f_require[i] = 1
end
if p_count[i] <= 1 #マッチングの過程で(受入、拒否どちらも含めて)提案された回数が複数回あるか
f_require[i] = 1
end
end
for i in 1:f_num
if f_require[i] == 0
f_new_prefs = copy(f_prefs)
for j in 1:m_num
false_prefs = collect(permutations(collect(1:1:m_num), j))
for l in 1:length(false_prefs)
f_new_prefs[i] = false_prefs[l] #「ウソのリスト」一つ一つに対してマッチング結果がどう変わるか
m_new_matched, f_new_matched = my_deferred_acceptance(m_prefs, f_new_prefs)
if 0 < findfirst(f_prefs[i], f_new_matched[i]) < findfirst(f_prefs[i], f_matched[i])
benefit_count+=1
if print_option == true
print(m_prefs, f_prefs, i, f_prefs[i], f_matched[i], false_prefs[l], f_new_matched[i], "// ")
end
end
end
end
end
end
end
end
return no_opt_count/num_trials, benefit_count/((total_list- 1) * f_num * num_trials)
end
Out[7]:
false_prefsは[0, 1, 2, ... , m]を並び替えたときの0より手前の順列を全て列挙することで「ウソのリスト」全てを吟味している。
例えばm = 4, j = 2の時、
In [24]: collect(permutations(collect(1:1:4), 2))
Out[24]: 12-element Array{Array{Int64,1},1}: [1, 2] [1, 3] [1, 4] [2, 1] [2, 3] [2, 4] [3, 1] [3, 2] [3, 4] [4, 1] [4, 2] [4, 3]
によって、0より手前に二人いるときの「ウソのリスト」全てを列挙できる。
In [8]:
using Combinatorics
In [9]:
strategic_pref(4, 4, 50, true)
Out[9]:
In [10]:
strategic_pref(4, 4, 10000, false)
Out[10]:
提案側と受入側を入れ替えたときに受入側のマッチング結果が変わる確率:40.7%
受入側が「ウソのリスト」を示すことで得をする確率:0.290%
In [11]:
strategic_pref2(4, 4, 50, true)
Out[11]:
In [12]:
strategic_pref2(4, 4, 10000, false)
Out[12]:
提案側と受入側を入れ替えたときに受入側のマッチング結果が変わる確率:2.35%
受入側が「ウソのリスト」を示すことで得をする確率:0.234%
In [13]:
strategic_pref(6, 6, 10000, false)
Out[13]:
提案側と受入側を入れ替えたときに受入側のマッチング結果が変わる確率:60.3%
受入側が「ウソのリスト」を示すことで得をする確率:0.461%
In [14]:
strategic_pref2(6, 6, 10000, false)
Out[14]:
提案側と受入側を入れ替えたときに受入側のマッチング結果が変わる確率:3.94%
受入側が「ウソのリスト」を示すことで得をする確率:0.329%