【Python】安定結婚問題と Gale-Shapley アルゴリズム

| 0件のコメント

今回は 「その問題、数理モデルが解決します」 の第 6 章 アルバイトの配属方法 にでてくる Gale-Shapley アルゴリズムを Python で試してみました。 実行環境は Python 3.7.0 です。

安定マッチングと安定結婚問題

参考書籍では, アルバイトの配属を題材に 1:1 マッチングを扱っている。本記事では男性と女性の 1:1 マッチングに置き換える。

男性の集合を M = {a, b, c}, 女性の集合を W = {A, B, C} とする。 男性 i が女性 A を女性 B より好むこと, つまり選好 (preference) を以下のように表す。

     \begin{eqnarray*}   A \succ_i B \end{eqnarray*}

あるペア (i,j) がマッチング m をブロックするとは以下が成立することである。

     \begin{eqnarray*}   j \succ_i m(i) \ and \ i \succ_j m(j) \end{eqnarray*}

マッチング 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. 各男性が第一希望の女性に申し込む.
  2. 1:1 マッチングが完成したら終了.完成しない場合は次に進む.
  3. 2名以上から申し込まれた女性がいる場合, その女性は申し込んだ中から最も望ましい人を残し他の人は断る.
  4. 第 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 の順で好ましさを持っており, この選好は以下で表せる。

     \begin{eqnarray*}   \succ_a: BAC \end{eqnarray*}

また, 女性群 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

おわりに

参考書籍は 「その問題、数理モデルが解決します」 です。

[1] アルゴリズム入門(12) (安定結婚問題) 京都大学
[2] Matching: The Theory