Compare the three matching mechanisms

Compare the three matching mechanisms.

1. BOS (list length is three)
2. SOSM (list length is two) + Additional BOS (list length is one)
3. SOSM (list length is three)

1) Features

Before comparing the two mechanisms, a summary of them is described below.



In [1]:

    
%matplotlib inline
import matchfuncs as mf



In [2]:

    
prop_num = 5
resp_num = 3
prop_prefs = [
    [2, 0, 1],
    [2, 1, 0],
    [1, 2, 0],
    [1, 2, 0],
    [1, 2, 0]
]
resp_prefs = [
    [4, 3, 1, 2, 0],
    [1, 0, 4, 3, 2],
    [1, 3, 0, 2, 4]
]
prop_caps = [1, 3, 2, 2, 1]
resp_caps = [2, 2, 4]
list_length = 3

1.1) BOS



In [3]:

    
prop_matched, resp_matched, prop_indptr, resp_indptr = mf.BOS(prop_prefs, resp_prefs, resp_caps, prop_caps, list_length)
print('prop_matched = ' + str(prop_matched))
print('resp_matched = ' + str(resp_matched))
print('prop_indptr = ' + str(prop_indptr))
print('resp_indptr = ' + str(resp_indptr))
mf.Graph(prop_matched, resp_matched, prop_indptr, resp_indptr)









    



prop_matched = [2 2 0 3 2 0 1 2 1]
resp_matched = [1 2 4 3 0 1 2 3]
prop_indptr = [0 1 4 6 8 9]
resp_indptr = [0 2 4 8]

1.2) SOSM + AddBOS



In [4]:

    
prop_matched, resp_matched, prop_indptr, resp_indptr = mf.DA(prop_prefs, resp_prefs, resp_caps, prop_caps, list_length-1)
print('prop_matched = ' + str(prop_matched))
print('resp_matched = ' + str(resp_matched))
print('prop_indptr = ' + str(prop_indptr))
print('resp_indptr = ' + str(resp_indptr))
mf.Graph(prop_matched, resp_matched, prop_indptr, resp_indptr)









    



prop_matched = [2 2 1 3 2 3 2 3 1]
resp_matched = [5 5 4 1 0 1 2 3]
prop_indptr = [0 1 4 6 8 9]
resp_indptr = [0 2 4 8]



In [5]:

    
prop_matched, resp_matched, prop_indptr, resp_indptr = mf.AddBOS(prop_prefs, resp_prefs, prop_matched, resp_matched, resp_caps, prop_caps)
print('prop_matched = ' + str(prop_matched))
print('resp_matched = ' + str(resp_matched))
print('prop_indptr = ' + str(prop_indptr))
print('resp_indptr = ' + str(resp_indptr))
mf.Graph(prop_matched, resp_matched, prop_indptr, resp_indptr)









    



prop_matched = [2 2 1 0 2 3 2 0 1]
resp_matched = [3 1 4 1 0 1 2 3]
prop_indptr = [0 1 4 6 8 9]
resp_indptr = [0 2 4 8]

1.3) SOSM



In [6]:

    
prop_matched, resp_matched, prop_indptr, resp_indptr = mf.DA(prop_prefs, resp_prefs, resp_caps, prop_caps, resp_num)
print('prop_matched = ' + str(prop_matched))
print('resp_matched = ' + str(resp_matched))
print('prop_indptr = ' + str(prop_indptr))
print('resp_indptr = ' + str(resp_indptr))
mf.Graph(prop_matched, resp_matched, prop_indptr, resp_indptr)









    



prop_matched = [2 2 1 0 2 3 2 0 1]
resp_matched = [1 3 4 1 0 1 2 3]
prop_indptr = [0 1 4 6 8 9]
resp_indptr = [0 2 4 8]

2) Comparison

Evaluate Axis is below;

1. Stability  
2. Truth-telling  
3. Efficiency  
4. Fairness  
5. Feasibility

2.1) truth-telling circumstances

The result is

	BOS	DAAdd	DA
Stability	1	0	0
Truth-telling	5	5	5
Efficiency	0.733, 2.167	0.9, 1.333	0.9, 1.333
Fairness	0, 0	0, 0	0, 0
Feasibility	9	13	15



In [7]:

    
# BOS
mf.Comp('BOS', prop_prefs, resp_prefs, resp_caps, prop_caps, list_length)









    Out[7]:





(1.0, 5.0, 0.733, 2.167, 0.0, 0.0, 9.0)



In [8]:

    
# DAAdd
mf.Comp('DAAdd', prop_prefs, resp_prefs, resp_caps, prop_caps, list_length)









    Out[8]:





(0.0, 5.0, 0.9, 1.333, 0.0, 0.0, 13.0)



In [9]:

    
# DA
mf.Comp('DA', prop_prefs, resp_prefs, resp_caps, prop_caps, resp_num)









    Out[9]:





(0.0, 5.0, 0.9, 1.333, 0.0, 0.0, 15.0)

2.2) Nash Equilibria

The result is

	BOS	DAAdd	DA
Nash	2768	3136	3672
Stability	1.236	0.737	0.0
Truth-telling	1.116	1.083	1.02
Efficiency	0.769, 1.854	0.807, 1.626	0.923, 1.333
Fairness	0.0, 0.501	0.0, 0.25	0.0, 0.0
Feasibility	8.696	12.319	15.0



