絶望の定理（僻地病院の定理）
1対1のマッチング問題の私的価値モデルにおいて、任意のエージェントの選好が完備性、推移性、狭義選好の仮定を満たす場合、安定マッチングが必ず存在するとともに、それは一意的であるとは限らないことが明らかになりました。複数の安定マッチングが存在する場合、その中のどれを選択すべきでしょうか。すでに明らかになったように、男性求婚型DAメカニズムが出力するマッチングはすべての男性にとって最も望ましい安定マッチングである一方で、すべての女性にとって最も望ましくない安定マッチングです。逆に、女性求婚型DAメカニズムが出力するマッチングはすべての男性にとって最も望ましくない安定マッチングである一方で、すべての女性にとって最も望ましい安定マッチングです。複数の安定マッチングが存在する場合、男女の間に明らかに利害の対立が存在します。
また、以下のような利害の対立も考えられます。あるエージェントは、誰ともマッチしないよりは何らかの異性とマッチしたいと考えているものとします。このエージェントは、ある安定マッチング\(\mu \)において異性とマッチできない一方で、別の安定マッチング\(\mu^{\prime }\)のもとでは異性とマッチできるものとします。このような場合、このエージェントにとって\(\mu \)よりも\(\mu ^{\prime }\)のほうが明らかに望ましく、したがって、\(\mu \)ではなく\(\mu^{\prime }\)を選び取るようなメカニズムを採用すべきであると主張するはずです。このような主張に正当性はあるでしょうか。
実は、任意の安定マッチングにおいて異性とマッチできるエージェントの顔ぶれは同じであることが保証されます。つまり、ある安定マッチングにおいて異性とマッチできないエージェントは、別の任意の安定マッチングにおいても異性とマッチできないことが確定しているということです。これを絶望の定理や僻地病院の定理（rural hospital theorem）などと呼びます。したがって、先の主張には正当性がありません。
まずはいくつか補題を示します。マッチング\(\mu \in M\)のもとで女性とマッチする男性からなる集合を、\begin{equation*}M\left( \mu \right) =\left\{ m\in M\ |\ \mu \left( m\right) \in W\right\}
\end{equation*}で表記し、\(\mu \)のもとで男性とマッチする女性からなる集合を、\begin{equation*}W\left( \mu \right) =\left\{ w\in W\ |\ \mu \left( w\right) \in M\right\}
\end{equation*}でそれぞれ表記します。以上を踏まえた上で、以下が成り立つことを示します。
_{m}\mu ^{\prime }\left( m\right) \right] \Rightarrow M\left( \mu ^{\prime
}\right) \subset M\left( \mu \right) \\
&&\left( b\right) \ \left[ \forall w\in W:\mu \left( w\right) \succsim
_{w}\mu ^{\prime }\left( w\right) \right] \Rightarrow W\left( \mu ^{\prime
}\right) \subset W\left( \mu \right)
\end{eqnarray*}がともに成り立つ。
つまり、2つの安定マッチング\(\mu ,\mu ^{\prime }\)が与えられたとき、すべての男性が\(\mu \)を\(\mu ^{\prime }\)よりも好む場合には、\(\mu^{\prime }\)において女性とマッチするすべての男性は\(\mu \)においても女性とマッチすることが保証されるということです。また、すべての女性が\(\mu \)を\(\mu ^{\prime }\)よりも好む場合には、\(\mu ^{\prime }\)において男性とマッチするすべての女性は\(\mu \)においても男性とマッチすることが保証されるということです。
1対1のマッチング問題においてエージェント集合\(M,W\)が有限集合であることを踏まえると、上の命題より以下を得ます。
_{m}\mu ^{\prime }\left( m\right) \right] \Rightarrow \left\vert M\left( \mu
^{\prime }\right) \right\vert \leq \left\vert M\left( \mu \right)
\right\vert \\
&&\left( b\right) \ \left[ \forall w\in W:\mu \left( w\right) \succsim
_{w}\mu ^{\prime }\left( w\right) \right] \Rightarrow \left\vert W\left( \mu
^{\prime }\right) \right\vert \leq \left\vert W\left( \mu \right)
\right\vert
\end{eqnarray*}がともに成り立つ。
男性求婚型DAメカニズム\(\phi ^{M}\)は男性最適安定メカニズムであり、女性求婚型DAメカニズム\(\phi ^{W}\)は女性最適安定メカニズムであることに加え、以上の2つの命題を踏まえると絶望の定理を証明することができます。
&&\left( b\right) \ W\left( \mu \right) =W\left( \mu ^{\prime }\right)
\end{eqnarray*}がともに成り立つ。
ペア安定性に関して絶望の定理は成立しない
マッチングが安定的であることは、それがペア安定的かつ個人合理的であることを意味します。したがって、絶望の定理とは、ペア安定的かつ個人合理的なマッチングを比較対象とした場合、それらのすべてのマッチングにおいて異性とマッチするエージェントの顔ぶれは常に一致するという主張です。
一方、個人合理的であるという条件を外した場合、絶望の定理は成立するとは限りません。つまり、ペア安定的なマッチングを比較対象とした場合、それらのマッチングにおいて異性とマッチするエージェントの顔ぶれは一致するとは限らないということです。以下の例より明らかです。
M &=&\left\{ m_{1},m_{2},m_{3}\right\} \\
W &=&\left\{ w_{1},w_{2},w_{3}\right\}
\end{eqnarray*}であるとともに、任意のエージェント\(i\in M\cup W\)の選好関係\(\succsim _{i}\)は完備性と推移性に加えて狭義選好の仮定を満たすものとします。具体的には、エージェントたちの選好プロファイル\(\succsim _{M\cup W}\)が以下の表によって与えられているものとします。
$$\begin{array}{ccccc}\hline
エージェント\diagdown 順位 & 1 & 2 & 3 & 4 \\ \hline
m_{1} & w_{2} & w_{1} & m_{1} & w_{3} \\ \hline
m_{2} & w_{1} & w_{2} & w_{3} & m_{2} \\ \hline
m_{3} & w_{1} & w_{2} & m_{3} & w_{3} \\ \hline
w_{1} & m_{1} & m_{3} & m_{2} & w_{1} \\ \hline
w_{2} & m_{2} & m_{1} & m_{3} & w_{2} \\ \hline
w_{3} & m_{1} & m_{3} & m_{2} & w_{3} \\ \hline
\end{array}$$
以下の2つのマッチング\begin{eqnarray*}
\mu &=&\begin{pmatrix}
m_{1} & m_{2} & m_{3} \\
w_{1} & w_{2} & w_{3}\end{pmatrix}
\\
\mu ^{\prime } &=&\begin{pmatrix}
m_{1} & m_{2} & m_{3} & w_{3} \\
w_{1} & w_{2} & m_{3} & w_{3}\end{pmatrix}\end{eqnarray*}はともに先の選好プロファイル\(\succsim _{M\cup W}\)のもとでペア安定的ですが、\(\mu \)においてすべてのエージェントが異性とマッチしているのに対して、\(\mu ^{\prime }\)において\(m_{3}\)と\(w_{3}\)は異性とマッチしていません。したがって、ペア安定性だけを要求する場合には絶望の定理は成立しません。ちなみに、\(\mu \)は個人合理的ではない一方で\(\mu ^{\prime }\)は個人合理的です。
プレミアム会員専用コンテンツです
【ログイン】【会員登録】