1対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_{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) \)以上に望ましいマッチングは存在し得るということです。

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}\)は存在しない。

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

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}\)のもとで広義パレート効率的である。