安定結婚問題のマッチングにおいて、すべてのエージェントが独身よりも望ましい異性とマッチしているかもしくは独身ならば、そのマッチングは個人合理的であると言います。また、エージェントたちが申告する選好の組に対してメカニズムが定めるマッチングが常に個人合理的ならば、そのようなメカニズムは個人合理的であると言います。

2019年3月13日:公開

個人合理的なマッチング

安定結婚問題を構成する男性の集合が\(M\)、女性の集合が\(W\)、それぞれのエージェント\(i\in M\cup W\)の選好が\(\succ _{i}\)で表されるものとします。また、マッチング\(\mu :M\cup W\rightarrow M\cup W\)においてエージェント\(i\)とマッチする相手を\(\mu \left( i\right) \)で表します。特に\(\mu \left( i\right) =i\)が成り立つことは、つまりエージェント\(i\)がマッチング\(\mu \)において自分自身とマッチすることは、\(i\)は\(\mu \)において独身であることを意味します。

エージェント\(i\)にとって独身であることよりもエージェント\(j\)と結婚することのほうが望ましいならば、すなわち、\begin{equation*}
j\succ _{i}i
\end{equation*}が成り立つならば、\(i\)にとって\(j\)は受容可能(acceptable)であると言います。逆に、エージェント\(i\)にとってエージェント\(j\)と結婚することよりも独身のほうが望ましいならば、すなわち、\begin{equation*}
i\succ _{i}j
\end{equation*}が成り立つならば、\(i\)にとって\(j\)は受容不可能(unacceptable)であると言います。

マッチング\(\mu \)のもとで任意のエージェントが受容可能な異性とマッチしているかもしくは独身ならば、すなわち、\begin{equation*}
\forall i\in M\cup W:\left[ \mu \left( i\right) \succ _{i}i\ \vee \ \mu \left( i\right) =i\right] \end{equation*}が成り立つならば、\(\mu\)は個人合理的(individually rational)であると言います。

マッチング\(\mu \)において受容不可能な相手とマッチしているエージェントが存在する場合には、すなわち、\begin{equation*}
\exists i\in M\cup W:i\succ _{i}\mu \left( i\right)
\end{equation*}が成り立つ場合には、エージェント\(i\)はマッチング\(\mu \)をブロックする(block)と言います。マッチング\(\mu\)をブロックするエージェントが存在するとき、\(\mu \)は明らかに個人合理的ではありません。

マッチメイカーが何らかのルールにもとづいて決定したマッチング\(\mu \)をブロックするエージェント\(i\)が存在するとき、\(i\)は\(\mu \)に従うと受容不可能な相手と結婚することになるため、\(i\)はマッチメイカーの決定に従わず独身のままでいたほうがマシです。したがって、このようなマッチングは維持可能ではありません。一方、マッチメイカーが定めるマッチング\(\mu \)が個人合理的ならば、それをブロックするエージェントは存在せず、任意のエージェントが直面する結果は独身以上です。したがって、個人合理的なマッチングは維持可能です。

例(個人合理的なマッチング)
男性の集合を\(M=\{m_{1},m_{2},m_{3}\}\)とし、女性の集合を\(W=\{w_{1},w_{2},w_{3}\}\)とします。それぞれのエージェントの選好が、\begin{eqnarray*}
&\succ &_{m_{1}}:w_{1},w_{2},m_{1},w_{3} \\
&\succ &_{m_{2}}:w_{2},m_{2},w_{3},w_{1} \\
&\succ &_{m_{3}}:w_{1},w_{2},w_{3},m_{3} \\
&\succ &_{w_{1}}:m_{1},m_{2},w_{1},m_{3} \\
&\succ &_{w_{2}}:m_{1},m_{2},w_{2},m_{3} \\
&\succ &_{w_{3}}:m_{1},m_{2},m_{3},w_{3}
\end{eqnarray*}で与えられているものとします。このとき、以下のマッチング\begin{equation*}
\mu =\begin{pmatrix}
m_{1} & m_{2} & m_{3} \\
w_{1} & w_{2} & w_{3}\end{pmatrix}\end{equation*}において全員が受容可能な相手とマッチしているため、\(\mu \)は個人合理的です。また、以下のマッチング\begin{equation*}
\mu ^{\prime }=\begin{pmatrix}
m_{1} & m_{2} & m_{3} & w_{3} \\
w_{1} & w_{2} & m_{3} & w_{3}\end{pmatrix}\end{equation*}において全員が受容可能な相手とマッチするか独身のどちらか一方であるため、\(\mu ^{\prime }\)は個人合理的です。一方、以下のマッチング\begin{equation*}
\mu ^{\prime \prime }=\begin{pmatrix}
m_{1} & m_{2} & m_{3} \\
w_{2} & w_{3} & w_{1}\end{pmatrix}\end{equation*}において、例えば\(m_{2}\)にとって\(\mu ^{\prime \prime }\)のもとでマッチする相手\(w_{3}\)は受容可能でないため、\(\mu ^{\prime \prime }\)は\(m_{2}\)にブロックされます。したがって\(\mu ^{\prime \prime }\)は個人合理的ではありません。

 

