教材一覧
教材一覧
教材検索

1対1のマッチング問題

安定マッチングどうしの比較(男性最適安定性と女性最適安定性)

目次

Twitterで共有
メールで共有

安定的なマッチングは一意的であるとは限らない

1対1のマッチング問題私的価値モデルにおいて、任意のエージェントの選好が完備性、推移性、狭義選好の仮定を満たす場合、男性求婚型DAメカニズム女性求婚型メカニズムはともに安定メカニズム(個人合理的かつペア安定的)であることを示しました。ちなみに、同様の条件のもとで、あるメカニズムが安定的であることと広義コア選択メカニズムであることは必要十分であり、広義コア選択メカニズムは広義事後効率的でもあります。

男性求婚型DAメカニズムと女性DAメカニズムはともに安定メカニズムであるため、エージェントたちの選好プロファイルを入力すれば、ともに安定的なマッチングを1つずつ出力します。加えて、以下の例が示唆するように、これらのメカニズムが出力する安定マッチングは一致するとは限りません。つまり、同一の選好プロファイルに対して安定的なマッチングは一意的に定まるとは限らないということです。そのような場合、安定的なマッチングどうしを比較する動機が発生します。

例(複数の安定マッチング)
1対1のマッチング問題の私的価値モデルにおいて、エージェント集合が、\begin{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_{3} & w_{2} & w_{1} & m_{1} \\ \hline
m_{2} & w_{1} & w_{3} & w_{2} & m_{2} \\ \hline
m_{3} & w_{2} & w_{1} & w_{3} & m_{3} \\ \hline
w_{1} & m_{2} & m_{3} & m_{1} & w_{1} \\ \hline
w_{2} & m_{1} & m_{2} & m_{3} & w_{2} \\ \hline
w_{3} & m_{3} & m_{1} & m_{2} & w_{3} \\ \hline
\end{array}$$

表:エージェントの選好

以上の選好プロファイル\(\succsim _{M\cup W}\)に対して男性求婚型DAメカニズム\(\phi ^{M}\)が定めるマッチングは、\begin{equation*}\phi ^{M}\left( \succsim _{M\cup W}\right) =\begin{pmatrix}
m_{1} & m_{2} & m_{3} \\
w_{3} & w_{1} & w_{2}\end{pmatrix}\end{equation*}である一方で、同じ選好プロファイル\(\succsim_{M\cup W}\)に対して女性求婚型DAメカニズム\(\phi ^{W}\)が定めるマッチングは、\begin{equation*}\phi ^{W}\left( \succsim _{M\cup W}\right) =\begin{pmatrix}
m_{1} & m_{2} & m_{3} \\
w_{2} & w_{1} & w_{3}\end{pmatrix}\end{equation*}となります。明らかに、\begin{equation*}
\phi ^{M}\left( \succsim _{M\cup W}\right) \not=\phi ^{W}\left( \succsim
_{M\cup W}\right)
\end{equation*}です。ただし、2つのメカニズム\(\phi ^{M},\phi ^{W}\)はともに安定メカニズムであるため、以上の2つのマッチング\(\phi ^{W}\left(\succsim _{M\cup W}\right) ,\phi ^{w}\left( \succsim _{M\cup W}\right) \)はともに\(\succsim _{M\cup W}\)のもとで安定的です。では、どちらのほうが望ましいでしょうか。男性の視点から見ると、\begin{eqnarray*}\phi _{m_{1}}^{M}\left( \succsim _{M\cup W}\right) &=&w_{3}\succ
_{m_{1}}w_{2}=\phi _{m_{1}}^{W}\left( \succsim _{M\cup W}\right) \\
\phi _{m_{2}}^{M}\left( \succsim _{M\cup W}\right) &=&w_{1}\sim
_{m_{2}}w_{1}=\phi _{m_{2}}^{W}\left( \succsim _{M\cup W}\right) \\
\phi _{m_{3}}^{M}\left( \succsim _{M\cup W}\right) &=&w_{2}\succ
_{m_{2}}w_{3}=\phi _{m_{3}}^{W}\left( \succsim _{M\cup W}\right)
\end{eqnarray*}が成立しています。つまり、すべての男性にとって、男性求婚型DAメカニズムが定める安定マッチングは女性求婚型DAメカニズムが定める安定マッチング以上に望ましいということです。逆に、女性の視点から見ると、\begin{eqnarray*}
\phi _{w_{1}}^{W}\left( \succsim _{M\cup W}\right) &=&m_{2}\sim
_{w_{1}}m_{2}=\phi _{w_{1}}^{M}\left( \succsim _{M\cup W}\right) \\
\phi _{w_{2}}^{W}\left( \succsim _{M\cup W}\right) &=&m_{1}\succ
_{w_{2}}m_{3}=\phi _{w_{2}}^{M}\left( \succsim _{M\cup W}\right) \\
\phi _{w_{3}}^{W}\left( \succsim _{M\cup W}\right) &=&m_{3}\succ
_{w_{3}}m_{1}=\phi _{w_{3}}^{M}\left( \succsim _{M\cup W}\right)
\end{eqnarray*}が成立しています。つまり、すべての女性たちにとって、女性求婚型DAメカニズムが定める安定マッチングは男性求婚型DAメカニズムが定める安定マッチング以上に望ましいということです。

すべての男性にとって、男性求婚型DAメカニズムが定める安定マッチングは女性求婚型DAメカニズムが定める安定マッチング以上に望ましく、逆に、すべての女性にとって、女性求婚型DAメカニズムが定める安定マッチングは男性求婚型DAメカニズムが定める安定マッチング以上に望ましいという現象は、上の例に限らず、一般的に成立します。実際には、すべての男性にとって男性求婚型DAメカニズムが定めるマッチングはすべての安定マッチングの中でも最も望ましい安定マッチングであり、逆に、すべての女性にとって女性求婚型DAメカニズムが定めるマッチングはすべての安定マッチングの中でも最も望ましい安定マッチングです。以下で順番に示します。

 

男性求婚型DAメカニズムは男性最適安定メカニズム

引き続き、1対1のマッチング問題の私的価値モデルにおいて、任意のエージェントの選好が完備性、推移性、および狭義選好の仮定を満たすものとします。選好プロファイル\(\succsim _{M\cup W}\in \mathcal{R}_{M\cup W}\)を任意に選んだ上で、\(\succsim _{M\cup W}\)のもとで安定的であるようなマッチングをすべて集めてできる集合を、\begin{equation*}S\left( \succsim _{M\cup W}\right) \subset \mathcal{M}
\end{equation*}で表記します。選好プロファイル\(\succsim _{M\cup W}\)に対して男性求婚型DAメカニズム\(\phi ^{M}\)を適用すれば1つのマッチング\(\phi ^{M}\left( \succsim _{M\cup W}\right) \)が必ず得られるとともに、\(\phi ^{M}\)の安定性より、\(\phi ^{M}\left(\succsim _{M\cup W}\right) \)が\(\succsim _{M\cup W}\)のもとで安定的なマッチングであることが保証されます。女性求婚型DAメカニズム\(\phi ^{W}\)についても同様です。したがって、\begin{equation*}\forall \succsim _{M\cup W}\in \mathcal{R}_{M\cup W}:S\left( \succsim
_{M\cup W}\right) \not=\phi
\end{equation*}が成り立つこと、すなわち安定マッチングが常に存在することが保証されます。

選好プロファイル\(\succsim_{M\cup W}\)のもとでの安定マッチング集合\(S\left( \succsim _{M\cup W}\right) \)に属する安定マッチングどうしを比較したとき、すべての男性にとって、ある安定マッチング\(\mu \in S\left(\succsim _{M\cup W}\right) \)がすべての安定マッチングの中でも最も望ましい場合には、すなわち、\begin{equation*}\forall m\in M,\ \forall \mu ^{\prime }\in S\left( \succsim _{M\cup
W}\right) :\mu \left( m\right) \succsim _{m}\mu ^{\prime }\left( m\right)
\end{equation*}が成り立つ場合には、このような安定マッチング\(\mu \)を\(\succsim _{M\cup W}\)のもとでの男性最適安定マッチング(men optimalstable matching)と呼びます。さらに、選好プロファイル\(\succsim _{M\cup W}\in \mathcal{R}_{M\cup W}\)を任意に選んだとき、それに対してメカニズム\(\phi \)が定めるマッチング\(\phi \left( \succsim _{M\cup W}\right) \)が\(\succsim _{M\cup W}\)のもとで男性最適安定マッチングであることが保証される場合には、すなわち、\(\succsim _{M\cup W}\in \mathcal{R}_{M\cup W}\)を任意に選んだときに\(\phi \left( \succsim _{M\cup W}\right) \in S\left( \succsim _{M\cup W}\right) \)が成り立つとともに、さらに、\begin{equation*}\forall m\in M,\ \forall \mu \in S\left( \succsim _{M\cup W}\right) :\phi
_{m}\left( \succsim _{M\cup W}\right) \succsim _{m}\mu \left( m\right)
\end{equation*}が成り立つ場合には、このようなメカニズム\(\phi \)を男性最適安定メカニズム(men optimalstable mechanism)と呼びます。

男性求婚型DAメカニズムは男性最適安定メカニズムです。

命題(男性提案型DAメカニズムは男性最適安定メカニズム)
1対1のマッチング問題の私的価値モデルにおいて、任意のエージェントの選好が完備性、推移性、狭義選好の仮定を満たす場合、男性求婚型DAメカニズム\(\phi ^{M}\)は男性最適安定メカニズムとなる。
証明

プレミアム会員専用コンテンツです
ログイン】【会員登録

男性求婚型DAメカニズム\(\phi ^{M}\)はメカニズムであるため、選好プロファイルを入力したとき、必ず1つのマッチングを出力します。加えて、そのマッチングは入力した選好プロファイルのもとで男性最適安定マッチングであることが保証されます。したがって、選好プロファイルに関わらず、男性最適安定マッチングが存在することは保証されます。しかも、男性求婚型DAメカニズムが出力するマッチングとは異なるマッチングは男性最適安定マッチングにはならないため、男性最適安定マッチングは一意的です。

命題(男性最適安定マッチングの一意性)
1対1のマッチング問題の私的価値モデルにおいて、任意のエージェントの選好が完備性、推移性、狭義選好の仮定を満たすものとする。選好プロファイル\(\succsim _{M\cup W}\in \mathcal{R}_{M\cup W}\)を任意に選んだとき、\(\succsim _{M\cup W}\)のもとでの男性最適安定マッチングが1つずつ存在する。
証明

プレミアム会員専用コンテンツです
ログイン】【会員登録

 

女性求婚型DAメカニズムは女性最適安定メカニズム

選好プロファイル\(\succsim_{M\cup W}\)のもとでの安定マッチング集合\(S\left( \succsim _{M\cup W}\right) \)に属する安定マッチングどうしを比較したとき、すべての女性にとって、ある安定マッチング\(\mu \in S\left(\succsim _{M\cup W}\right) \)がすべての安定マッチングの中でも最も望ましい場合には、すなわち、\begin{equation*}\forall w\in W,\ \forall \mu ^{\prime }\in S\left( \succsim _{M\cup
W}\right) :\mu \left( w\right) \succsim _{w}\mu ^{\prime }\left( w\right)
\end{equation*}が成り立つ場合には、このような安定マッチング\(\mu \)を\(\succsim _{M\cup W}\)のもとでの女性最適安定マッチング(womenoptimal stable matching)と呼びます。さらに、選好プロファイル\(\succsim _{M\cup W}\in \mathcal{R}_{M\cup W}\)を任意に選んだとき、それに対してメカニズム\(\phi \)が定めるマッチング\(\phi \left( \succsim _{M\cup W}\right) \)が\(\succsim _{M\cup W}\)のもとで女性最適安定マッチングであることが保証される場合には、すなわち、\(\succsim _{M\cup W}\in \mathcal{R}_{M\cup W}\)を任意に選んだときに\(\phi \left( \succsim _{M\cup W}\right) \in S\left( \succsim _{M\cup W}\right) \)が成り立つとともに、さらに、\begin{equation*}\forall w\in W,\ \forall \mu \in S\left( \succsim _{M\cup W}\right) :\phi
_{w}\left( \succsim _{M\cup W}\right) \succsim _{w}\mu \left( w\right)
\end{equation*}が成り立つ場合には、このようなメカニズム\(\phi \)を女性最適安定メカニズム(womenoptimal stable mechanism)と呼びます。

女性求婚型DAメカニズムは女性最適安定メカニズムです。証明は男性求婚型DAメカニズムに関する先の命題と同様です。

命題(女性提案型DAメカニズムは女性最適安定メカニズム)
1対1のマッチング問題の私的価値モデルにおいて、任意のエージェントの選好が完備性、推移性、狭義選好の仮定を満たす場合、女性い求婚型DAメカニズム\(\phi ^{W}\)は女性最適安定メカニズムとなる。

男性最適安定マッチングと同様、女性最適安定マッチングもまた一意的です。

命題(女性最適安定マッチングの一意性)
1対1のマッチング問題の私的価値モデルにおいて、任意のエージェントの選好が完備性、推移性、狭義選好の仮定を満たすものとする。選好プロファイル\(\succsim _{M\cup W}\in \mathcal{R}_{M\cup W}\)を任意に選んだとき、\(\succsim _{M\cup W}\)のもとでの女性最適安定マッチングが1つずつ存在する。

最適安定メカニズム\(\phi \)が誘因両立性を満たす場合、均衡配分\(\phi \left( \succsim _{M\cup W}\right) \)は真の状態\(\succsim _{M\cup W}\)のもとで最適安定的であることが保証されます。一方、最適安定メカニズム\(\phi \)のもとでのベイジアンゲーム\(G\left( \phi \right) \)に均衡が存在することを前提としない場合、マッチング\(\phi \left(\succsim _{M\cup W}\right) \)はエージェントたちが申告する選好プロファイル\(\succsim _{M\cup W}\)のもとで最適安定的です。後に示すように、DAメカニズムは誘因両立性を満たさないため、上の2つの命題は後者の意味合いにとどまります。

 

男性最適安定マッチングと女性最適安定マッチングの支配関係

繰り返しになりますが、男性求婚型DAメカニズム\(\phi ^{M}\)は男性最適安定メカニズムであるため、選好プロファイル\(\succsim _{M\cup W}\in \mathcal{R}_{M\cup W}\)を任意に選んだとき、\begin{equation}\forall m\in M,\ \forall \mu \in S\left( \succsim _{M\cup W}\right) :\phi
_{m}^{M}\left( \succsim _{M\cup W}\right) \succsim _{m}\mu \left( m\right)
\quad \cdots (1)
\end{equation}という関係が成り立ちます。加えて、女性求婚型DAメカニズム\(\phi ^{W}\)は安定メカニズムであることから、\begin{equation}\phi ^{W}\left( \succsim _{M\cup W}\right) \in S\left( \succsim _{M\cup
W}\right) \quad \cdots (2)
\end{equation}が成り立ちます。\(\left(1\right) ,\left( 2\right) \)より、\begin{equation*}\forall m\in M:\phi _{m}^{M}\left( \succsim _{M\cup W}\right) \succsim
_{m}\phi _{m}^{M}\left( \succsim _{M\cup W}\right)
\end{equation*}を得ます。つまり、すべての男性にとって、男性求婚型DAメカニズムが定める安定マッチングは女性求婚型DAメカニズムが定める安定マッチング以上に望ましいということです。では、すべての男性からなる提携\(M\)にとって\(\phi ^{M}\left(\succsim _{M\cup W}\right) \)は\(\phi ^{W}\left( \succsim _{M\cup W}\right) \)を広義にパレート支配するとまで言えるのでしょうか。つまり、\begin{eqnarray*}&&\left( a\right) \ \exists m\in M:\phi _{m}^{M}\left( \succsim _{M\cup
W}\right) \succ _{m}\phi _{m}^{M}\left( \succsim _{M\cup W}\right) \\
&&\left( b\right) \ \forall m\in M:\phi _{m}^{M}\left( \succsim _{M\cup
W}\right) \succsim _{m}\phi _{m}^{M}\left( \succsim _{M\cup W}\right)
\end{eqnarray*}がともに成り立つことを保証できるのでしょうか。選好プロファイル\(\succsim _{M\cup W}\)に対して男性求婚型DAメカニズムが定めるマッチング\(\phi ^{M}\left( \succsim _{M\cup W}\right) \)と女性求婚型DAメカニズムが定めるマッチング\(\phi ^{W}\left( \succsim _{M\cup W}\right) \)が異なる場合には、すなわち、\begin{equation*}\phi ^{M}\left( \succsim _{M\cup W}\right) \not=\phi ^{W}\left( \succsim
_{M\cup W}\right)
\end{equation*}が成り立つ場合には主張が成り立ちます。ただ、同一の選好プロファイルに対して2つのメカニズムが同一のマッチングを導くことがあるため、すなわち、\begin{equation*}
\phi ^{M}\left( \succsim _{M\cup W}\right) =\phi ^{W}\left( \succsim _{M\cup
W}\right)
\end{equation*}が成り立つ場合は起こり得るため、そのような場合には、\begin{equation*}
\forall m\in M:\phi _{m}^{M}\left( \succsim _{M\cup W}\right) \sim _{m}\phi
_{m}^{M}\left( \succsim _{M\cup W}\right)
\end{equation*}となり、主張は成り立ちません。

男性求婚型DAメカニズムと女性求婚型DAメカニズムの立場を逆にした議論もまた成り立ちます。

 

演習問題

問題(安定マッチングの比較)
1対1のマッチング問題の私的価値モデルにおいて、エージェント集合が、\begin{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_{3} & w_{2} & w_{1} & m_{1} \\ \hline
m_{2} & w_{1} & w_{3} & w_{2} & m_{2} \\ \hline
m_{3} & w_{2} & w_{1} & w_{3} & m_{3} \\ \hline
w_{1} & m_{2} & m_{3} & m_{1} & w_{1} \\ \hline
w_{2} & m_{1} & m_{2} & m_{3} & w_{2} \\ \hline
w_{3} & m_{3} & m_{1} & m_{2} & w_{3} \\ \hline
\end{array}$$

表:エージェントの選好

以上の選好プロファイル\(\succsim _{M\cup W}\)のもとでの安定マッチングをすべて求めた上で、その中でも男性求婚型DAメカニズムが導くマッチング\(\phi ^{M}\left( \succsim _{M\cup W}\right) \)は男性最適安定的であり、女性求婚型DAメカニズムが導くマッチング\(\phi ^{W}\left( \succsim _{M\cup W}\right) \)は女性最適安定的であることを確認してください。

解答を見る

プレミアム会員専用コンテンツです
ログイン】【会員登録

Twitterで共有
メールで共有