In [10]:

    
# BOS
mf.NashComp('BOS', prop_prefs, resp_prefs, resp_caps, prop_caps, list_length)









    Out[10]:





(2768, 1.236, 1.116, 0.769, 1.854, 0.0, 0.501, 8.696)



In [11]:

    
# DAAdd
mf.NashComp('DAAdd', prop_prefs, resp_prefs, resp_caps, prop_caps, list_length)









    Out[11]:





(3136, 0.737, 1.083, 0.807, 1.626, 0.0, 0.25, 12.319)



In [12]:

    
# DA
mf.NashComp('DA', prop_prefs, resp_prefs, resp_caps, prop_caps, resp_num)









    Out[12]:





(3672, 0.0, 1.02, 0.923, 1.333, 0.0, 0.0, 15.0)

2.3) Common-Value Model

Utility Function for the i-th student is given as follows.

$U_{i} = \alpha CV_{j} + (1-\alpha) PV_{ij}$

$CV_{j}$ means a common value to the j-th seminar. (popularity etc.)
$PV_{ij}$ means the i-th student's private value to the j-th seminar.
These are uniformly distributed over [0, 1), and the lower j is, the higher CV is.
$\alpha$ is a parameter, default set is 0.3.

Utility Function for the j-th seminar is given as follows.

$U_{j} = \beta CV_{i} + (1-\beta) PV_{ji}$

$CV_{i}$ means a common value to the i-th student. (grade etc.)
$PV_{ji}$ means the j-th seminar's private value to the i-th student.
These are uniformly distributed over [0, 1), and the lower i is, the higher CV is.
$\beta$ is a parameter, default set is also 0.3.

Suppose that the preferences of the students and seminars are decided by these utility functions,
and the number of students is 345, that of seminars is 38.
Half of the seminars have capacity 6, while the other half have capacity 13.
All students have 2 capacity.



In [13]:

    
prop_num = 9
resp_num = 6
alpha = 0.3
beta = 0.3
prop_caps = [2 for i in range(prop_num)]
resp_caps = [2, 2, 2, 4, 4, 4]
list_length = 3



In [14]:

    
prop_prefs, resp_prefs = mf.MakeCVprefs(prop_num, resp_num, alpha, beta)



In [15]:

    
print('prop_prefs =')
print(prop_prefs)
print('\nresp_prefs = ')
print(resp_prefs)
print('\nprop_caps = ')
print(prop_caps)
print('\nresp_caps = ')
print(resp_caps)









    



prop_prefs =
[[2 3 0 1 5 4]
 [0 5 2 4 1 3]
 [4 0 3 2 1 5]
 [0 3 1 5 2 4]
 [1 0 4 3 2 5]
 [0 2 5 1 3 4]
 [2 0 1 5 3 4]
 [0 2 3 5 1 4]
 [1 0 2 5 4 3]]

resp_prefs = 
[[5 3 8 2 1 7 6 4 0]
 [1 4 0 7 2 3 5 6 8]
 [2 0 5 3 7 4 1 8 6]
 [1 4 6 5 3 0 8 7 2]
 [4 7 6 1 0 8 3 5 2]
 [4 5 3 0 8 1 7 2 6]]

prop_caps = 
[2, 2, 2, 2, 2, 2, 2, 2, 2]

resp_caps = 
[2, 2, 2, 4, 4, 4]



In [16]:

    
result1 = mf.Comp('BOS', prop_prefs, resp_prefs, resp_caps, prop_caps, list_length)
result2 = mf.Comp('DAAdd', prop_prefs, resp_prefs, resp_caps, prop_caps, list_length)
result3 = mf.Comp('DA', prop_prefs, resp_prefs, resp_caps, prop_caps)



In [17]:

    
print('Justified Envy')
print('1: %s \n2: %s \n3: %s' % (result1[0], result2[0], result3[0]))
print('Truth-telling')
print('1: %s \n2: %s \n3: %s' % (result1[1], result2[1], result3[1]))
print('Efficiency of the students')
print('1: %s \n2: %s \n3: %s' % (result1[2], result2[2], result3[2]))
print('Efficiency of the seminars')
print('1: %s \n2: %s \n3: %s' % (result1[3], result2[3], result3[3]))
print('None Zemi')
print('1: %s \n2: %s \n3: %s' % (result1[4], result2[4], result3[4]))
print('Vacant Caps')
print('1: %s \n2: %s \n3: %s' % (result1[5], result2[5], result3[5]))
print('Interviews')
print('1: %s \n2: %s \n3: %s' % (result1[6], result2[6], result3[6]))









    



Justified Envy
1: 5.0 
2: 2.0 
3: 0.0
Truth-telling
1: 9.0 
2: 9.0 
3: 9.0
Efficiency of the students
1: 1.389 
2: 1.722 
3: 1.556
Efficiency of the seminars
1: 3.833 
2: 4.0 
3: 3.625
None Zemi
1: 0.0 
2: 0.0 
3: 0.0
Vacant Caps
1: 0.0 
2: 2.0 
3: 0.0
Interviews
1: 20.0 
2: 24.0 
3: 54.0

Therefore, the result is

	BOS	DAAdd	DA
Stability	5	2	0
Truth-telling	9	9	9
Efficiency	1.389, 3.833	1.722, 4.0	1.556, 3.625
Fairness	0, 0	0, 2	0, 0
Feasibility	20	24	54