安定結婚問題においてマッチメイカーはすべての男女に自身の選好を表明させた上で、あらかじめ定めた何らかのルールにもとづいて誰と誰が結婚するかを決定します。そのようにして得られる夫婦の組をマッチングと呼びます。

2019年3月6日:公開

マッチング

安定結婚問題においてマッチメイカーはすべての男女に自身の選好を表明させた上で、あらかじめ定めた何らかのルールにもとづいて誰と誰が結婚するかを決定します。そのようにして得られる夫婦の組をマッチング(matching)と呼びます。

それぞれのマッチングにおいて各人は異性とマッチするか独身のままでいるかのどちらか一方です。また、各人は複数の相手とマッチすることはできないものとします。重婚の可能性を排除するということです。

 

マッチングの定式化

マッチングの概念を定式化します。男性の集合\(M\)と女性の集合\(W\)が与えられたとき、それぞれのエージェント\(i\in M\cup W\)に対して異性の結婚相手もしくは独身という選択肢\(\mu \left( i\right) \in M\cup W\)を特定する写像\(\mu :M\cup W\rightarrow M\cup W\)としてマッチングを定式化します。ただし、この写像は以下の条件\begin{eqnarray*}
&&\left( a\right) \ \forall (m,w)\in M\times W:[\mu (m)=w\ \Leftrightarrow \ \mu (w)=m] \\
&&\left( b\right) \ \forall m\in M:[\mu (m)\not\in W\ \Rightarrow \ \mu \left( m\right) =m] \\
&&\left( c\right) \ \forall w\in W:[\mu (w)\not\in M\ \Rightarrow \ \mu \left( w\right) =w] \end{eqnarray*}を満たします。

条件\(\left( a\right) \)は、マッチング\(\mu \)のもとで男性\(m\)の妻が女性\(w\)であることと、その女性\(w\)の夫が男性\(m\)であることが同値であることを意味します。男女\(m,w\)に対して条件\(\left( a\right) \)が成り立つとき、マッチング\(\mu \)のもとで\(m\)と\(w\)はマッチする(matched)と言います。\(m\)と\(w\)は夫婦関係にあるということです。条件\(\left( b\right) \)は、マッチング\(\mu \)のもとで女性とマッチしない男性は自身とマッチすること、すなわち独身であることを意味します。条件\(\left( c\right) \)は、マッチング\(\mu \)のもとで男性とマッチしない女性は自身とマッチすること、すなわち独身であることを意味します。

例(マッチング)
男性の集合を\(M=\{m_{1},m_{2},m_{3},m_{4},m_{5},m_{6}\}\)とし、女性の集合を\(W=\{w_{1},w_{2},w_{3},w_{4},w_{5}\}\)とします。例えば、\begin{eqnarray*}
\mu \left( m_{1}\right) &=&w_{3} \\
\mu \left( m_{2}\right) &=&w_{1} \\
\mu \left( m_{3}\right) &=&w_{5} \\
\mu \left( m_{4}\right) &=&m_{4} \\
\mu \left( m_{5}\right) &=&w_{4} \\
\mu \left( m_{6}\right) &=&w_{2}
\end{eqnarray*}というマッチング\(\mu :M\cup W\rightarrow M\cup W\)について考えます。つまり、\(m_{1}\)と\(w_{3}\)が夫婦であり、\(m_{2}\)と\(w_{1}\)が夫婦であり、\(\cdots \)ということです。上の表記を単純化して、\begin{equation*}
\begin{pmatrix}
m_{1} & m_{2} & m_{3} & m_{4} & m_{5} & m_{6} \\
w_{3} & w_{1} & w_{5} & m_{4} & w_{4} & w_{2}\end{pmatrix}\end{equation*}と書くこともできるものとします。
例(マッチング)
男性の集合を\(M=\{m_{1},m_{2},m_{3},m_{4},m_{5},m_{6}\}\)とし、女性の集合を\(W=\{w_{1},w_{2},w_{3},w_{4},w_{5}\}\)とします。ある写像\(\mu :M\cup W\rightarrow M\cup W\)が、\begin{equation*}
\mu \left( m_{1}\right) =\mu \left( m_{2}\right) =w_{1}
\end{equation*}を満たすとき、マッチングを定義する条件\(\left( a\right) \)より\(m_{1}=m_{2}\)が成り立ちますが、これは矛盾です。したがって、この写像\(\mu \)はマッチングではありません。この例のように、同一人物が異なる 2 人の異性と同時にマッチすることはできません。重婚を認めないということです。

 

