今回は 『その問題、数理モデルが解決します』の第 6 章 アルバイトの配属方法 にでてくる Gale-Shapley アルゴリズムを Python で試してみました。 実行環境は Python 3.7.0 です。
安定マッチングと安定結婚問題
参考書籍では, アルバイトの配属を題材に 1:1 マッチングを扱っている。本記事では男性と女性の 1:1 マッチングに置き換える。
男性の集合を M = {a, b, c}, 女性の集合を W = {A, B, C} とする。 男性 i が女性 A を女性 B より好むこと, つまり選好 (preference) を以下のように表す。
あるペア (i,j) がマッチング m をブロックするとは以下が成立することである。
マッチング m が選好のもとで安定的であるとは, どのようなペア (i,j) でも m がブロックされないことである。 m がブロックされる場合 m は不安定である。
安定マッチングを求める問題を, 安定結婚問題 (stable marriage problem) という。
Gale-Shapley アルゴリズム
Deferred Acceptance (DA) アルゴリズム, または Gale-Shapley (GS) アルゴリズムは College Admissions and the Stability of Marriage [D.Gale and L.S.Shapley, 1962] で提案された手法で安定的なマッチングを実現する。ただし, 最適なマッチングには方向性があり, 男性最適安定マッチングと女性最適安定マッチングがある。
GSアルゴリズムの手順は以下。
- 各男性が第一希望の女性に申し込む.
- 1:1 マッチングが完成したら終了.完成しない場合は次に進む.
- 2名以上から申し込まれた女性がいる場合, その女性は申し込んだ中から最も望ましい人を残し他の人は断る.
- 第 k 希望の女性から断られた男性は第 k+1 希望の女性へ申し込み, 手順2に戻る.
上記は男性最適安定マッチングの手順で, 男性と女性を入れ替えると女性最適安定マッチングとなる。
GSアルゴリズムの実装は gist.github.com/joyrexus/9967709 を参考として主に pandas.DataFrame を引数に取るように変更。
# -*- coding: utf-8 -*-
from collections import defaultdict
class Matcher:
def __init__(self, men, women):
'''
Constructs a Matcher instance.
Takes a pandas.DataFrame `men` and a pandas.DataFrame `women`.
'''
self.M = men
self.W = women
self.wives = {}
self.pairs = []
# we index spousal preferences at initialization
# to avoid expensive lookups when matching
self.mrank = defaultdict(dict) # `mrank[m][w]` is m's ranking of w
self.wrank = defaultdict(dict) # `wrank[w][m]` is w's ranking of m
ncol = men.shape[1]
for _, row in men.iterrows():
for j in range(1, ncol):
self.mrank[row['id']][row[str(j)]] = j
ncol = women.shape[1]
for _, row in women.iterrows():
for j in range(1, ncol):
self.wrank[row['id']][row[str(j)]] = j
def prefers(self, w, m, h):
'''Test whether w prefers m over h.'''
return self.wrank[w][m] < self.wrank[w][h]
def after(self, m, w):
'''Return the woman favored by m after w.'''
i = self.mrank[m][w] + 1 # index of woman following w in list of prefs
return self.M.loc[self.M['id'] == m][str(i)].values[0]
def match(self, men=None, next=None, wives=None):
'''
Try to match all men with their next preferred spouse.
'''
if men is None:
men = list(self.M['id'].values) # get the complete list of men
if next is None:
# if not defined, map each man to their first preference
next = dict((row['id'], row['1']) for m, row in self.M.iterrows())
if wives is None:
wives = {} # mapping from women to current spouse
if not len(men):
self.pairs = [(h, w) for w, h in wives.items()]
self.wives = wives
return wives
m, men = list(men)[0], list(men)[1:]
w = next[m] # next woman for m to propose to
next[m] = self.after(m, w) # woman after w in m's list of prefs
if w in wives:
h = wives[w] # current husband
if self.prefers(w, m, h):
men.append(h) # husband becomes available again
wives[w] = m # w becomes wife of m
else:
men.append(m) # m remains unmarried
else:
wives[w] = m # w becomes wife of m
# print('m: {0}, w: {1}, men: {2}'.format(m, w, men))
return self.match(men, next, wives)
def is_stable(self, wives=None, verbose=False):
if wives is None:
wives = self.wives
for w, m in wives.items():
mrank = list(self.M.loc[self.M['id'] == m].values[0][1:])
i = mrank.index(w)
preferred = mrank[:i]
for p in preferred:
h = wives[p]
wrank = list(self.W.loc[self.W['id'] == p].values[0][1:])
if wrank.index(m) < wrank.index(h):
msg = "{}'s marriage to {} is unstable: " + \
"{} prefers {} over {} and {} prefers " + \
"{} over her current husband {}"
if verbose:
print(msg.format(m, w, m, p, w, p, m, h))
return False
return True
男性群 M = {a, b, c} の選好を以下 (men.csv) とする。
id,1,2,3
a,B,A,C
b,A,C,B
c,B,C,A
例えば, 男性 a は女性群に対して B, A, C の順で好ましさを持っており, この選好は以下で表せる。
また, 女性群 W = {A, B, C} の選好を以下 (women.csv) とする。
id,1,2,3
A,a,b,c
B,b,a,c
C,c,b,a
Matcher クラスに男性群と女性群の選好を渡す。
$ ipython
Python 3.7.0 (default, Jun 28 2018, 07:39:16)
Type 'copyright', 'credits' or 'license' for more information
IPython 6.5.0 -- An enhanced Interactive Python. Type '?' for help.
In [1]: from matcher import Matcher
In [2]: import pandas as pd
In [3]: men = pd.read_csv('data/men.csv')
In [4]: women = pd.read_csv('data/women.csv')
In [5]: m = Matcher(men, women)
match メソッドで安定マッチングを求める。
In [6]: wives = m.match()
In [7]: 'wives: {0}, is_stable: {1}'.format(wives, m.is_stable())
Out[7]: "wives: {'B': 'a', 'A': 'b', 'C': 'c'}, is_stable: True"
ペアの一覧は以下となる。
In [8]: pairs = pd.DataFrame(m.pairs, columns=['man', 'woman'])
In [9]: pairs
Out[9]:
man woman
0 a B
1 b A
2 c C
おわりに
参考書籍は『その問題、数理モデルが解決します』です。
