In 1962, D. Gale and L. S. Shapley raised the issue of stable marriage. Chaprey won the Nobel Prize in Economics in 2012 for this series of achievements.
The stable marriage problem is as follows. (From Wikipedia)
An example of a stable marriage problem consists of N men and N women, and each individual's wish list. The wish list is a list of all the opposite sexes arranged in total order based on each individual's preference. The solution to the stable marriage problem is stable matching. For the example of the stable marriage problem A pair that you like more than the other person you are currently pairing with (hereinafter referred to as a blocking pair) Matching that does not exist is called stable matching.
The stable marriage problem is a type of stable matching problem, and the stable matching problem is widely used, such as assigning residents to hospitals and university students to laboratories. Resident assignment has been used in the United States since around 1950, and has recently begun to be used in Japan.
Stable matching problems can be solved with stable_matching in Python's ortoolpy (http://qiita.com/Tsutomu-KKE@github/items/2ec5f7626054f4b4de63) can do. Let's try it out.
Stable_matching of ortoolpy can only be solved if the number of residents and assignees is the same. Here, if the acceptable number of assignment destination A is 2, let's create a dummy of the assignment destination such as assignment destination A_0 and assignment destination A_1 and match them. We define a method stable_matching2 that solves such an extended stable matching problem.
python3
from itertools import accumulate
from ortoolpy import stable_matching
def stable_matching2(prefs, prefl, capa):
"""
Asymmetric matching
prefs:Residents' preferences for their assignment
prefl:Preference for residents(All assignments have the same preference)
capa:Acceptable number of assignees
"""
acca = list(accumulate([0] + capa[:-1])) #Cumulative acceptable number
idx = [i for i, j in enumerate(capa) for _ in range(j)] #Dummy assignment destination → assignment destination conversion list
prefs = [[j+acca[i] for i in pr for j in range(capa[i])] for pr in prefs] #Dummy selection
res = stable_matching([prefl] * len(prefl), prefs)
return{k:idx[v] for k, v in res.items()} #Return the dummy to the original
Create a question at random.
python3
lab_capa = [2, 3, 3, 2] #Acceptable number of assignees
ns, nl = sum(lab_capa), len(lab_capa) #Number of residents and assignments
import numpy as np
np.random.seed(1)
def shuffled(n):
"""0..n-Shuffle and return 1"""
a = np.arange(n)
np.random.shuffle(a)
return a.tolist()
performance = shuffled(ns) #Preference for residents
preferences = [shuffled(nl) for i in range(ns)] #Preference for assignment
print(performance)
print(preferences)
>>>
[2, 9, 6, 4, 0, 3, 1, 7, 8, 5]
[[2, 0, 1, 3], [3, 0, 1, 2], [3, 1, 2, 0], [3, 1, 0, 2], [1, 3, 2, 0],
[3, 0, 2, 1], [3, 2, 1, 0], [1, 0, 2, 3], [0, 3, 1, 2], [2, 0, 3, 1]]
Solve and display the result.
python3
res = stable_matching2(preferences, performance, lab_capa)
for k, v in res.items():
print('medical intern%d ->Assigned to%d'%(k,v))
>>>
Resident 0->Assigned to 2
Resident 1->Assigned to 0
Resident 2->Assigned to 3
Resident 3->Assigned to 1
Resident 4->Assigned to 1
Resident 5->Assigned to 2
Resident 6->Assigned to 3
Resident 7->Assigned to 1
Resident 8->Assigned to 0
Resident 9->Assigned to 2
The stable matching problem is a problem that seeks matching without blocking pairs, and what we care about is the relative value of preference order. If the preference is an absolute value in the first place, it becomes a weight matching problem of the combinatorial optimization problem.
The absolute value is, for example, the commuting time from the trainee's home to the place of assignment. At this time, the problem of minimizing the total commuting time of all residents is a weight matching problem, which can be solved by the Edmonds method or the like.
The solution of the weight matching problem is stable matching, but the solution of the stable matching problem is not always the optimal solution of the weight matching problem.
After all, it looks like this:
You can think of probable weights → Weight matching problem The exact weight is unknown, but the order is known → Stable matching problem
reference Learn about romance while solving Haskell programming while solving stable marriage problems that's all
Recommended Posts