Deferred Acceptance Algorithm Demo

In [1]:

    

include("test_deferred_acceptance.jl")


    

    




Test Summary:       | Pass  Total
Testing matching.jl |    4      4






    
Out[1]:





BaseTestNext.DefaultTestSet("Testing matching.jl",Any[BaseTestNext.DefaultTestSet("gale_shapley_T",Any[Test Passed
  Expression: m_matched_computed == m_matched_expected
   Evaluated: [1,2,3,0] == [1,2,3,0],Test Passed
  Expression: f_matched_computed == f_matched_expected
   Evaluated: [1,2,3] == [1,2,3],Test Passed
  Expression: m_matched_computed == m_matched_expected
   Evaluated: [1,2,3,0] == [1,2,3,0],Test Passed
  Expression: f_matched_computed == f_matched_expected
   Evaluated: [1,2,3] == [1,2,3]],false)],false)

In [109]:

    

include("matching.jl")
include("matching_tools.jl")


    

    




WARNING: replacing module Matching






    
Out[109]:





_randperm2d! (generic function with 1 method)

In [3]:

    

srand(613)
m_prefs, f_prefs = random_prefs(4, 3, allow_unmatched=true)
println(m_prefs)
println(f_prefs)
println(Matching.gale_shapley_T(m_prefs, f_prefs))


    

    




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

In [4]:

    

function make_preferences(loop::Int=1000, m_size::Int=1000, f_size::Int=1000, seed::Int64=617)
    srand(seed)
    m_prefs = Array{Int64}(loop, f_size+1, m_size)
    f_prefs = Array{Int64}(loop, m_size+1, f_size)
    for i in 1:loop
        m_pref, f_pref = random_prefs(m_size, f_size, allow_unmatched=true)
        m_prefs[i, :, :] = m_pref
        f_prefs[i, :, :] = f_pref
    end
    
    return m_prefs, f_prefs
end

function speedtest(func::Function, m_prefs, f_prefs, loop)
    m_size = size(m_prefs, 3)
    f_size = size(f_prefs, 3)
    for i in 1:loop
        m_pref = reshape(m_prefs[i, :, :], f_size+1, m_size)
        f_pref = reshape(f_prefs[i, :, :], m_size+1, f_size)
    end
end


    

    
Out[4]:





speedtest (generic function with 1 method)

In [5]:

    

m_size = 1000
f_size = 1000
loop = 100

@time m_prefs, f_prefs = make_preferences(loop, m_size, f_size) 
@time speedtest(Matching.gale_shapley_T, m_prefs, f_prefs, loop)


    

    




  8.922630 seconds (660.59 k allocations: 3.011 GB, 4.75% gc time)
  3.317073 seconds (64.48 k allocations: 1.495 GB, 6.80% gc time)

In [107]:

    

function is_stable_matching{T<:Int}(
    m_matched::AbstractArray{T, 1}, f_matched::AbstractArray{T, 1},
    m_prefs::AbstractArray{T, 2}, f_prefs::AbstractArray{T, 2})
    
    m_size = size(m_prefs, 1)
    f_size = size(f_prefs, 1)

    f_rankings = argsort(m_prefs)
    m_rankings = argsort(f_prefs)

    for i in 1:m_size
        f = m_matched[i]
        for j in 1:m_size
            # jにとって現在マッチしている相手よりも, fの方が順位が上なら
            f_j = m_matched[j]
            if f_rankings[j, f] < f_rankings[j, f_j]
                # 更にfにとってiよりもjの順位が上なら, Blocking pair
                if m_rankings[f, j] < m_rankings[f, i]
                    println("Blocking pair man: %s woman: %s" % (j, f_j))
                    return false
                end
            end
        end
    end
    return true
end


    

    
Out[107]:





is_stable_matching (generic function with 1 method)

In [110]:

    

srand(613)
m_prefs, f_prefs = random_prefs(4, 3, allow_unmatched=true)
println(m_prefs)
println(f_prefs)

m_matched, f_matched = Matching.gale_shapley_T(m_prefs, f_prefs)
println(m_matched, f_matched)
println(Matching.is_stable_matching(m_matched, f_matched, m_prefs', f_prefs'))

m_matching2 = Array{Int64}([0, 2, 0, 3])
f_matching2 = Matching.make_f_matched_from_m_matched(m_matching2, 4, 3)
println(m_matching2, f_matching2)
println(Matching.is_stable_matching(m_matching2, f_matching2, m_prefs', f_prefs'))


    

    




