notebook.community

Edit and run



In [1]:

    
using MyMatching

まずは普通に。Wikipediaの例。



In [2]:

    
# 例-01
prop_prefs = [[1, 2, 3, 4], [3, 2, 1, 4], [1, 2, 4, 3], [3, 1, 4, 2]]
resp_prefs = [[1, 2, 3, 4], [2, 1, 4, 3], [2, 3, 1, 4], [1, 4, 3, 2]]
my_deferred_acceptance(prop_prefs, resp_prefs)









    Out[2]:





([1, 3, 2, 4], [1, 3, 2, 4])

提案を入れ替えてみる。



In [3]:

    
resp_prefs = [[1, 2, 3, 4], [3, 2, 1, 4], [1, 2, 4, 3], [3, 1, 4, 2]]
prop_prefs = [[1, 2, 3, 4], [2, 1, 4, 3], [2, 3, 1, 4], [1, 4, 3, 2]]
my_deferred_acceptance(prop_prefs, resp_prefs)









    Out[3]:





([1, 3, 2, 4], [1, 3, 2, 4])

この例では提案するのを男女入れ替えても一致する。

では、次のような少しいじった例を考える。



In [4]:

    
# 例-02
prop_prefs = [[1, 2, 3, 4], [3, 2, 1, 4], [1, 2, 4, 3], [4, 1, 3, 2]]
resp_prefs = [[1, 2, 3, 4], [2, 1, 4, 3], [3, 2, 1, 4], [1, 4, 3, 2]]
my_deferred_acceptance(prop_prefs, resp_prefs)









    Out[4]:





([1, 3, 2, 4], [1, 3, 2, 4])

提案を入れ替えてみる。



In [5]:

    
resp_prefs = [[1, 2, 3, 4], [3, 2, 1, 4], [1, 2, 4, 3], [4, 1, 3, 2]]
prop_prefs = [[1, 2, 3, 4], [2, 1, 4, 3], [3, 2, 1, 4], [1, 4, 3, 2]]
my_deferred_acceptance(prop_prefs, resp_prefs)









    Out[5]:





([1, 2, 3, 4], [1, 2, 3, 4])

提案を入れ替えると、最適なマッチングが変わる。

つまり、この例では男の立場からすると(1, 3, 2, 4)とマッチングするのが最適だが、女の立場からすると(1, 2, 3, 4)とマッチングするのが最適。

ここで、次のようなことを考えよう。

ある個人について、選好のn番目の人とマッチングした時の不幸度をnとする。但し、マッチングされなかった場合は(選好の長さ)+1とする。

人々の不幸度の合計が最小になるような状態を考えたい。



In [6]:

    
prop_prefs = [[1, 2, 3, 4], [3, 2, 1, 4], [1, 2, 4, 3], [4, 1, 3, 2]]
resp_prefs = [[1, 2, 3, 4], [2, 1, 4, 3], [3, 2, 1, 4], [1, 4, 3, 2]]
prop_matched, resp_matched = my_deferred_acceptance(prop_prefs, resp_prefs)









    Out[6]:





([1, 3, 2, 4], [1, 3, 2, 4])



In [7]:

    
m = length(prop_prefs)
prop_uf = Vector{Int64}(m)

c = 1
while c <= length(prop_prefs)
    if prop_matched[c] == 0
        prop_uf[c] = length(prop_prefs[c])+1
    else
        prop_uf[c] = findfirst(prop_prefs[c], prop_matched[c])
    end
    c += 1
end

prop_uf









    Out[7]:





4-element Array{Int64,1}:
 1
 1
 2
 1



In [8]:

    
n = length(resp_prefs)
resp_uf = Vector{Int64}(n)

d = 1
while d <= length(resp_prefs)
    if resp_matched[d] == 0
        resp_uf[d] = length(resp_prefs[d])+1
    else
        resp_uf[d] = findfirst(resp_prefs[d], resp_matched[d])
    end
    d += 1
end

resp_uf









    Out[8]:





4-element Array{Int64,1}:
 1
 4
 2
 2



In [9]:

    
sum(prop_uf[1:end])









    Out[9]:





5