個人合理的なメカニズム

マッチメイカーはすべてのエージェントに自身の選好を申告させた上で、何らかのルールにもとづいてマッチングを決定します。エージェントたちが申告した選好の組に対してマッチングを定めるルールをメカニズム(mechanism)と呼びます。さらに、エージェントたちが申告する選好の組に対してメカニズムが定めるマッチングが常に個人合理的ならば、そのようなメカニズムは個人合理的(individually rational)であると言います。

以下では個人合理的ではないメカニズムの例を挙げましょう。

例(抽選)
男性の集合を\(M=\{m_{1},m_{2},m_{3}\}\)とし、女性の集合を\(W=\{w_{1},w_{2},w_{3}\}\)とします。それぞれのエージェントの選好が、\begin{eqnarray*}
&\succ &_{m_{1}}:w_{1},w_{2},m_{1},w_{3} \\
&\succ &_{m_{2}}:w_{2},m_{2},w_{3},w_{1} \\
&\succ &_{m_{3}}:w_{1},w_{2},w_{3},m_{3} \\
&\succ &_{w_{1}}:m_{2},w_{1},m_{3},m_{1} \\
&\succ &_{w_{2}}:m_{1},m_{2},w_{2},m_{3} \\
&\succ &_{w_{3}}:m_{1},m_{2},m_{3},w_{3}
\end{eqnarray*}で与えられており、エージェントたちは上の選好をそのまま申告するものと仮定します。ここで、以下のようなメカニズムについて考えます。

  1. クジによって6人に順番をつける。
  2. 1 番目の人は最も望ましい相手(もしくは独身)とマッチする。
  3. まだ誰ともマッチしていない人の中で最も順番の早い人は、誰ともマッチしていない人の中から最も望ましい相手(もしくは独身)とマッチする。
  4. 以降も同様。

クジによって決められた順番が\(m_{1},w_{1},m_{2},w_{2},m_{3},w_{3}\)であるものとしましょう。このとき、まずは\(m_{1}\)が\(w_{1}\)とマッチし、次に\(m_{2}\)が\(w_{2}\)とマッチし、最後に\(m_{3}\)が\(w_{3}\)とマッチします。最終的に得られるマッチングは、\begin{equation*}
\mu =\begin{pmatrix}
m_{1} & m_{2} & m_{3} \\
w_{1} & w_{2} & w_{3}\end{pmatrix}\end{equation*}ですが、例えば\(w_{1}\)は\(\mu \)をブロックするため、\(\mu \)は個人合理的ではありません。したがって、このメカニズムは個人合理的ではありません。

では、個人合理的なメカニズムは存在するのでしょうか。また存在する場合、それは具体的にどのようなメカニズムでしょうか。この問題については場を改めて考えます。

 

Python による個人合理性の判定

後の便宜のために、入力したエージェントたちの選好とマッチングに対して、そのマッチングが個人合理的であるか否かを判定する関数を定義します。

まずは、先の例で用いた選好を以下のような辞書として定式化します。menspreferences は男性たちの選好、womenspreferences は女性たちの選好を表す辞書です。

同じく先の例で用いたマッチング\(\mu ,\mu ^{\prime },\mu ^{\prime \prime }\)をそれぞれ以下のような辞書として定式化します。辞書
matching_a は\(\mu \)に、辞書 matching_b は\(\mu ^{\prime }\)に、辞書 matching_c は\(\mu ^{\prime \prime }\)にそれぞれ対応しています。

選好とマッチングを入力し、マッチングをブロックするエージェントからなる集合を返す関数を以下のように定義します。

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

keys メソッドは辞書のキーからなるリストを取得します。具体的には、\begin{equation*}
\text{x.keys()}
\end{equation*}と記述すると、辞書 x のキーからなるリストを取得します。

index メソッドはリストの要素に対してインデックスを返します。具体的には、\begin{equation*}
\text{x.index(y)}
\end{equation*}と記述すると、リスト x に含まれる要素 y のインデックスを取得します。今回の例では選好をリストを用いて表現し、より望ましいマッチ相手にはより小さいインデックスが与えられているため、インデックスを比較することでどちらがより望ましいマッチ相手であるかを判定できます。

items メソッドは辞書に対してキーと値の組からなるリストを返します。具体的には、\begin{equation*}
\text{x.items()}
\end{equation*}と記述すると、辞書 x に含まれるキーと値の組を要素とするリストを取得します。上の例ではマッチングを表す辞書 matching に対して、男性と結婚している女性 she の男性 husband を取得するためにこのメソッドを利用しています。一般に、辞書に対して値を指定し、その値に対応するキーを取得するためには、上の例のように foritems メソッドを組み合わせて対応します。解説は以上です。

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

最後に、以前定義した選好をランダムに生成する関数 preference、マッチングをランダムに生成する関数 matching と今回定義した個人合理性を判定する関数 ircheck を組み合わせて、ランダムに生成した選好とマッチングに対して、マッチングの個人合理性を判定する一連の処理を定義します。

次回はマッチングの望ましさの基準の 1 つであるペア安定性(pairwise stability)について解説します。
次へ進む