Examples



In [1]:

    
using MatchingMarkets

Roth and Sotomayor (1990)

Example 2.9



In [2]:

    
m, n = 5, 4;



In [3]:

    
m_prefs = [
    1, 2, 3, 4, 0,
    4, 2, 3, 1, 0,
    4, 3, 1, 2, 0,
    1, 4, 3, 2, 0,
    1, 2, 4, 0, 3,
]
m_prefs = reshape(m_prefs, n+1, m)









    Out[3]:





5×5 Array{Int64,2}:
 1  4  4  1  1
 2  2  3  4  2
 3  3  1  3  4
 4  1  2  2  0
 0  0  0  0  3



In [4]:

    
f_prefs = [
    2, 3, 1, 4, 5, 0,
    3, 1, 2, 4, 5, 0,
    5, 4, 1, 2, 3, 0,
    1, 4, 5, 2, 3, 0,
]
f_prefs = reshape(f_prefs, m+1, n)









    Out[4]:





6×4 Array{Int64,2}:
 2  3  5  1
 3  1  4  4
 1  2  1  5
 4  4  2  2
 5  5  3  3
 0  0  0  0



In [5]:

    
deferred_acceptance(m_prefs, f_prefs)









    Out[5]:





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



In [6]:

    
deferred_acceptance(f_prefs, m_prefs)









    Out[6]:





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

Example 2.17



In [7]:

    
m = n = 4;



In [8]:

    
m_prefs = [
    1, 2, 3, 4, 0,
    2, 1, 4, 3, 0,
    3, 4, 1, 2, 0,
    4, 3, 2, 1, 0,
]
m_prefs = reshape(m_prefs, n+1, m)









    Out[8]:





5×4 Array{Int64,2}:
 1  2  3  4
 2  1  4  3
 3  4  1  2
 4  3  2  1
 0  0  0  0



In [9]:

    
f_prefs = [
    4, 3, 2, 1, 0,
    3, 4, 1, 2, 0,
    2, 1, 4, 3, 0,
    1, 2, 3, 4, 0,
]
f_prefs = reshape(f_prefs, m+1, n)









    Out[9]:





5×4 Array{Int64,2}:
 4  3  2  1
 3  4  1  2
 2  1  4  3
 1  2  3  4
 0  0  0  0



In [10]:

    
deferred_acceptance(m_prefs, f_prefs)









    Out[10]:





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



In [11]:

    
deferred_acceptance(f_prefs, m_prefs)









    Out[11]:





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

Example 5.24



In [12]:

    
m_caps = fill(2, m)
f_caps = m_caps









    Out[12]:





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



In [13]:

    
deferred_acceptance(m_prefs, f_prefs, m_caps, f_caps)









    Out[13]:





([1, 2, 1, 2, 3, 4, 3, 4], [1, 2, 2, 1, 3, 4, 4, 3], [1, 3, 5, 7, 9], [1, 3, 5, 7, 9])



In [14]:

    
deferred_acceptance(f_prefs, m_prefs, f_caps, m_caps)









    Out[14]:





([3, 4, 3, 4, 1, 2, 1, 2], [4, 3, 3, 4, 2, 1, 1, 2], [1, 3, 5, 7, 9], [1, 3, 5, 7, 9])

Page 162



In [15]:

    
m, n = 7, 5;



In [16]:

    
s_prefs = [
    5, 1, 0, 2, 3, 4,
    2, 5, 1, 0, 3, 4,
    3, 1, 0, 2, 4, 5,
    4, 1, 0, 2, 3, 5,
    1, 2, 0, 3, 4, 5,
    1, 3, 0, 2, 4, 5,
    1, 3, 4, 0, 2, 6,
]
s_prefs = reshape(s_prefs, n+1, m)









    Out[16]:





6×7 Array{Int64,2}:
 5  2  3  4  1  1  1
 1  5  1  1  2  3  3
 0  1  0  0  0  0  4
 2  0  2  2  3  2  0
 3  3  4  3  4  4  2
 4  4  5  5  5  5  6



In [17]:

    
c_prefs = [
    1, 2, 3, 4, 5, 6, 7, 0,
    5, 2, 0, 1, 3, 4, 6, 7,
    6, 7, 3, 0, 1, 2, 4, 5,
    7, 4, 0, 1, 2, 3, 5, 6,
    2, 1, 0, 3, 4, 5, 6, 7,
]
c_prefs = reshape(c_prefs, m+1, n)









    Out[17]:





8×5 Array{Int64,2}:
 1  5  6  7  2
 2  2  7  4  1
 3  0  3  0  0
 4  1  0  1  3
 5  3  1  2  4
 6  4  2  3  5
 7  6  4  5  6
 0  7  5  6  7



In [18]:

    
caps = ones(Int, n)
caps[1] = 3
caps









    Out[18]:





5-element Array{Int64,1}:
 3
 1
 1
 1
 1



