# 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 [ ]: