WIIS

1対1のマッチング問題

1対1のマッチング問題における安定性と効率性のトレードオフ

目次

Twitter
Mailで保存

男性(女性)最適安定マッチングは男性(女性)たちにとって狭義パレート効率的であるとは限らない

1対1のマッチング問題私的価値モデルにおいて、任意のエージェントの選好が完備性、推移性、狭義選好の仮定を満たす場合、安定マッチングが必ず存在するとともに、それは一意的であるとは限らないことが明らかになりました。安定マッチングどうしを比較した場合、男性求婚型DAメカニズムが出力するマッチングはすべての男性にとって最も望ましい安定マッチングである一方で、すべての女性にとって最も望ましくない安定マッチングです。逆に、女性求婚型DAメカニズムが出力するマッチングはすべての男性にとって最も望ましくない安定マッチングである一方で、すべての女性にとって最も望ましい安定マッチングです。ただ、以上の議論は安定マッチングどうしの比較が前提となっており、安定マッチングと安定的ではないマッチングの関係については何も言っていません。つまり、安定性を犠牲にした場合に、別の意味においてより望ましいマッチングが存在する可能性は排除されていないということです。そのようなマッチングは存在するのでしょうか。

まずは男性の視点から考えます。先の条件のもとでは男性求婚型DAメカニズムは安定的(個人合理的かつペア安定的)ですが、これは広義コア選択メカニズムであることと必要十分です。広義コア選択メカニズムは広義事後効率的であるため、結局、男性求婚型DAメカニズムは広義事後効率的です。加えて、狭義選好の仮定を含む先の条件のもとでは、メカニズムが広義コア選択であることと狭義コア選択であることは必要十分です。狭義コア選択メカニズムは狭義事後効率的であるため、結局、男性求婚型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_{2} & w_{1} & w_{3} & m_{1} \\ \hline
m_{2} & w_{1} & w_{2} & w_{3} & m_{2} \\ \hline
m_{3} & w_{1} & w_{2} & w_{3} & m_{3} \\ \hline
w_{1} & m_{1} & m_{2} & m_{3} & w_{1} \\ \hline
w_{2} & m_{3} & m_{1} & m_{2} & w_{2} \\ \hline
w_{3} & m_{1} & m_{2} & m_{3} & 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_{1} & w_{3} & w_{2}\end{pmatrix}\end{equation*}です(確認してください)。\(\succsim _{M\cup W}\)のもとで安定的なマッチングどうしを比べたとき、このマッチング\(\phi ^{M}\left( \succsim _{M\cup W}\right) \)はすべての男性にとって最も望ましい安定マッチングです。加えて、すべてのエージェントにとって狭義パレート効率的であるため、ここを出発点にすべてのエージェントにとっての広義のパレート改善を実現することは不可能です。ただ、以下のマッチング\begin{equation*}\mu =\begin{pmatrix}
m_{1} & m_{2} & m_{3} \\
w_{2} & w_{3} & w_{1}\end{pmatrix}\end{equation*}に注目すると、それぞれの男性について、\begin{eqnarray*}
\mu \left( m_{1}\right) &=&w_{2}\succ _{m_{1}}w_{1}=\phi _{m_{1}}^{M}\left(
\succsim _{M\cup W}\right) \\
\mu \left( m_{2}\right) &=&w_{3}\sim _{m_{2}}w_{3}=\phi _{m_{2}}^{M}\left(
\succsim _{M\cup W}\right) \\
\mu \left( m_{3}\right) &=&w_{1}\succ _{m_{3}}w_{2}=\phi _{m_{3}}^{M}\left(
\succsim _{M\cup W}\right)
\end{eqnarray*}という関係が成立しており、提携\(M\)にとって\(\mu \)は\(\phi ^{M}\left( \succsim _{M\cup W}\right) \)を広義にパレート支配しています。したがって、\(M\)にとって\(\phi ^{M}\left(\succsim _{M\cup W}\right) \)は狭義パレート効率的ではありません。もちろん、\(\mu \)は安定的ではありません。仮に\(\mu \)が安定的であれば\(\phi ^{M}\left( \succsim _{M\cup W}\right) \)が男性最適な安定マッチングであることと矛盾するからです。実際、男女のペア\(\left( m_{2},w_{1}\right) \)に注目したとき、\begin{eqnarray*}w_{1} &\succ &_{m_{2}}w_{3}=\mu \left( m_{2}\right) \\
m_{2} &\succ &_{w_{1}}m_{3}=\mu \left( w_{1}\right)
\end{eqnarray*}が成立しているため\(\left( m_{2},w_{1}\right) \)は\(\mu \)をブロックします。したがって\(\mu \)はペア安定的ではなく、ゆえに安定的でもありません。いずれにせよ、安定性を犠牲にすれば、すべての男性にとって男性最適安定マッチング\(\phi ^{M}\left( \succsim _{M\cup W}\right) \)以上に望ましいマッチングは存在し得るということです。

女性についても同様の議論が成立します。つまり、先の条件のもとで女性求婚型DAメカニズムは安定的かつ狭義事後効率的であるため、女性求婚型DAメカニズムが出力するマッチングはすべての女性にとって最も望ましい安定マッチングであるとともに、そこを出発点に、安定的であるものとそうではないものを含めた他の任意のマッチングへ移行しても、すべてのエージェントにとっての広義のパレート改善を実現することは不可能です。ただ、安定性を犠牲にすれば、すべての女性にとって女性最適安定マッチング以上に望ましいマッチングは存在し得ます。言い換えると、提携\(W\)にとって女性求婚型DAメカニズムが出力するマッチングは狭義パレート効率的であるとは限らないということです。

 

男性(女性)最適安定マッチングは男性(女性)たちにとって広義パレート効率的

安定性を犠牲にした場合、すべての男性にとって男性最適安定マッチング以上に望ましいマッチングが存在し得ることが明らかになりました。つまり、提携\(M\)にとって男性最適安定マッチングを広義パレート支配する非安定マッチングが存在するということです。では、提携\(M\)にとって男性最適安定マッチングを狭義にパレート支配する非安定マッチングは存在するのでしょうか。言い換えると、安定性を犠牲にした場合、すべての男性にとって男性最適安定マッチングよりも望ましいマッチングが存在し得るとまで言えるのでしょうか。実は、そのような非安定的マッチングは存在しません。

命題(男性提案型DAメカニズムは男性たちにとって広義パレート効率的)
1対1のマッチング問題の私的価値モデルにおいて、任意のエージェントの選好が完備性、推移性、狭義選好の仮定を満たすものとする。選好プロファイル\(\succsim _{M\cup W}\in \mathcal{R}_{M\cup W}\)を任意に選んだとき、すべての男性からなる提携\(M\)にとって男性提案型DAメカニズム\(\phi ^{M}\)が定めるマッチング\(\phi ^{M}\left( \succsim _{M\cup W}\right) \)は\(\succsim _{M\cup W}\)のもとで広義パレート効率的である。つまり、\begin{equation*}\forall m\in M:\mu \left( m\right) \succ _{m}\phi _{m}^{M}\left( \succsim
_{M\cup W}\right)
\end{equation*}を満たすマッチング\(\mu\in \mathcal{M}\)は存在しない。
証明

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

与えられた条件のもとでは、男性提案型DAメカニズムが出力するマッチングとは別のマッチングが男性最適安定マッチングになることはありません。したがって、上の命題を以下のように表現することもできます。

命題(男性最適安定マッチング男性たちにとって広義パレート効率的)
1対1のマッチング問題の私的価値モデルにおいて、任意のエージェントの選好が完備性、推移性、狭義選好の仮定を満たすものとする。選好プロファイル\(\succsim _{M\cup W}\in \mathcal{R}_{M\cup W}\)を任意に選んだとき、すべての男性からなる提携\(M\)にとって男性最適安定マッチングは\(\succsim _{M\cup W}\)のもとで広義パレート効率的である。

女性提案型DAメカニズムについても同様の命題が成り立ちます。

命題(女性提案型DAメカニズムは女性たちにとって広義パレート効率的)
1対1のマッチング問題の私的価値モデルにおいて、任意のエージェントの選好が完備性、推移性、狭義選好の仮定を満たすものとする。選好プロファイル\(\succsim _{M\cup W}\in \mathcal{R}_{M\cup W}\)を任意に選んだとき、すべての女性からなる提携\(W\)にとって女性提案型DAメカニズム\(\phi ^{W}\)が定めるマッチング\(\phi ^{W}\left( \succsim _{M\cup W}\right) \)は\(\succsim _{M\cup W}\)のもとで広義パレート効率的である。つまり、\begin{equation*}\forall w\in W:\mu \left( w\right) \succ _{w}\phi _{w}^{w}\left( \succsim
_{M\cup W}\right)
\end{equation*}を満たすマッチング\(\mu\in \mathcal{M}\)は存在しない。

この命題を以下のように表現することもできます。

命題(女性最適安定マッチング女性たちにとって広義パレート効率的)
1対1のマッチング問題の私的価値モデルにおいて、任意のエージェントの選好が完備性、推移性、狭義選好の仮定を満たすものとする。選好プロファイル\(\succsim _{M\cup W}\in \mathcal{R}_{M\cup W}\)を任意に選んだとき、すべての女性からなる提携\(W\)にとって女性最適安定マッチングは\(\succsim _{M\cup W}\)のもとで広義パレート効率的である。
Twitter
Mailで保存

質問とコメント

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

関連知識

1対1のマッチング問題(安定結婚問題)

2つのグループに分かれたプレイヤーたちを何らかのルールにもとづいてグループ間で1対1でマッチングさせる資源配分問題を1対1のマッチング問題(安定結婚問題)と呼ばれるモデルとして定式化します。

1対1のマッチング問題の私的価値モデル

1対1のマッチング問題(安定結婚問題)において、プレイヤーの選好に関して非外部性と私的価値を仮定する場合、そのようなモデルを私的価値モデルと呼びます。

1対1のマッチング問題における耐戦略的メカニズム

1対1のマッチング問題(安定結婚問題)におけるメカニズムにおいて、すべてのエージェントにとって自身の真の選好を正直に申告することが支配戦略である場合、そのようなメカニズムは耐戦略性を満たすと言います。

DAメカニズムのもとでの男女の利害の対立

1対1のマッチング問題(安定結婚問題)において安定性を追求する限りにおいて、男性求婚型DAメカニズムは男性にとって最良である一方で女性にとって最悪であり、逆に、女性求婚型DAメカニズムは女性にとって最良である一方で男性にとって最悪です。