In [19]:

    
deferred_acceptance(s_prefs, c_prefs, caps)









    Out[19]:





([5, 2, 3, 4, 1, 1, 1], [7, 6, 5, 2, 3, 4, 1], [1, 4, 5, 6, 7, 8])



In [20]:

    
deferred_acceptance(s_prefs, c_prefs, caps, SProposing)









    Out[20]:





([5, 2, 3, 4, 1, 1, 1], [7, 6, 5, 2, 3, 4, 1], [1, 4, 5, 6, 7, 8])



In [21]:

    
deferred_acceptance(s_prefs, c_prefs, caps, CProposing)









    Out[21]:





([1, 5, 1, 1, 2, 3, 4], [1, 3, 4, 5, 6, 7, 2], [1, 4, 5, 6, 7, 8])

Gusfield and Irving (1989)

Section 1.6.5



In [22]:

    
m, n = 11, 5;



In [23]:

    
s_prefs = [
    3, 1, 5, 4, 0, 2,
    1, 3, 4, 2, 5, 0,
    4, 5, 3, 1, 2, 0,
    3, 4, 1, 5, 0, 2,
    1, 4, 2, 0, 3, 5,
    4, 3, 2, 1, 5, 0,
    2, 5, 1, 3, 0, 4,
    1, 3, 2, 5, 4, 0,
    4, 1, 5, 0, 2, 3,
    3, 1, 5, 2, 4, 0,
    5, 4, 1, 3, 2, 0,
]
s_prefs = reshape(s_prefs, n+1, m)









    Out[23]:





6×11 Array{Int64,2}:
 3  1  4  3  1  4  2  1  4  3  5
 1  3  5  4  4  3  5  3  1  1  4
 5  4  3  1  2  2  1  2  5  5  1
 4  2  1  5  0  1  3  5  0  2  3
 0  5  2  0  3  5  0  4  2  4  2
 2  0  0  2  5  0  4  0  3  0  0



In [24]:

    
c_prefs = [
    3, 7, 9, 11, 5, 4, 10, 8, 6, 1, 2, 0,
    5, 7, 10, 6, 8, 2, 3, 11, 0, 1, 4, 9,
    11, 6, 8, 3, 2, 4, 7, 1, 10, 0, 5, 9,
    10, 1, 2, 11, 4, 9, 5, 3, 6, 8, 0, 7,
    2, 4, 10, 7, 6, 1, 8, 3, 11, 9, 0, 5,
]
c_prefs = reshape(c_prefs, m+1, n)









    Out[24]:





12×5 Array{Int64,2}:
  3   5  11  10   2
  7   7   6   1   4
  9  10   8   2  10
 11   6   3  11   7
  5   8   2   4   6
  4   2   4   9   1
 10   3   7   5   8
  8  11   1   3   3
  6   0  10   6  11
  1   1   0   8   9
  2   4   5   0   0
  0   9   9   7   5



In [25]:

    
caps = [4, 1, 3, 2, 1];



In [26]:

    
deferred_acceptance(s_prefs, c_prefs, caps)









    Out[26]:





([3, 1, 4, 3, 1, 3, 2, 1, 4, 1, 5], [2, 10, 8, 5, 7, 1, 6, 4, 3, 9, 11], [1, 5, 6, 9, 11, 12])



In [27]:

    
deferred_acceptance(s_prefs, c_prefs, caps, SProposing)









    Out[27]:





([3, 1, 4, 3, 1, 3, 2, 1, 4, 1, 5], [2, 10, 8, 5, 7, 1, 6, 4, 3, 9, 11], [1, 5, 6, 9, 11, 12])



In [28]:

    
deferred_acceptance(s_prefs, c_prefs, caps, CProposing)









    Out[28]:





([4, 5, 3, 1, 1, 3, 2, 3, 1, 4, 1], [4, 5, 9, 11, 7, 3, 6, 8, 1, 10, 2], [1, 5, 6, 9, 11, 12])

The book claims that the following matching $M_7$ is the hospital-optimal (college-optimal in our language) stable matching: $$ \begin{array} ~ & r_1 & r_2 & r_3 & r_4 & r_5 & r_6 & r_7 & r_8 & r_9 & r_{10} & r_{11} \\ M_7 & h_4 & h_4 & h_3 & h_1 & h_1 & h_3 & h_2 & h_3 & h_1 & h_5 & h_1 \end{array} $$

but the above matching, say $M_8$, appears to be the hospital-optimal matching: $$ \begin{array} ~ & r_1 & r_2 & r_3 & r_4 & r_5 & r_6 & r_7 & r_8 & r_9 & r_{10} & r_{11} \\ M_8 & h_4 & h_5 & h_3 & h_1 & h_1 & h_3 & h_2 & h_3 & h_1 & h_4 & h_1 \end{array} $$



In [ ]: