小住真央のデモノートです。
このノートブックでは、受け入れ側にとって最も望ましい定員数が何通り考えられるかを調べている。
手順は以下の通りである。
定員を設けなかった場合のマッチングを調べる。その結果から受け入れ側にとって利得を生まない学生を除外する。
(1)の結果から、受け入れ側にとって利得を生まない学生を除外し、そのときの定員数を導出する。
(2)から導出した定員数から、各学科が１人定員を増やした場合の利得の増分を求め、比較する。
最も利得の増分が多い学科の定員を1人増やす。
(3)(4)の操作を繰り返し、最適な定員数を導出する。
In [1]:
using MyMatching
今回は学生の人数を前回の300人から1500人に増やして試行を行う。
In [2]:
using ShingakuMatching
departments = get_departments()
num_students = 1500
students = get_students(num_students)
prop_prefs, resp_prefs, caps = get_random_prefs(students, departments)
Out[2]:
以下では、学科にとって最適な定員数を考える。
学生の内定により発生する学科の利得は、次のように定める。Shingakumatchingでは、学生の志望する学科の選好リストにその学生が必ず含まれるため、選好リスト内には必ずしも学科の利得を上昇させない学生が含まれていると考えられる。
ここから、当該学生が学科の選好リストの下位50パーセントに属す場合、学科の利得は0とみなすこととする。
それ以外の場合は、1/2 ×（学生全体の人数）ー（学生に対する学科の選好順位）の大きさで決まるものとする。
まず、学科が定員を設けない場合のマッチングを考える。
In [3]:
limitless_caps = Vector{Int}(length(caps))
limitless_caps[1:end] = num_students
Out[3]:
In [4]:
limitless_prop_matched, limitless_resp_matched, limitless_indptr = my_deferred_acceptance(prop_prefs, resp_prefs, limitless_caps)
Out[4]:
まず、定員を設けなかった場合の学科側のマッチング結果(limitless_resp_matched)から、学科にとって利得が0の学生を排除し、各学科の利得が損なわれないように定員数を削減する。
以下の関数を用いる。
In [5]:
function decrease_caps(caps,resp_matched,resp_prefs,indptr)
decreased_caps = copy(caps)
function student_resp_rank(resp_number)
w = resp_matched[indptr[resp_number]:indptr[resp_number+1]-1]
st_ranking = Array{Int}(length(w),2)
st_ranking[1:end] = 0
y = 1
while y <= caps[resp_number]
if !(w[y] == 0)
resp_rank = 1
pref = resp_prefs[resp_number]
while !(pref[resp_rank] == w[y])
resp_rank += 1
end
st_ranking[y,1] = resp_rank
st_ranking[y,2] = w[y]
else
break
end
y += 1
end
return st_ranking
end
resp_number = 1
while resp_number <= length(caps)
st_ranking = student_resp_rank(resp_number)
i = 1
while i <= length(st_ranking[:,2])
if !(st_ranking[i,1] <= (1/2 * length(resp_prefs[resp_number]))) || (st_ranking[i,1] == 0)
decreased_caps[resp_number] -= 1
end
i += 1
end
resp_number += 1
end
return decreased_caps
end
Out[5]:
In [6]:
decreased_caps = decrease_caps(limitless_caps,limitless_resp_matched,resp_prefs,limitless_indptr)
Out[6]:
実際にこの定員数を用いてマッチングを行う
In [7]:
decreased_prop_matched, decreased_resp_matched, decreased_indptr = my_deferred_acceptance(prop_prefs, resp_prefs, decreased_caps)
Out[7]:
以下では、学科にとって、decreased_capsから定員数を増やす誘因があるかを調べる。
ある学科の定員数を増やした際に、その学科への移動を希望する学生と、その学生に対する学科の選好順位のリストを作成する関数を以下のように設定する。
In [8]:
function trans_ranking(resp_number,prop_matched)
trans_list = Vector{Int}(num_students)
trans_rank = Array{Int}(num_students,2)
trans_list[1:end] = 0
trans_rank[1:end] = 0
k = 1
for x in 1:num_students
if resp_number in prop_prefs[x]
if prop_matched[x] == 0
trans_list[k] = x
k += 1
else
n = 1
m = 1
while !((prop_prefs[x][n]) == prop_matched[x])
n += 1
end
while !((prop_prefs[x][m]) == resp_number)
m += 1
end
if min(m,n) == m
trans_list[k] = x
k += 1
else
continue
end
end
end
end
y = 1
if !(trans_list == []) && !(sum(trans_list) == 0)
while y <= length(trans_list)
if trans_list[y] == 0
break
else
rank = 1
while !((resp_prefs[resp_number][rank]) == trans_list[y])
rank += 1
end
trans_rank[y,2] = rank
trans_rank[y,1]= trans_list[y]
end
y += 1
end
trans_order = view(trans_rank,1:y-1,:)
sort(trans_order,1,rev=false)
else
trans_order = 0
end
return trans_order
end
Out[8]:
trans_orderをもとに、定員を増やすことで学科が得られる利得を計算する関数を以下のように定める。
In [9]:
function increase_caps_benefit(resp_number,trans_order,prop_matched)
z = 1
delta_benefit = [0]
if !(trans_order == 0)
while ((trans_order[z,1]) <= (1/2 * length(resp_prefs[resp_number]))) && !(trans_order[z,1] == trans_order[end,1])
push!(delta_benefit, (1/2 * num_students) - (trans_order[z,1]))
z += 1
end
shift!(delta_benefit)
else
delta_benefit = []
end
return delta_benefit
end
Out[9]:
上の二つの関数を利用し、学科にとって最適な定員を求めるため、以下の関数を設定する。
In [10]:
function resp_optimal_caps(caps,prop_matched)
resp_opt_caps = copy(caps)
i = Vector{Int}(length(caps))
i[1:end] = 1
while sum(resp_opt_caps) <= num_students
max_benefit = 0
resp_num = 0
resp_other_num = [0]
resp_number = 1
resp_box = 0
stop = false
while resp_number <= length(caps)
trans_order = trans_ranking(resp_number,prop_matched)
delta_benefit = increase_caps_benefit(resp_number,trans_order,prop_matched)
if delta_benefit[i[resp_number]] <= max_benefit
if delta_benefit[i[resp_number]] == max_benefit
push!(resp_other_num,resp_number)
end
else
max_benefit = delta_benefit[i[resp_number]]
resp_num = resp_number
resp_other_num = [0]
end
resp_number += 1
end
if max_benefit == 0
break
end
resp_opt_caps[resp_num] += 1
i[resp_num] += 1
if !(resp_other_num == [0])
shift!(resp_other_num)
m = 1
while m <= length(resp_other_num)
if !(num_students <= sum(resp_opt_caps))
resp_opt_caps[resp_other_num[m]] += 1
i[resp_other_num[m]] += 1
else
for n in 1:m-1
resp_opt_caps[resp_other_num[n]] -= 1
end
resp_opt_caps[resp_num] -= 1
println("$resp_num and $resp_other_num can increase their caps.")
resp_box = push!(resp_other_num, resp_num)
stop = true
break
end
m += 1
end
end
if stop
break
end
end
if resp_box == 0
resp_box = resp_num
end
return resp_opt_caps,resp_box
end
Out[10]:
実際に、resp_opt_capsを求めてみると、以下のようになる。
In [11]:
resp_opt_caps,resp_box = resp_optimal_caps(decreased_caps,decreased_prop_matched)
Out[11]:
In [12]:
sum(resp_opt_caps)
Out[12]:
In [13]:
length(resp_box)
Out[13]:
以上の結果から、resp_opt_capsからさらに全体で2人定員を増やすことができることがわかる。
resp_boxに含まれる学科であればどの学科の定員を増やしても学科全体の利得の増え方は変わらない。
よって、resp_box内で2つ学科を選ぶような組み合わせを考えれば、最適な定員数が何通り考えられるかがわかる。
In [14]:
using Iterators
In [16]:
c = 0
for i in subsets(resp_box,num_students - sum(resp_opt_caps))
c += 1
end
c
Out[16]:
以上より、今回の試行では、学科全体にとって最適な定員数は3160通り考えられる。
以上で検証を終える。