In [10]:

    
sum(resp_uf[1:end])









    Out[10]:





9

となるから、男側の不幸度の合計は5、女性側の不幸度の合計は9、全体としての不幸度は14である。

一方、提案を入れ替えた場合、



In [11]:

    
resp_prefs = [[1, 2, 3, 4], [3, 2, 1, 4], [1, 2, 4, 3], [4, 1, 3, 2]]
prop_prefs = [[1, 2, 3, 4], [2, 1, 4, 3], [3, 2, 1, 4], [1, 4, 3, 2]]
prop_matched, resp_matched = my_deferred_acceptance(prop_prefs, resp_prefs)









    Out[11]:





([1, 2, 3, 4], [1, 2, 3, 4])



In [12]:

    
m = length(prop_prefs)
prop_uf = Vector{Int64}(m)
n = length(resp_prefs)
resp_uf = Vector{Int64}(n)

c = 1
while c <= length(prop_prefs)
    if prop_matched[c] == 0
        prop_uf[c] = length(prop_prefs[c])+1
    else
        prop_uf[c] = findfirst(prop_prefs[c], prop_matched[c])
    end
    c += 1
end

d = 1
while d <= length(resp_prefs)
    if resp_matched[d] == 0
        resp_uf[d] = length(resp_prefs[d])+1
    else
        resp_uf[d] = findfirst(resp_prefs[d], resp_matched[d])
    end
    d += 1
end



In [13]:

    
sum(prop_uf[1:end])









    Out[13]:





5



In [14]:

    
sum(resp_uf[1:end])









    Out[14]:





8

となり、男側の不幸度の合計は8、女側の不幸度の合計は5、全体としての不幸度は13である。

従って、提案の入れ替えにより、男側の不幸度が増加し女側の不幸度は減少している。

つまり、提案する側にとってのみ最適なマッチングとなっている。

また、社会的によいマッチングを全体としての不幸度が小さい方であるとすると、女側が提案した時の方が社会的によいことになる。

マッチングしない人がいるような例も考えてみる。



In [15]:

    
# 例-03
prop_prefs = [[1, 2, 3], [3, 2, 1], [1, 2, 3], [1, 3, 2]]
resp_prefs = [[1, 2, 3, 4], [2, 1, 3, 4], [3, 2, 1, 4]]
prop_matched, resp_matched = my_deferred_acceptance(prop_prefs, resp_prefs)









    Out[15]:





([1, 3, 2, 0], [1, 3, 2])



In [16]:

    
m = length(prop_prefs)
prop_uf = Vector{Int64}(m)
n = length(resp_prefs)
resp_uf = Vector{Int64}(n)

c = 1
while c <= length(prop_prefs)
    if prop_matched[c] == 0
        prop_uf[c] = length(prop_prefs[c])+1
    else
        prop_uf[c] = findfirst(prop_prefs[c], prop_matched[c])
    end
    c += 1
end

d = 1
while d <= length(resp_prefs)
    if resp_matched[d] == 0
        resp_uf[d] = length(resp_prefs[d])+1
    else
        resp_uf[d] = findfirst(resp_prefs[d], resp_matched[d])
    end
    d += 1
end



In [17]:

    
sum(prop_uf[1:end])









    Out[17]:





8



In [18]:

    
sum(resp_uf[1:end])









    Out[18]:





6



In [19]:

    
resp_prefs = [[1, 2, 3], [3, 2, 1], [1, 2, 3], [1, 3, 2]]
prop_prefs = [[1, 2, 3, 4], [2, 1, 3, 4], [3, 2, 1, 4]]
prop_matched, resp_matched = my_deferred_acceptance(prop_prefs, resp_prefs)









    Out[19]:





([1, 2, 3], [1, 2, 3, 0])



In [20]:

    
m = length(prop_prefs)
prop_uf = Vector{Int64}(m)
n = length(resp_prefs)
resp_uf = Vector{Int64}(n)

c = 1
while c <= length(prop_prefs)
    if prop_matched[c] == 0
        prop_uf[c] = length(prop_prefs[c])+1
    else
        prop_uf[c] = findfirst(prop_prefs[c], prop_matched[c])
    end
    c += 1
