有限人の男女がおり、各人は結婚相手として誰が望ましいか異性をランキングするものとします。ただし、そのランキングの中には独身のままでいることという選択肢を含めることができます。各人はランキングを結婚仲介人に提出し、仲介人は何らかのルールのもとでカップルを決めます。このような問題を結婚安定問題と呼びます。今回は結婚安定問題を定式化した上で、さらに Python を用いてモデル化します。

2019年3月5日:公開

安定結婚問題

安定結婚問題(stable marriage problem)の登場人物は未婚の男女です。男性と女性の人数は同じでなくてもかまいませんが、人数はともに有限であるものとします。

男性は結婚したいと思う順番に女性たちをランキングした上で、そのランキングを結婚仲介者に申告する必要があります。このランキングを選好(preference)と呼び、仲介者をマッチメイカー(match maker)と呼びます。男性は選好を形成する際にすべての女性を一列に並べる必要があります。つまり、すべての女性に順位をつける必要があり、なおかつ異なる女性に対して同じ順位をつけることはできないということです。また、男性には独身のままでいるという選択肢も与えられており、この選択肢を選好の中に含めることができます。

女性もまた結婚したいと思う順番に男性たちをランキングした上で、そうしてできる選好をマッチメイカーに申告します。そこではやはり、すべての男性に順位をつける必要があり、なおかつ異なる男性に対して同じ順位をつけることはできません。また、独身のままでいるという選択肢を選好の中に含めることができます。

以上の要素からなるモデルを安定結婚問題と呼びます。つまり、安定結婚問題とは男性の集合、女性の集合、そして各人の選好からなるモデルです。

 

安定結婚問題の定式化

安定結婚問題を定式化しましょう。まず、すべての男性からなる集合を\(M\)で表し、すべての女性からなる集合を\(W\)で表します。\(M\)と\(W\)は互いに素な有限集合です。仮に男性の人数が有限\(n\)人で女性の人数が有限\(m\)人ならば、男女の集合をそれぞれ、\begin{eqnarray*}
M &=&\{m_{1},\cdots ,m_{n}\} \\
W &=&\{w_{1},\cdots ,w_{m}\}
\end{eqnarray*}と表現できます。男女の人数\(n,m\)の大小に関しては特に制約を設ける必要はありませんが、多くの場合に単純化のために\(n=m\)と仮定します。男女を総称してエージェント(agent)やプレイヤー(player)などと呼ぶこともあります。

男性\(m\in M\)の選好関係を\(\succ _{m}\)で表し、男性\(m\)が女性\(w\in W\)を別の女性\(w^{\prime }\in W\)よりも好むことを\(w\succ _{m}w^{\prime }\)で表現します。また、男性\(m\)にとって独身でいるという選択肢を\(m\)で表します。つまり、男性\(m\)にとって女性\(w\)と結婚することが独身でいることも望ましければ\(w\succ _{m}m \)で表し、女性\(w\)と結婚するよりも独身でいることのほうが望ましければ\(m\succ _{m}w\)で表すということです。男性\(m\)の選好\(\succ _{m}\)のもとでは集合\(W\cup \{m\}\)に属するすべての要素が 1 列に並べられるものとします。つまり、男性はすべての女性に加えて独身であることを引き分けのない形でランキングするという仮定です。

女性\(w\in w\)の選好関係\(\succ _{w}\)についても同様に考えます。つまり、女性\(w\)が男性\(m\in M\)を別の男性\(m^{\prime }\in M\)よりも好むことを\(m\succ _{w}m^{\prime }\)で表現します。また、女性\(w\)にとって独身でいる選択肢を\(w\)で表します。女性\(w\)の選好\(\succ _{w}\)のもとでは集合\(M\cup \{w\}\)に属するすべての要素が 1 列に並べられるものとします。

例(安定結婚問題)
男性の集合を\(M=\{m_{1},m_{2},m_{3},m_{4},m_{5},m_{6}\}\)とし、女性の集合を\(W=\{w_{1},w_{2},w_{3},w_{4},w_{5}\}\)とします。例えば、男性\(m_{1}\)の選好\(\succ _{1}\)として、\begin{equation*}
w_{1}\succ _{1}w_{2}\succ _{1}w_{3}\succ _{1}w_{4}\succ _{1}w_{5}\succ _{1}m_{1}
\end{equation*}というものを考えます。つまり、男性\(m_{1}\)にとって女性\(w_{i}\)は\(i\)番目に望ましい女性であり、\(m_{1}\)すなわち独身でいることが最も望ましくない結果です。上の表記を単純化して、\begin{equation*}
\succ _{1}:w_{1},w_{2},w_{3},w_{4},w_{5},m_{1}
\end{equation*}と書くこともできるものとします。他の男性や女性の選好についても同様に表記します。

 