マッチングを Python で表現する

男女のリストとして前回と同様に以下を用います。

例えば、マッチング\begin{equation*}
\begin{pmatrix}
m_{1} & m_{2} & m_{3} & m_{4} & m_{5} & m_{6} \\
w_{3} & w_{1} & w_{5} & m_{4} & w_{4} & w_{2}\end{pmatrix}\end{equation*}が与えられたとき、これを以下のような辞書を用いて表現します。

後の便宜のために、入力した男女のリスト menwomen に対してマッチングをランダムに生成する関数を定義します。

マッチングをランダムに生成する処理は以下の通りです。

今回新たに登場したメソッドないしモジュールについて簡単に解説します。

remove メソッドはリストから特定の要素を削除します。具体的には、\begin{equation*}
\text{x.remove(y)}
\end{equation*}と記述すると、リスト x の要素の中から y と同じものを検索し、該当するものがある場合にはその中の最初の要素を削除します。解説は以上です。

上の処理を活用して、入力された男性のリストと女性リストに対してランダムに生成したマッチングを返す関数を定義します。

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

安定結婚問題の課題

マッチメイカーはすべての男女に自身の選好を申告させた上で、何らかのルールにもとづいてマッチングを決定します。すべての男女が申告した選好の組に対してマッチングを定めるルールをメカニズム(mechanism)と呼びます。では、マッチメイカーはどのような性質を持つメカニズムを採用すればよいでしょうか。候補としては個人合理性や効率性、安定性などというものが広く使われますが、これらについては後ほど解説します。いずれにせよ、マッチメイカーは何らかの基準を採用した上で、その基準を満たすマッチングを導出するようなメカニズムを設計し、そのメカニズムを活用することで当初定めた基準を満たすマッチングを遂行しようとします。つまり、安定結婚問題は最適配分問題(optimum allocation problem)としての側面を持ちます。

安定結婚問題における最大のポイントは、各自の選好はその人だけが知っている情報であり、他の人やマッチメイカーはそれを事前に観察できないということです。ある人が自分の選好を事前に公言した場合でも、それがその人の真の選好であるか否かを他の人が検証することは原理的に不可能です。各々はより望ましい異性と結婚するために、マッチメイカーに選好を申告する際に戦略的に嘘をつく可能性がありますが、マッチメイカーは原理的にそれが嘘であるか否かを確認できません。

マッチメイカーが何らかの望ましさの基準を採用し、エージェントたちの選好の組に対してその基準を満たすマッチングを導出するメカニズムを設計した場合でも、そこから得られるマッチングは当初定めた基準を満たすものである保証はありません。先に指摘したように、各人は戦略的に偽りの選好を申告する可能性がありますが、マッチメイカーは申告された選好が偽りであるかどうかを見抜くことは原理的に不可能です。したがって、偽りの選好を申告する人がいる場合には、マッチメイカーは偽りの情報を入力として最適なマッチングを導出することになり、得られるマッチングは真の意味では最適ではないということになります。各人が持つ情報が対称的ではないことに起因するこのような問題をインセンティブの問題(incentive problem)と呼びます。安定結婚問題は情報の非対称性に起因するインセンティブの問題としての側面も持っています。

インセンティブの問題を解決するためには、マッチメイカーはすべての男女にとって真の選好を表明することが最適戦略になるようなメカニズムを設計する必要があります。このような性質を誘因両立性(incentive compatibility)と呼びます。誘因両立的なメカニズムのもとで各人はみずから進んで真の選好を正直に表明することになり、結果としてマッチメイカーは真の選好の組を得ます。さらに、メカニズムが誘因両立性を満たすと同時に、エージェントたちの選好の組に対して何らかの意味で望ましいマッチングを定めるものとしましょう。このようなメカニズムのもとではインセンティブの問題と最適配分問題が同時に解決されるため、真の意味で望ましいマッチングが得られることになります。では、そのようなメカニズムはの設計は可能でしょうか。また、可能な場合にはそれは具体的にどのようなメカニズムでしょうか。以降ではこれらの問題について順番に考えていきます。

次回はマッチングの望ましさの基準の 1 つである個人合理性(individual rationality)について解説します。
次へ進む

 

演習問題

先に定義した関数 randommatching が生成するマッチングでは、異性と結婚せずに独身のままでいるようなエージェントの存在を認めました。そこで、この関数に手を加えて、全員が必ず異性と結婚するようなマッチングをランダムに生成する形にしてください。ただし、入力する男女の人数は同数であるものとします。
解答を見る(プレミアム会員限定)