end

d = 1
while d <= length(resp_prefs)
    if resp_matched[d] == 0
        resp_uf[d] = length(resp_prefs[d])+1
    else
        resp_uf[d] = findfirst(resp_prefs[d], resp_matched[d])
    end
    d += 1
end



In [21]:

    
sum(prop_uf[1:end])









    Out[21]:





3



In [22]:

    
sum(resp_uf[1:end])









    Out[22]:





10

となり、男側が提案した場合、男側の不幸度の合計は8、女側の不幸度の合計は6、全体としての不幸度は14である。

一方、提案を入れ替えた場合、男側の不幸度の合計は10、女側の不幸度の合計は3、全体としての不幸度は13である。

従って、やはり提案の入れ替えにより、男側の不幸度が増加し女側の不幸度は減少している。

また、社会的によいマッチングは、女側が提案した時である。

では、以下では社会的によいマッチングを考える。

簡単のため、全員がマッチングするような例を考える。

あるprop_matchedが与えられた時の全体としての不幸度を求める。



In [23]:

    
# 例-02
prop_prefs = [[1, 2, 3, 4], [3, 2, 1, 4], [1, 2, 4, 3], [4, 1, 3, 2]]
resp_prefs = [[1, 2, 3, 4], [2, 1, 4, 3], [3, 2, 1, 4], [1, 4, 3, 2]]









    Out[23]:





4-element Array{Array{Int64,1},1}:
 [1, 2, 3, 4]
 [2, 1, 4, 3]
 [3, 2, 1, 4]
 [1, 4, 3, 2]



In [24]:

    
function UNF(prop_prefs, resp_prefs, prop_matched)
    m = length(prop_matched)
    resp_matched = Vector{Int64}(m)
    for i in 1:m
        resp_matched[i] = findfirst(prop_matched, i)
    end
    prop_uf = Vector{Int64}(m)
    resp_uf = Vector{Int64}(m)

    c = 1
    while c <= length(prop_prefs)
        prop_uf[c] = findfirst(prop_prefs[c], prop_matched[c])
        c += 1
    end

    d = 1
    while d <= length(resp_prefs)
        resp_uf[d] = findfirst(resp_prefs[d], resp_matched[d])
        d += 1
    end
    return sum(prop_uf[1:end]) + sum(resp_uf[1:end])
end









    Out[24]:





UNF (generic function with 1 method)

例えば、prop_matched = [1, 2, 3, 4]の時は、



In [25]:

    
prop_matched = [1, 2, 3, 4]









    Out[25]:





4-element Array{Int64,1}:
 1
 2
 3
 4



In [26]:

    
UNF(prop_prefs, resp_prefs, prop_matched)









    Out[26]:





13

と求まる。

そこで、1対1の場合の最適なマッチングを、提案を入れ替えて社会的によい方のマッチングとする。

そのような関数を作ることを以下では考える。



In [27]:

    
function my_DA_1(prop_prefs, resp_prefs)
    prop_matched, resp_matched = my_deferred_acceptance(prop_prefs, resp_prefs)
    k = UNF(prop_prefs, resp_prefs, prop_matched)
    prop_matched, resp_matched = my_deferred_acceptance(resp_prefs, prop_prefs)
    l = UNF(prop_prefs, resp_prefs, prop_matched)
    if k < l
        return prop_matched, resp_matched = my_deferred_acceptance(prop_prefs, resp_prefs)
    end
    if l <= k
        return prop_matched, resp_matched = my_deferred_acceptance(resp_prefs, prop_prefs)
    end
end









    Out[27]:





my_DA_1 (generic function with 1 method)



In [28]:

    
# 例-02
prop_prefs = [[1, 2, 3, 4], [3, 2, 1, 4], [1, 2, 4, 3], [4, 1, 3, 2]]
resp_prefs = [[1, 2, 3, 4], [2, 1, 4, 3], [3, 2, 1, 4], [1, 4, 3, 2]]
my_DA_1(prop_prefs, resp_prefs)









    Out[28]:





([1, 2, 3, 4], [1, 2, 3, 4])

となり、確かに社会的によいマッチングとなっている。