安定結婚問題を Python で表現する

以降では登場人物として 6 人の男性と 5 人の女性を想定します。ただし、以下の議論は任意の人数の男女についてもそのまま成り立ちます。

まずはプレイヤー集合のモデル化ですが、男女の集合を Python では以下のようなリストを用いて表現します。

上のリスト men には m1 から m6 までの 6 人の男性が、リスト women には w1 から w5 までの 5 人の女性がそれぞれ登録されています。

続いてエージェントの選好のモデル化ですが、例えば、男性 m1 の選好はリスト women に含まれる 5 人の女性と独身であること(この選択肢を自分自身を指す m1 で表現します)を要素とする以下のようなリストを用いて表現します。

ただし、上のリストにおいてより小さいインデックスが割り当てられた要素は男性 m1 にとってより望ましい選択肢であるものと解釈します。つまり、m1 にとって最も望ましい結婚相手は w2 であり、2 番目は w3 であり、3 番目は m1 すなわち独身でいることであり、\(\cdots \)ということです。他のエージェントたちの選好も同様にリストを用いて表現します。

後の便宜のために、入力した男女のリストに対して各人の選好をランダムに生成する関数を定義します。

安定結婚問題において男性 m1 に与えられる選択肢はすべての女性と m1 自身(これは独身を表す)です。そこで、これらを要素とするリストを作成した上で、そのリスト内の要素をランダムに並べ替えて得られるリストとして m1 の選好を表現します。他の男性についても同様の作業を行うことですべての男性の選好からなる辞書を作成します。具体的には以下の通りです。

実行結果の例は以下の通りです。

上の例で利用しているモジュールやメソッドなどについて簡単に解説します。

copy モジュールをインポートすることで利用できる copy メソッドはオブジェクトをコピーします。具体的には、\begin{equation*}
\text{x = copy.copy(y)}
\end{equation*}と記述することで yx にコピーできます。

リストにオブジェクトを加える際には appned メソッドを使います。具体的には、\begin{equation*}
\text{x.append(y)}
\end{equation*}と記述することでリスト x の最後に要素 y を追加します。

random モジュールをインポートすることで利用できる sample メソッドはリストの要素をランダムに並べ替えます。具体的には、\begin{equation*}
\text{random.sample(x,y)}
\end{equation*}と記述すると、リスト x から抽出した y 個の要素をランダムに並べ替えて得られるリストを生成します。その際、もとのリスト x は変更されません。また、y としてリスト x の全要素数 len(x) を指定すれば x の全要素をランダムに並べ替えた新たなリストを得られます。

pprint モジュールをインポートすることで利用できる pprint メソッドはリストや辞書を整形して出力できます。具体的には、\begin{equation*}
\text{pprint.pprint(x)}
\end{equation*}と記述することでリストもしくは辞書 x を整形して画面上に出力します。解説は以上です。

女性たちの選好プロファイルも同じ要領で作成します。具体的には以下の通りです。

実行結果の例は以下の通りです。

最後に以上のコードをすべて統合して、入力された男性のリストと女性リストに対して男女の選好プロファイルを返す関数を定義します。

実行結果の例は以下の通りです。

次回は安定結婚問題の結果であるマッチング(matching)の概念や、結婚安定問題においてマッチメイカーや参加者が直面する問題について解説します。
次へ進む

 

演習問題

今回はそれぞれの参加者がすべての異性と独身という選択肢に対して順位をつけることを要請しましたが、独身よりも望ましくない異性に対して順位をつける必要はないとする場合もあります。具体例を挙げると、男性\(m_{1}\)の選好\(\succ _{1}\)が、\begin{equation}
w_{1}\succ _{1}w_{2}\succ _{1}w_{3}\succ _{1}m_{1}\succ _{1}w_{4}\succ _{1}w_{5} \tag{1}
\end{equation}であるとき、男性\(m_{1}\)が実際に表明する選好は、\begin{equation}
w_{1}\succ _{1}w_{2}\succ _{1}w_{3}\succ _{1}m_{1} \tag{2}
\end{equation}でもよいということです。男性\(m_{1}\)は女性\(w_{4},w_{5}\)と結婚する意志はないため、それらの女性に対しては順位をつける必要がないということです。

そこで、今回作成した関数 preference に手を加えて、それぞれの人の選好から、独身よりも望ましくないすべての異性を除いた形で選好を出力してください。例えば、ランダムに生成した男性\(m_{1}\)の選好が\(\left( 1\right) \)の場合には、それを\(\left( 2\right) \)として出力するということです。このような操作を全員の選好に対して行った形で選好プロファイルを出力することが今回の演習問題です。
解答を見る(プレミアム会員限定)