男性求婚型DAメカニズム
1対1のマッチング問題におけるメカニズムとは、エージェントたちが申告する選好からなる組\(\succsim _{M\cup W}\in \mathcal{R}_{M\cup W}\)に対して、何らかのマッチング\begin{equation*}\phi \left( \succsim _{M\cup W}\right) =\left( \phi _{i}\left( \succsim
_{M\cup W}\right) \right) _{i\in M\cup W}\in \mathcal{M}
\end{equation*}を1つずつ選ぶ写像\(\phi :\mathcal{R}_{M\cup W}\rightarrow \mathcal{M}\)として定式化されます。メカニズムを設計することとは、この写像\(\phi \)の具体的な形状を定めることを意味します。今回は、1対1のマッチング問題における代表的なメカニズムである受入保留メカニズム（deferred-acceptancemechanism）について解説します。これは受入保留アルゴリズム（deferred-acceptance algorithm）やゲール＝シャプレーアルゴリズム（Gale-Shapley algorithm）などと呼ばれることもありますが、以降ではDAメカニズム（DA mechanism）と呼ぶこととします。
DAメカニズムについて分析する際には、多くの場合、私的価値モデルを分析対象にします。つまり、エージェントの選好について非外部性と私的価値の仮定を置くということです。この場合、任意のエージェント\(i\in M\cup W\)と任意のマッチング\(\mu ,\mu ^{\prime }\in \mathcal{M}\)に対して、\begin{equation*}\mu \succsim _{i}^{\mathcal{M}}\left[ \succsim _{M\cup W}\right] \ \mu
^{\prime }\Leftrightarrow \mu \left( i\right) \succsim _{i}\mu ^{\prime
}\left( i\right)
\end{equation*}という関係が成り立つため、エージェント\(i\)がマッチングどうしを比較する選好\(\succsim_{i}^{\mathcal{M}}\left[ \succsim _{M\cup W}\right] \)について考えるかわりに、エージェント\(i\)がマッチし得る相手どうしを比較する選好\(\succsim _{i}\)について考えても一般性は失われません。さらに、それぞれのエージェント\(i\)がマッチし得る相手どうしを比較する\(\succsim _{i}\)が完備性、推移性、さらに狭義選好の仮定を満たすものとします。この場合、エージェント\(i\)はマッチし得るすべての相手を狭義選好\(\succ _{i}\)だけを用いて一列に並べることができます。つまり、マッチし得るすべての対象を最も望ましい相手から最も望ましくない相手まで順番に並べることができ、なおかつ、その中に同じ程度望ましい複数の相手は存在しないことを仮定するということです。
以上を踏まえた上で、まずは男性求婚型DAメカニズム（man-proposing DA mechanism）と呼ばれるメカニズム\(\phi ^{M}\)を以下のように定義します。
- 【ステップ\(1\)】エージェントたちが申告する選好の組が\(\succsim _{M\cup W}=\left( \succsim _{i}\right) _{i\in M\cup W}\)であるものとする。それぞれの男性\(m\in M\)は、自身が申告した選好\(\succsim _{m}\)のもとで、未婚のままでいることに相当する選択肢\(m\)以上に望ましいすべての女性の中で最も望ましい1人の女性に求婚する。\(m\)以上に望ましい女性がいない場合には\(m\)を選択する。それぞれの女性\(w\in W\)は、自身が申告した選好\(\succsim _{w}\)のもとで、未婚のままでいることに相当する選択肢\(w\)より望ましくない求婚者がいる場合には、そのような男性からの求婚をすべて断る。また、\(w\)以上に望ましい求婚者がいる場合には、その中で最も望ましい男性と婚約し、その他の求婚者からの求婚をすべて断る。求婚者がいない場合には何もしない。求婚を断られた男性が存在する場合には次のステップへ進む。そのような男性が存在しない場合にはプロセスを終了する。
- 【ステップ\(2\)】ステップ\(1\)において求婚を断られたそれぞれの男性\(m\in M\)は、自身が申告した選好\(\succsim _{m}\)のもとで、\(m\)以上に望ましく、なおかつ自身からの求婚をまだ断っていない女性の中で最も望ましい1人の女性に求婚する。\(m\)以上に望ましい女性がいない場合には\(m\)を選択する。それ以外の男性は何もしない。それぞれの女性\(w\in W\)は、自身が申告した選好\(\succsim _{w}\)のもとで、\(w\)より望ましくない求婚者がいる場合には、そのような男性からの求婚をすべて断る。また、婚約者や\(w\)以上に望ましい求婚者がいる場合には、その中で最も望ましい男性と婚約し、その他の婚約者および求婚者からの婚約および求婚をすべて断る。求婚者がいない場合には何もしない。求婚を断られた男性や婚約を解消された男性が存在する場合には次のステップへ進む。そのような男性が存在しない場合にはプロセスを終了する。
- 【ステップ\(k\)】以上のプロセスを繰り返す。各ステップ\(k\)の内容は以下のように一般化される。直前のステップ\(k-1\)において求婚を断られた、もしくは婚約を解消された男性\(m\in M\)は、自身が申告した選好\(\succsim _{m}\)のもとで、\(m\)以上に望ましく、なおかつ自身からの求婚をまだ断っていない女性の中で最も望ましい1人の女性に求婚する。\(m\)以上に望ましい女性がいない場合には\(m\)を選択する。それ以外の男性は何もしない。それぞれの女性\(w\in W\)は、自身が申告した選好\(\succsim _{w}\)のもとで、\(w\)より望ましくない求婚者がいる場合には、そのような男性からの求婚をすべて断る。また、婚約者や\(w\)以上に望ましい求婚者がいる場合には、その中で最も望ましい男性と婚約し、その他の婚約者および求婚者からの婚約および求婚をすべて断る。求婚者がいない場合には何もしない。求婚を断られた男性や婚約を解消された男性が存在する場合には次のステップへ進む。そのような男性が存在しない場合にはプロセスを終了する。
- プロセスの終了後、それぞれのエージェント\(i\in M\cup W\)は、その時点において婚約している異性\(j\in M\cup W\)と結婚する。すなわち、\(\phi _{i}^{M}\left( \succsim _{M\cup W}\right) =j\)と定める。その時点において異性と婚約していないそれぞれのエージェント\(i\in M\cup W\)は未婚のままとする。すなわち、\(\phi _{i}^{M}\left( \succsim _{M\cup W}\right) =i\)と定める。その結果、男性求婚型DAメカニズムが定めるマッチング\(\phi ^{M}\left( \succsim _{M\cup W}\right) \)が得られる。
M &=&\left\{ m_{1},m_{2},m_{3},m_{4}\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}{cccccc}\hline
エージェント\diagdown 順位 & 1 & 2 & 3 & 4 & 5 \\ \hline
m_{1} & w_{1} & w_{2} & w_{3} & m_{1} & – \\ \hline
m_{2} & w_{2} & w_{3} & w_{1} & m_{2} & – \\ \hline
m_{3} & w_{3} & w_{1} & w_{2} & m_{3} & – \\ \hline
m_{4} & w_{3} & w_{2} & m_{4} & w_{1} & – \\ \hline
w_{1} & m_{1} & m_{2} & m_{3} & m_{4} & w_{1} \\ \hline
w_{2} & m_{1} & m_{3} & m_{2} & w_{2} & m_{4} \\ \hline
w_{3} & m_{2} & m_{4} & m_{1} & w_{3} & m_{3} \\ \hline
\end{array}$$
以上の選好プロファイル\(\succsim _{M\cup W}\)に対して男性求婚型DAメカニズム\(\phi ^{M}\)が定めるマッチング\(\phi ^{M}\left( \succsim _{M\cup W}\right) \)を特定します。ステップ\(1\)における求婚は以下の通りです。\begin{equation*}m_{1}\rightarrow w_{1},\quad m_{2}\rightarrow w_{2},\quad m_{3}\rightarrow
w_{3},\quad m_{4}\rightarrow w_{3}
\end{equation*}\(w_{1}\)は\(m_{1}\)と婚約し、\(w_{2}\)は\(m_{2}\)と婚約し、\(w_{3}\)は\(m_{4}\)と婚約する一方で\(m_{3}\)からの求婚を断ります。その結果、以下の婚約関係\begin{equation*}\begin{pmatrix}
w_{1} & w_{2} & w_{3} \\
m_{1} & m_{2} & m_{4}\end{pmatrix}\end{equation*}が成立します。求婚を断られた男性\(m_{3}\)が存在するため次のステップへ進みます。ステップ\(2\)における求婚は以下の通りです。\begin{equation*}m_{3}\rightarrow w_{1}
\end{equation*}\(w_{1}\)は婚約者\(m_{1}\)と求婚者\(m_{3}\)を比較した上で、\(m_{1}\)との婚約を維持する一方で\(m_{3}\)からの求婚を断ります。その結果、以下の婚約関係\begin{equation*}\begin{pmatrix}
w_{1} & w_{2} & w_{3} \\
m_{1} & m_{2} & m_{4}\end{pmatrix}\end{equation*}が成立します。求婚を断られた男性\(m_{3}\)が存在するため次のステップへ進みます。ステップ\(3\)における求婚は以下の通りです。\begin{equation*}m_{3}\rightarrow m_{2}
\end{equation*}\(w_{2}\)は婚約者\(m_{2}\)と求婚者\(m_{3}\)を比較した上で、\(m_{3}\)と婚約する一方で\(m_{2}\)との婚約を解消します。その結果、以下の婚約関係\begin{equation*}\begin{pmatrix}
w_{1} & w_{2} & w_{3} \\
m_{1} & m_{3} & m_{4}\end{pmatrix}\end{equation*}が成立します。婚約を解消された男性\(m_{2}\)が存在するため次のステップへ進みます。ステップ\(4\)における求婚は以下の通りです。\begin{equation*}m_{2}\rightarrow w_{3}
\end{equation*}\(w_{3}\)は婚約者\(m_{4}\)と求婚者\(m_{2}\)を比較した上で、\(m_{2}\)と婚約する一方で\(m_{4}\)との婚約を解消します。その結果、以下の婚約関係\begin{equation*}\begin{pmatrix}
w_{1} & w_{2} & w_{3} \\
m_{1} & m_{3} & m_{2}\end{pmatrix}\end{equation*}が成立します。婚約を解消された男性\(m_{4}\)が存在するため次のステップへ進みます。ステップ\(5\)における求婚は以下の通りです。\begin{equation*}m_{4}\rightarrow w_{2}
\end{equation*}\(w_{2}\)は婚約者\(m_{3}\)と求婚者\(m_{4}\)を比較した上で、\(m_{3}\)との婚約を維持する一方で\(m_{4}\)からの求婚を断ります。その結果、以下の婚約関係\begin{equation*}\begin{pmatrix}
w_{1} & w_{2} & w_{3} \\
m_{1} & m_{3} & m_{2}\end{pmatrix}\end{equation*}が成立します。求婚を断られた男性\(m_{4}\)が存在するため次のステップへ進みます。ステップ\(6\)における求婚は以下の通りです。\begin{equation*}m_{4}\rightarrow m_{4}
\end{equation*}求婚を断られたり婚約を解消された男性は存在しないためプロセスを終了します。最終的に得られるマッチングは、\begin{equation*}
\phi ^{M}\left( \succsim _{M\cup W}\right) =\begin{pmatrix}
w_{1} & w_{2} & w_{3} & m_{4} \\
m_{1} & m_{3} & m_{2} & m_{4}\end{pmatrix}\end{equation*}となります。
男性求婚型DAメカニズムを運用する際には、プロセスの冒頭においてエージェントたちは自身の選好を申告し、以降は、申告された選好プロファイルに対して以上のプロセスを機械的に適用することによりマッチングを導くことになります。エージェントたちは各ステップにおいて繰り返し選好を申告するわけではなく、冒頭に1度だけ申告するということです。
女性求婚型DAメカニズム
男性求婚型DAメカニズムでは男性が女性に対して求婚する構造になっていますが、男女の役割を逆にしたメカニズムを考えることもできます。これを女性求婚型DAメカニズム（woman-proposing DA mechanism）と呼びます。女性求婚型メカニズム\(\phi ^{W}\)を以下のように定義します。
- 【ステップ\(1\)】エージェントたちが申告する選好の組が\(\succsim _{M\cup W}=\left( \succsim _{i}\right) _{i\in M\cup W}\)であるものとする。それぞれの女性\(w\in W\)は、自身が申告した選好\(\succsim _{w}\)のもとで、未婚のままでいることに相当する選択肢\(w\)以上に望ましいすべての男性の中で最も望ましい1人の男性に求婚する。\(w\)以上に望ましい男性がいない場合には\(w\)を選択する。それぞれの男性\(m\in M\)は、自身が申告した選好\(\succsim _{m}\)のもとで、未婚のままでいることに相当する選択肢\(m\)より望ましくない求婚者がいる場合には、そのような女性からの求婚をすべて断る。また、\(m\)以上に望ましい求婚者がいる場合には、その中で最も望ましい女性と婚約し、その他の求婚者からの求婚をすべて断る。求婚者がいない場合には何もしない。求婚を断られた女性が存在する場合には次のステップへ進む。そのような女性が存在しない場合にはプロセスを終了する。
- 【ステップ\(2\)】ステップ\(1\)において求婚を断られたそれぞれの女性\(w\in W\)は、自身が申告した選好\(\succsim _{w}\)のもとで、\(w\)以上に望ましく、なおかつ自身からの求婚をまだ断っていない男性の中で最も望ましい1人の男性に求婚する。\(w\)以上に望ましい男性がいない場合には\(w\)を選択する。それ以外の女性は何もしない。それぞれの男性\(m\in M\)は、自身が申告した選好\(\succsim _{m}\)のもとで、\(m\)より望ましくない求婚者がいる場合には、そのような女性からの求婚をすべて断る。また、婚約者や\(m\)以上に望ましい求婚者がいる場合には、その中で最も望ましい女性と婚約し、その他の婚約者および求婚者からの婚約および求婚をすべて断る。求婚者がいない場合には何もしない。求婚を断られた女性や婚約を解消された女性が存在する場合には次のステップへ進む。そのような女性が存在しない場合にはプロセスを終了する。
- 【ステップ\(k\)】以上のプロセスを繰り返す。各ステップ\(k\)の内容は以下のように一般化される。直前のステップ\(k-1\)において求婚を断られた、もしくは婚約を解消された女性\(w\in W\)は、自身が申告した選好\(\succsim _{w}\)のもとで、\(w\)以上に望ましく、なおかつ自身からの求婚をまだ断っていない男性の中で最も望ましい1人の男性に求婚する。\(w\)以上に望ましい男性がいない場合には\(w\)を選択する。それ以外の女性は何もしない。それぞれの男性\(m\in M\)は、自身が申告した選好\(\succsim _{m}\)のもとで、\(m\)より望ましくない求婚者がいる場合には、そのような女性からの求婚をすべて断る。また、婚約者や\(m\)以上に望ましい求婚者がいる場合には、その中で最も望ましい女性と婚約し、その他の婚約者および求婚者からの婚約および求婚をすべて断る。求婚者がいない場合には何もしない。求婚を断られた女性や婚約を解消された女性が存在する場合には次のステップへ進む。そのような女性が存在しない場合にはプロセスを終了する。
- プロセスの終了後、それぞれのエージェント\(i\in M\cup W\)は、その時点において婚約している異性\(j\in M\cup W\)と結婚する。すなわち、\(\phi _{i}^{M}\left( \succsim _{M\cup W}\right) =j\)と定める。その時点において異性と婚約していないそれぞれのエージェント\(i\in M\cup W\)は未婚のままとする。すなわち、\(\phi _{i}^{M}\left( \succsim _{M\cup W}\right) =i\)と定める。その結果、女性求婚型DAメカニズムが定めるマッチング\(\phi ^{W}\left( \succsim _{M\cup W}\right) \)が得られる。
M &=&\left\{ m_{1},m_{2},m_{3},m_{4}\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}{cccccc}\hline
エージェント\diagdown 順位 & 1 & 2 & 3 & 4 & 5 \\ \hline
m_{1} & w_{1} & w_{2} & w_{3} & m_{1} & – \\ \hline
m_{2} & w_{2} & w_{3} & w_{1} & m_{2} & – \\ \hline
m_{3} & w_{3} & w_{1} & w_{2} & m_{3} & – \\ \hline
m_{4} & w_{3} & w_{2} & m_{4} & w_{1} & – \\ \hline
w_{1} & m_{1} & m_{2} & m_{3} & m_{4} & w_{1} \\ \hline
w_{2} & m_{1} & m_{3} & m_{2} & w_{2} & m_{4} \\ \hline
w_{3} & m_{2} & m_{4} & m_{1} & w_{3} & m_{3} \\ \hline
\end{array}$$
以上の選好プロファイル\(\succsim _{M\cup W}\)に対して女性求婚型DAメカニズム\(\phi ^{W}\)が定めるマッチング\(\phi ^{W}\left( \succsim _{M\cup W}\right) \)を特定します。ステップ\(1\)における求婚は以下の通りです。\begin{equation*}w_{1}\rightarrow m_{1},\quad w_{2}\rightarrow m_{1},\quad w_{3}\rightarrow
m_{2}
\end{equation*}\(m_{1}\)は\(w_{1}\)と婚約する一方で\(w_{2}\)からの求婚を断り、\(m_{2}\)は\(w_{3}\)と婚約し、\(m_{3}\)と\(m_{4}\)は何もしません。その結果、以下の婚約関係\begin{equation*}\begin{pmatrix}
m_{1} & m_{2} & m_{3} & m_{4} \\
w_{1} & w_{3} & – & -\end{pmatrix}\end{equation*}が成立します。求婚を断られた女性\(w_{2}\)が存在するため次のステップへ進みます。ステップ\(2\)における求婚は以下の通りです。\begin{equation*}w_{2}\rightarrow m_{3}
\end{equation*}\(m_{3}\)は\(w_{2}\)と婚約します。その結果、以下の婚約関係\begin{equation*}\begin{pmatrix}
m_{1} & m_{2} & m_{3} & m_{4} \\
w_{1} & w_{3} & w_{2} & -\end{pmatrix}\end{equation*}が成立します。求婚を断られたり婚約を解消された女性は存在しないためプロセスを終了します。最終的に得られるマッチングは、\begin{equation*}
\phi ^{W}\left( \succsim _{M\cup W}\right) =\begin{pmatrix}
m_{1} & m_{2} & m_{3} & m_{4} \\
w_{1} & w_{3} & w_{2} & m_{4}\end{pmatrix}\end{equation*}となります。
DAメカニズムはメカニズムである
DAメカニズムはメカニズムとしての要件を満たすのでしょうか。メカニズムを写像\(\phi :\mathcal{R}_{M\cup W}\rightarrow \mathcal{M}\)として定義しましたが、これは、エージェントたちが表明する選好の組\(\succsim _{M\cup W}\in \mathcal{R}_{M\cup W}\)がいかなるものであっても、それに対して\(\phi \)は必ずマッチング\(\phi\left( \succsim _{M\cup W}\right) \in \mathcal{M}\)を1つずつ選び取ることができることを意味します。実際、DAメカニズムは常にマッチングを1つずつ選び取ることができるのでしょうか。
まずは男性求婚型DAメカニズム\(\phi ^{M}\)について考えます。1対1のマッチング問題の前提としてエージェント集合\(M,W\)は有限集合であり、したがってエージェントの人数は有限です。男性求婚型DAアルゴリズムにおいて、それぞれの男性は求婚を断られた女性に対して再び求婚することはできません。女性の人数は有限であるため、すべての男性は有限ステップ内で求婚対象となる女性がいなくなります。したがって男性求婚型DAメカニズムは有限ステップで終了します。
男性求婚型DAメカニズムの各ステップにおいて、それぞれのエージェントは最も望ましい相手を1人だけ選ぶ必要があります。したがって、エージェントの選好が狭義選好の仮定を満たさない場合、無差別であるような異なる相手が存在する状況が起こり得るため、アルゴリズムが途中で止まってしまいます。アルゴリズムが完遂することを保証するために狭義選好の仮定は必須です。狭義選好の仮定が成り立たない場合、エージェントたちは何らかの外生的な方法を通じて無差別な相手の間に順序を付与する必要があります。ただ、このようなタイ・ブレークが必要になる場合、メカニズムが本来のパフォーマンスを発揮できない状況が起こり得ます。詳細は場を改めて議論します。
男性求婚型DAメカニズムのそれぞれのステップにおいて男性が求婚できる相手は高々1人であり、女性が婚約できる相手は高々1人です。プロセスが終了すると、それぞれのエージェントには1人の婚約者がいるか、婚約者がいないかのどちらか一方であるため、男性提案型DAメカニズムは常にマッチングを1つずつ選び取ることが明らかになりました。男性提案型DAメカニズムはメカニズムとしての要件を満たしているということです。
女性求婚型DAメカニズムについても同様の議論が成立します。女性提案型DAメカニズムもまたメカニズムとしての要件を満たしているということです。
DAメカニズムは事後個人合理的メカニズム
1対1のマッチング問題におけるメカニズム\(\phi \)が事後個人合理的であることは、選好プロファイル\(\succsim _{M\cup W}\)を任意に選んだとき、それに対して\(\phi \)が定めるマッチング\(\phi \left(\succsim _{M\cup W}\right) \)が\(\succsim _{M\cup W}\)のもとで個人合理的であることを意味します。特に、私的価値モデルを分析対象とする場合、メカニズム\(\phi \)が事後個人合理的であることとは、選好プロファイル\(\succsim _{M\cup W}\in \mathcal{R}_{M\cup W}\)を任意に選んだとき、\begin{equation*}\forall i\in M\cup W:\phi _{i}\left( \succsim _{M\cup W}\right) \succsim
_{i}i
\end{equation*}が成り立つことを意味します。つまり、任意のエージェント\(i\)にとって、マッチング\(\phi \left( \succsim _{M\cup W}\right) \)のもとでマッチする相手\(\phi_{i}\left( \succsim _{M\cup W}\right) \)が誰ともマッチしないこと\(i\)以上に望ましいということです。
男性求婚型DAメカニズムと女性求婚型DAメカニズムはともに事後個人合理的なメカニズムです。
M &=&\left\{ m_{1},m_{2},m_{3},m_{4}\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}{cccccc}\hline
エージェント\diagdown 順位 & 1 & 2 & 3 & 4 & 5 \\ \hline
m_{1} & w_{1} & w_{2} & w_{3} & m_{1} & – \\ \hline
m_{2} & w_{2} & w_{3} & w_{1} & m_{2} & – \\ \hline
m_{3} & w_{3} & w_{1} & w_{2} & m_{3} & – \\ \hline
m_{4} & w_{3} & w_{2} & m_{4} & w_{1} & – \\ \hline
w_{1} & m_{1} & m_{2} & m_{3} & m_{4} & w_{1} \\ \hline
w_{2} & m_{1} & m_{3} & m_{2} & w_{2} & m_{4} \\ \hline
w_{3} & m_{2} & m_{4} & m_{1} & w_{3} & m_{3} \\ \hline
\end{array}$$
先に確認したように、以上の選好プロファイル\(\succsim _{M\cup W}\)に対して男性求婚型DAメカニズム\(\phi ^{M}\)が定めるマッチングは、\begin{equation*}\phi ^{M}\left( \succsim _{M\cup W}\right) =\begin{pmatrix}
w_{1} & w_{2} & w_{3} & m_{4} \\
m_{1} & m_{3} & m_{2} & m_{4}\end{pmatrix}\end{equation*}です。このとき、\begin{eqnarray*}
\phi _{m_{1}}^{M}\left( \succsim _{M\cup W}\right) &=&w_{1}\succ
_{m_{1}}m_{1} \\
\phi _{m_{2}}^{M}\left( \succsim _{M\cup W}\right) &=&w_{3}\succ
_{m_{2}}m_{2} \\
\phi _{m_{3}}^{M}\left( \succsim _{M\cup W}\right) &=&w_{2}\succ
_{m_{3}}m_{3} \\
\phi _{m_{4}}^{M}\left( \succsim _{M\cup W}\right) &=&m_{4}\sim m_{4} \\
\phi _{w_{1}}^{M}\left( \succsim _{M\cup W}\right) &=&m_{1}\succ
_{w_{1}}w_{1} \\
\phi _{w_{2}}^{M}\left( \succsim _{M\cup W}\right) &=&m_{3}\succ
_{w_{2}}w_{2} \\
\phi _{w_{3}}^{M}\left( \succsim _{M\cup W}\right) &=&m_{2}\succ
_{w_{1}}w_{3}
\end{eqnarray*}が成立しているため、\(\phi ^{M}\left( \succsim _{M\cup W}\right) \)は\(\succsim_{M\cup W}\)のもとで個人合理的です。この結果は先の命題の主張と整合的です。
事後個人合理的メカニズム\(\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メカニズムは誘因両立性を満たさないため、上の命題中の選好プロファイル\(\succsim _{M\cup W}\)はエージェントたちが申告する選好からなる組という意味合いにとどまります。
DAメカニズムはペア安定的メカニズム
1対1のマッチング問題におけるメカニズム\(\phi \)がペア安定的であることは、選好プロファイル\(\succsim _{M\cup W}\)を任意に選んだとき、それに対して\(\phi \)が定めるマッチング\(\phi \left( \succsim _{M\cup W}\right) \)が\(\succsim _{M\cup W}\)のもとでペア安定的であることを意味します。特に、私的価値モデルを分析対象とする場合、メカニズム\(\phi \)がペア安定的であることとは、選好プロファイル\(\succsim _{M\cup W}\in \mathcal{R}_{M\cup W}\)を任意に選んだとき、\begin{eqnarray*}&&\left( a\right) \ w\succ _{m}\phi _{m}\left( \succsim _{M\cup W}\right) \\
&&\left( b\right) \ m\succ _{w}\phi _{w}\left( \succsim _{M\cup W}\right)
\end{eqnarray*}をともに満たす男女のペア\(\left( m,w\right) \in M\times W\)が存在しないことを意味します。つまり、メカニズムが定めるマッチング\(\phi \left( \succsim _{M\cup W}\right) \)においてマッチする相手との関係を解消してお互いにマッチすることで狭義にパレート改善できる男女のペア\(\left( m,w\right) \)が存在しないということです。男性求婚型DAメカニズムと女性求婚型DAメカニズムはともにペア安定的なメカニズムです。
M &=&\left\{ m_{1},m_{2},m_{3},m_{4}\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}{cccccc}\hline
エージェント\diagdown 順位 & 1 & 2 & 3 & 4 & 5 \\ \hline
m_{1} & w_{1} & w_{2} & w_{3} & m_{1} & – \\ \hline
m_{2} & w_{2} & w_{3} & w_{1} & m_{2} & – \\ \hline
m_{3} & w_{3} & w_{1} & w_{2} & m_{3} & – \\ \hline
m_{4} & w_{3} & w_{2} & m_{4} & w_{1} & – \\ \hline
w_{1} & m_{1} & m_{2} & m_{3} & m_{4} & w_{1} \\ \hline
w_{2} & m_{1} & m_{3} & m_{2} & w_{2} & m_{4} \\ \hline
w_{3} & m_{2} & m_{4} & m_{1} & w_{3} & m_{3} \\ \hline
\end{array}$$
先に確認したように、以上の選好プロファイル\(\succsim _{M\cup W}\)に対して男性求婚型DAメカニズム\(\phi ^{M}\)が定めるマッチングは、\begin{equation*}\phi ^{M}\left( \succsim _{M\cup W}\right) =\begin{pmatrix}
w_{1} & w_{2} & w_{3} & m_{4} \\
m_{1} & m_{3} & m_{2} & m_{4}\end{pmatrix}\end{equation*}です。\(w_{1},w_{3},m_{1}\)は自身にとって最も望ましい相手とマッチしているため相手を変える必要がありません。\(w_{2}\)は相手を\(m_{1}\)に変えたいところですが\(m_{1}\)はそれを望みません。\(m_{2}\)は相手を\(w_{2}\)に変えたいところですが\(w_{2}\)はそれを望みません。\(m_{3}\)は相手を\(w_{1}\)または\(w_{3}\)に変えたいところですが、\(w_{1}\)と\(w_{3}\)はそれを望みません。\(m_{4}\)は相手を\(w_{2}\)または\(w_{3}\)に変えたいところですが、\(w_{2}\)と\(w_{3}\)はそれを望みません。したがって、\(\phi ^{M}\left( \succsim _{M\cup W}\right) \)は\(\succsim _{M\cup W}\)のもとでペア安定的です。この結果は先の命題の主張と整合的です。
ペア安定的なメカニズム\(\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メカニズムは誘因両立性を満たさないため、上の命題中の選好プロファイル\(\succsim _{M\cup W}\)はエージェントたちが申告する選好からなる組という意味合いにとどまります。
DAメカニズムは安定メカニズム
1対1のマッチング問題におけるメカニズム\(\phi \)が安定的であることは、選好プロファイル\(\succsim _{M\cup W}\)を任意に選んだとき、それに対して\(\phi \)が定めるマッチング\(\phi \left( \succsim _{M\cup W}\right) \)が\(\succsim _{M\cup W}\)のもとで個人合理的かつペア安定的であることを意味します。先に示したように、男性求婚型DAメカニズムと女性求婚型DAメカニズムはともに個人合理的かつペア安定的なメカニズムです。したがって以下を得ます。
安定メカニズム\(\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メカニズムは誘因両立性を満たさないため、上の命題中の選好プロファイル\(\succsim _{M\cup W}\)はエージェントたちが申告する選好からなる組という意味合いにとどまります。
DAメカニズムは広義コア選択メカニズム
1対1のマッチング問題におけるメカニズム\(\phi \)が広義コア選択メカニズムであることは、選好プロファイル\(\succsim _{M\cup W}\)を任意に選んだとき、それに対して\(\phi \)が定めるマッチング\(\phi \left( \succsim _{M\cup W}\right) \)が\(\succsim_{M\cup W}\)のもとで広義コアであることを意味します。特に、私的価値モデルを分析対象とする場合、メカニズム\(\phi \)が広義コア選択メカニズムであることとは、選好プロファイル\(\succsim _{M\cup W}\in \mathcal{R}_{M\cup W}\)を任意に選んだとき、\begin{eqnarray*}&&\left( a\right) \ \forall i\in T:\mu \left( i\right) \in T \\
&&\left( b\right) \ \forall i\in T:\mu \left( i\right) \succ _{i}\phi
_{i}\left( \succsim _{M\cup W}\right)
\end{eqnarray*}をともに満たす提携\(T\subset M\cup W\)とマッチング\(\mu \in \mathcal{M}\)の組が存在しないことを意味します。つまり、メカニズムが定めるマッチング\(\phi \left( \succsim _{M\cup W}\right) \)においてマッチする相手を交換して内部で狭義にパレート改善できる提携が存在しないということです。
1対1のマッチング問題の私的価値モデルにおいて、メカニズム\(\phi \)が安定メカニズムであることと、\(\phi \)が広義コア選択メカニズムであることは必要十分です。以上の事実と、男性求婚型DAメカニズムと女性求婚型DAメカニズムがともに安定メカニズムであることを踏まえると以下を得ます。
広義コア選択メカニズム\(\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メカニズムは誘因両立性を満たさないため、上の命題中の選好プロファイル\(\succsim _{M\cup W}\)はエージェントたちが申告する選好からなる組という意味合いにとどまります。
DAメカニズムは広義事後効率的メカニズム
1対1のマッチング問題におけるメカニズム\(\phi \)が広義事後効率的であることは、選好プロファイル\(\succsim _{M\cup W}\)を任意に選んだとき、それに対して\(\phi \)が定めるマッチング\(\phi \left(\succsim _{M\cup W}\right) \)が\(\succsim _{M\cup W}\)のもとで広義パレート効率的であることを意味します。特に、私的価値モデルを分析対象とする場合、メカニズム\(\phi \)が広義事後効率的であることとは、選好プロファイル\(\succsim _{M\cup W}\in \mathcal{R}_{M\cup W}\)を任意に選んだとき、\begin{equation*}\forall i\in M\cup W:\mu \left( i\right) \succ _{i}\phi _{i}\left( \succsim
_{M\cup W}\right)
\end{equation*}を満たすマッチング\(\mu\in \mathcal{M}\)が存在しないことを意味します。つまり、メカニズムが定めるマッチング\(\phi \left(\succsim _{M\cup W}\right) \)から狭義パレート改善が不可能であるということです。
1対1のマッチング問題の私的価値モデルにおいて、広義コア選択メカニズム\(\phi \)は広義事後効率的です。以上の事実と、男性求婚型DAメカニズムと女性求婚型DAメカニズムがともに広義パレート効率的であることを踏まえると以下を得ます。
広義事後効率的メカニズム\(\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メカニズムは誘因両立性を満たさないため、上の命題中の選好プロファイル\(\succsim _{M\cup W}\)はエージェントたちが申告する選好からなる組という意味合いにとどまります。
プレミアム会員専用コンテンツです
【ログイン】【会員登録】