[2 2 1 1
 3 0 2 0
 0 3 3 2
 1 1 0 3]
[3 4 4
 2 1 3
 0 2 2
 1 0 1
 4 3 0]
[2,0,1,0][3,1,0]
true
[0,2,0,3][0,2,4]
Invalid matchings
For man: 4, staying alone is better than matching with woman: 3.
false

In [113]:

    

srand(613)
m_prefs, f_prefs = random_prefs(4, 3, allow_unmatched=true)
println(Matching.gale_shapley_T(m_prefs, f_prefs))
println("Stable matching: $(Matching.find_all_stable_matchings(m_prefs', f_prefs'))")


    

    




([2,0,1,0],[3,1,0])
Stable matching: Set(Any[[2,0,1,0]])

In [114]:

    

srand(613)

for i in 1:10
    m_prefs, f_prefs = random_prefs(4, 3, allow_unmatched=true)
    println("$(i) 個目のPreference")
    println(m_prefs)
    println(f_prefs)
    println(Matching.gale_shapley_T(m_prefs, f_prefs))
    println("Stable matching: $(Matching.find_all_stable_matchings(m_prefs', f_prefs'))")
    println("\n")
end


    

    




1 個目のPreference
[2 2 1 1
 3 0 2 0
 0 3 3 2
 1 1 0 3]
[3 4 4
 2 1 3
 0 2 2
 1 0 1
 4 3 0]
([2,0,1,0],[3,1,0])
Stable matching: Set(Any[[2,0,1,0]])


2 個目のPreference
[1 2 2 2
 2 1 0 1
 3 3 1 0
 0 0 3 3]
[2 3 2
 3 4 4
 0 0 0
 4 2 1
 1 1 3]
([0,1,2,0],[2,3,0])
Stable matching: Set(Any[[0,1,2,0]])


3 個目のPreference
[2 1 3 2
 3 0 0 3
 0 3 1 0
 1 2 2 1]
[1 2 3
 2 1 2
 3 3 0
 0 4 4
 4 0 1]
([2,1,3,0],[2,1,3])
Stable matching: Set(Any[[2,1,3,0]])


4 個目のPreference
[3 2 3 2
 0 3 1 3
 1 0 0 1
 2 1 2 0]
[3 1 2
 0 0 3
 2 2 0
 4 3 1
 1 4 4]
([0,3,1,0],[3,0,2])
Stable matching: Set(Any[[0,3,1,0]])


5 個目のPreference
[3 3 1 2
 0 1 0 0
 1 0 3 1
 2 2 2 3]
[4 3 2
 2 4 4
 0 0 3
 1 1 0
 3 2 1]
([0,3,0,2],[0,4,2])
Stable matching: Set(Any[[0,3,0,2]])


6 個目のPreference
[2 2 3 1
 3 0 1 2
 1 1 2 3
 0 3 0 0]
[3 1 2
 1 4 4
 4 0 1
 2 3 3
 0 2 0]
([2,0,3,1],[4,1,3])
Stable matching: Set(Any[[2,0,1,3],[2,0,3,1]])


7 個目のPreference
[1 1 2 2
 2 2 3 3
 3 0 1 0
 0 3 0 1]
[2 1 3
 1 4 0
 4 2 2
 3 3 1
 0 0 4]
([2,1,3,0],[2,1,3])
Stable matching: Set(Any[[2,1,3,0]])


8 個目のPreference
[1 3 3 3
 0 0 1 0
 2 1 2 1
 3 2 0 2]
[3 3 2
 0 2 3
 4 0 1
 2 1 0
 1 4 4]
([0,3,1,0],[3,0,2])
Stable matching: Set(Any[[0,3,1,0]])


9 個目のPreference
[3 1 1 3
 0 0 2 1
 2 2 3 0
 1 3 0 2]
[3 1 2
 0 3 0
 2 0 3
 4 4 4
 1 2 1]
([0,0,1,0],[3,0,0])
Stable matching: Set(Any[[0,0,1,0]])


10 個目のPreference
[2 3 2 1
 3 2 3 2
 0 1 1 3
 1 0 0 0]
[1 1 3
 4 3 2
 2 2 4
 0 4 0
 3 0 1]
([2,0,3,1],[4,1,3])
Stable matching: Set(Any[[2,0,3,1]])