WIIS

1対1のマッチング問題

1対1のマッチング問題における安定メカニズム

目次

Twitter
Mailで保存

ペア安定的なマッチング

1対1のマッチング問題私的価値モデルにおいて状態\(\succsim _{M\cup W}\in \mathcal{R}_{M\cup W}\)を任意に選びます。このとき、マッチング\(\mu \in \mathcal{M}\)に対して、以下の条件\begin{eqnarray*}&&\left( a\right) \ w\succ _{m}\mu \left( m\right) \\
&&\left( b\right) \ m\succ _{w}\mu \left( w\right)
\end{eqnarray*}をともに満たす男女のペア\(\left( m,w\right) \in M\times W\)が存在する場合、\(\succsim _{M\cup W}\)においてマッチング\(\mu \)はペア\(\left( m,w\right) \)によってブロックされる(\(\mu \) is blocked by \(\left( m,w\right) \) at \(\succsim_{M\cup W}\))と言います。

条件\(\left( a\right) \)は、男性\(m\)にとってマッチング\(\mu \)のもとで自身がマッチしている相手\(\mu \left( m\right) \)よりも女性\(w\)のほうが望ましいことを意味し、条件\(\left( b\right) \)は、女性\(w\)にとってマッチング\(\mu \)のもとで自身がマッチしている相手\(\mu\left( w\right) \)よりも男性\(m\)のほうが望ましいことを意味します。以上を踏まえると、状態\(\succsim_{M\cup W}\)においてマッチング\(\mu \)が男女のペア\(\left(m,w\right) \)によってブロックされることとは、エージェントたちが\(\mu \)に直面した場合に、\(m\)と\(w\)は\(\mu \)においてマッチする相手との関係をそれぞれ解消して\(m\)と\(w\)どうしでマッチした方が双方にとってより望ましいことを意味します。この場合、男女\(\left( m,w\right) \)はマッチング\(\mu \)を受け入れる道理がありません。このような意味において、何らかの男女のペアによってブロックされるマッチングは望ましくありません。

状態\(\succsim _{M\cup W}\in \mathcal{R}_{M\cup W}\)においてマッチング\(\mu \in \mathcal{M}\)がいかなる男女のペアによってもブロックされない場合には、すなわち、マッチング\(\mu \)に対して、\begin{eqnarray*}&&\left( a\right) \ w\succ _{m}\mu \left( m\right) \\
&&\left( b\right) \ m\succ _{w}\mu \left( w\right)
\end{eqnarray*}をともに満たす\(\left( m,w\right)\in M\times W\)が存在しない場合、\(\succsim _{M\cup W}\)において\(\mu \)はペア安定的(pairwisestable)であると言います。ペア安定的なマッチングは状態\(\succsim _{M\cup W}\)に依存して変化します。つまり、ある状態\(\succsim _{M\cup W}\)においてペア安定的であるようなマッチングが別の状態\(\succsim _{M\cup W}^{\prime }\)においてもペア安定的であるとは限りません。

例(ペア安定的なマッチング)
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} & 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}$$

表:エージェントの選好

以下のマッチング\begin{equation*}
\mu =\begin{pmatrix}
m_{1} & m_{2} & m_{3} \\
w_{1} & w_{2} & w_{3}\end{pmatrix}\end{equation*}は先の選好プロファイル\(\succsim _{M\cup W}\)のもとでペア安定的でしょうか。\(w_{1},w_{2}\)は自身にとって最も望ましい相手とマッチしているため相手を変える必要がありません。\(w_{3}\)は相手を\(m_{1}\)に変えたいところですが\(m_{1}\)はそれを望みません。\(m_{1}\)は相手を\(w_{2}\)に変えたいところですが\(w_{2}\)はそれを望みません。\(m_{2}\)は相手を\(w_{1}\)に変えたいところですが\(w_{1}\)はそれを望みません。\(m_{3}\)は相手を\(w_{1}\)または\(w_{2}\)に変えたいところですが、\(w_{1}\)と\(w_{2}\)はそれを望みません。したがって\(\mu \)をブロックする男女のペアは存在せず、\(\mu \)は\(\succsim _{M\cup W}\)のもとでペア安定的であることが明らかになりました。では、以下のマッチング\begin{equation*}\mu ^{\prime }=\begin{pmatrix}
m_{1} & m_{2} & m_{3} & w_{3} \\
w_{1} & w_{2} & m_{3} & w_{3}\end{pmatrix}\end{equation*}は先の選好プロファイル\(\succsim _{M\cup W}\)のもとでペア安定的でしょうか。\(w_{1},w_{2}\)は自身にとって最も望ましい相手とマッチしているため相手を変える必要がありません。\(w_{3}\)は相手を\(m_{1},m_{2},m_{3}\)の誰かに変えたいところですが\(m_{1},m_{2},m_{3}\)はそれを望みません。\(m_{1}\)は相手を\(w_{2}\)に変えたいところですが\(w_{2}\)はそれを望みません。\(m_{2}\)は相手を\(w_{1}\)に変えたいところですが\(w_{1}\)はそれを望みません。\(m_{3}\)は相手を\(w_{1}\)または\(w_{2}\)に変えたいところですが、\(w_{1}\)と\(w_{2}\)はそれを望みません。したがって\(\mu ^{\prime }\)をブロックする男女のペアは存在せず、\(\mu^{\prime }\)は\(\succsim _{M\cup W}\)のもとでペア安定的であることが明らかになりました。では、以下のマッチング\begin{equation*}\mu ^{\prime \prime }=\begin{pmatrix}
m_{1} & m_{2} & m_{3} \\
w_{3} & w_{1} & w_{2}\end{pmatrix}\end{equation*}は先の選好プロファイル\(\succsim _{M\cup W}\)のもとでペア安定的でしょうか。男女のペア\(\left( m_{1},w_{2}\right)\in M\times W\)に注目すると、\begin{eqnarray*}w_{2} &\succ &_{m_{1}}w_{3}=\mu ^{\prime \prime }\left( m_{1}\right) \\
m_{1} &\succ &_{w_{2}}m_{3}=\mu ^{\prime \prime }\left( w_{2}\right)
\end{eqnarray*}が成り立つため、\(\left(m_{1},w_{2}\right) \)は\(\mu \)をブロックします。したがって、\(\mu ^{\prime }\)は\(\succsim _{M\cup W}\)のもとでペア安定的ではありません。

 

安定的なマッチング

1対1のマッチング問題の私的価値モデルにおいて状態\(\succsim _{M\cup W}\in \mathcal{R}_{M\cup W}\)を任意に選びます。このとき、マッチング\(\mu \in \mathcal{M}\)が\(\succsim _{M\cup W}\)のもとで個人合理的かつペア安定的であるならば、すなわち、\begin{equation*}\forall i\in M\cup W:\mu \left( i\right) \succsim _{i}i
\end{equation*}が成り立つとともに、\begin{eqnarray*}
&&\left( a\right) \ w\succ _{m}\mu \left( m\right) \\
&&\left( b\right) \ m\succ _{w}\mu \left( w\right)
\end{eqnarray*}をともに満たす\(\left( m,w\right)\in M\times W\)が存在しない場合には、\(\succsim _{M\cup W}\)において\(\mu \)は安定的(stable)であると言います。安定的なマッチングは状態\(\succsim _{M\cup W}\)に依存して変化します。つまり、ある状態\(\succsim _{M\cup W}\)において安定的であるようなマッチングが別の状態\(\succsim _{M\cup W}^{\prime }\)においても安定的であるとは限りません。

例(安定的なマッチング)
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} & 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}$$

表:エージェントの選好

以下のマッチング\begin{equation*}
\mu =\begin{pmatrix}
m_{1} & m_{2} & m_{3} \\
w_{1} & w_{2} & w_{3}\end{pmatrix}\end{equation*}が先の選好プロファイル\(\succsim _{M\cup W}\)のもとでペア安定的であることはすでに確認した通りです。一方、\(m_{2}\)について、\begin{equation*}m_{3}\succ _{m_{3}}w_{3}=\mu \left( m_{3}\right)
\end{equation*}が成り立つため、\(\mu \)は\(\succsim _{M\cup W}\)のもとで個人合理的ではありません。したがって、\(\mu \)は\(\succsim _{M\cup W}\)のもとで安定的ではありません。以下のマッチング\begin{equation*}\mu ^{\prime }=\begin{pmatrix}
m_{1} & m_{2} & m_{3} & w_{3} \\
w_{1} & w_{2} & m_{3} & w_{3}\end{pmatrix}\end{equation*}のもとでペア安定的であることはすでに確認した通りです。加えて、任意のエージェントは誰ともマッチしないこと以上に望ましい相手とマッチしているため\(\mu^{\prime }\)は個人合理的です。したがって、\(\mu ^{\prime }\)は\(\succsim _{M\cup W}\)のもとで安定的です。以下のマッチング\begin{equation*}\mu ^{\prime \prime }=\begin{pmatrix}
m_{1} & m_{2} & m_{3} \\
w_{3} & w_{1} & w_{2}\end{pmatrix}\end{equation*}が先の選好プロファイル\(\succsim _{M\cup W}\)のもとでペア安定的でないことはすでに確認した通りです。したがって、\(\mu ^{\prime \prime }\)は\(\succsim _{M\cup W}\)のもとで安定的ではありません。

 

安定メカニズム

1対1のマッチング問題におけるメカニズム\(\phi \)が何らかの純粋戦略の組を均衡として遂行可能であるものとします。ただし、表明原理より、正直戦略の組が均衡になるケース、すなわち誘因両立的なメカニズムに対象を限定しても一般性は失われません。状態が\(\succsim _{M\cup W}\)である場合、誘因両立的なメカニズム\(\phi \)のもとではエージェントたちは正直戦略にもとづいて\(\succsim _{M\cup W}\)を申告し、その申告に対してメカニズムはマッチング\(\phi \left( \succsim _{M\cup W}\right) \)を定めますが、このマッチングが\(\succsim _{M\cup W}\)のもとで安定的であることが保証される場合、このメカニズム\(\phi \)は安定メカニズム(stable mechanism)であると言います。

メカニズムを設計する段階において、制度設計者はどの状態が真の状態であるか分からないため、誘因両立的なメカニズムが安定的であることを保証するためには、起こり得るあらゆる状態において、そこでの均衡マッチングが安定的であることを保証する必要があります。したがって、誘因両立的なメカニズム\(\phi \)が安定的であることとは、状態\(\succsim _{M\cup W}\in \mathcal{R}_{M\cup W}\)を任意に選んだとき、それに対して、マッチング\(\phi \left( \succsim _{M\cup W}\right) \in \mathcal{M}\)が\(\succsim _{M\cup W}\)のもとで個人合理的かつペア安定的であること、すなわち、\begin{equation*}\forall i\in M\cup W:\phi _{i}\left( \succsim _{M\cup W}\right) \succsim
_{i}i
\end{equation*}が成り立つとともに、\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 \)に均衡が存在することを前提としない場合にはどうなるでしょうか。この場合、メカニズム\(\phi \)が安定的であることとは、エージェントたちが申告する選好プロファイル\(\succsim _{M\cup W}\in \mathcal{R}_{M\cup W}\)を任意に選んだとき、それに対して\(\phi \)が定めるマッチング\(\phi \left( \succsim _{M\cup W}\right) \)が\(\succsim _{M\cup W}\)のもとで個人合理的かつペア安定的であること、すなわち、\begin{equation*}\forall i\in M\cup W:\phi _{i}\left( \succsim _{M\cup W}\right) \succsim
_{i}i
\end{equation*}が成り立つとともに、\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 \)が安定的であるための条件と同様です。ただし、この場合、メカニズム\(\phi \)は誘因両立的であるとは限らないため、メカニズムが定めるマッチングはエージェントたちが申告する選好のもとで安定的である一方で、エージェントたちの真の選好のもとで安定的であるとは限りません。つまり、真の意味での安定的なマッチングを遂行するためには、メカニズムは安定的であるとともに誘因両立的である必要があるということです。

 

安定性とコアの関係

1対1のマッチング問題の私的価値モデルにおいて、状態\(\succsim _{M\cup W}\in \mathcal{R}_{M\cup W}\)においてマッチング\(\mu \in \mathcal{M}\)が広義コアであることとは、\begin{eqnarray*}&&\left( a\right) \ \forall i\in T:\mu ^{\prime }\left( i\right) \in T \\
&&\left( b\right) \ \forall i\in T:\mu ^{\prime }\left( i\right) \succ
_{i}\mu \left( i\right)
\end{eqnarray*}をともに満たすマッチング\(\mu ^{\prime }\in \mathcal{M}\)とエージェント集合\(T\subset M\cup W\)が存在しないことを意味します。つまり、任意の提携\(T\)はその内部でマッチする相手を交換しても狭義にパレート改善できる可能性はないということです。一方、マッチング\(\mu \)がペア安定的であることとは任意の男女のペア\(\left( m,w\right) \)がその内部でパレート改善できる可能性はないことを意味します。男女のペア\(\left( m,w\right) \)は提携\(\left\{ m,w\right\} \)と解釈できるため、広義コアを出発点にいかなる男女のペアもまた狭義のパレート改善できる見込みはありません。つまり、広義コアはペア安定的であるということです。

命題(広義コアはペア安定的)
1対1のマッチング問題の私的価値モデルにおいて、状態\(\succsim _{M\cup W}\in \mathcal{R}_{M\cup W}\)のもとでマッチング\(\mu \in \mathcal{M}\)が広義コアであるならば、\(\succsim_{M\cup W}\)のもとで\(\mu \)はペア安定的である。
証明

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

1対1のマッチング問題の私的価値モデルにおいて、広義コアが個人合理的であることはすでに示した通りです。以上の命題と安定性の定義を踏まえると以下を得ます。

命題(広義コアは安定的)
1対1のマッチング問題の私的価値モデルにおいて、状態\(\succsim _{M\cup W}\in \mathcal{R}_{M\cup W}\)のもとでマッチング\(\mu \in \mathcal{M}\)が広義コアであるならば、\(\succsim_{M\cup W}\)のもとで\(\mu \)は安定的である。したがって、メカニズム\(\phi \)が広義コア選択メカニズムであるならば、\(\phi \)は安定メカニズムである。

実は、上の命題の逆もまた成立します。つまり、安定的なマッチングは広義コアです。

命題(安定的なマッチングは広義コア)
1対1のマッチング問題の私的価値モデルにおいて、状態\(\succsim _{M\cup W}\in \mathcal{R}_{M\cup W}\)のもとでマッチング\(\mu \in \mathcal{M}\)が安定的であるならば、\(\succsim _{M\cup W}\)のもとで\(\mu \)は広義コアである。したがって、メカニズム\(\phi \)が安定メカニズムであるならば、\(\phi \)は広義コア選択メカニズムである。
証明

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

以上より、1対1のマッチング問題の私的価値モデルにおいて、安定性と広義コアは概念として一致することが明らかになりました。

命題(安定性と広義コアの関係)
1対1のマッチング問題の私的価値モデルにおいて、状態\(\succsim _{M\cup W}\in \mathcal{R}_{M\cup W}\)のもとでマッチング\(\mu \in \mathcal{M}\)が安定的であることと、\(\succsim _{M\cup W}\)のもとで\(\mu \)が広義コアであることは必要十分である。したがって、メカニズム\(\phi \)が安定メカニズムであることと、\(\phi \)が広義コア選択メカニズムであることは必要十分である。

つまり、1対1のマッチング問題の私的価値モデルを対象とする場合、あるマッチング\(\mu \)が広義コアであることを検証する際に、すべての提携についてそれが\(\mu \)を狭義ブロックしないことを調べる必要はなく、男女のペアや個人が\(\mu \)をブロックしないことを調べれば十分であるということです。

一般に、狭義コアは広義コアである一方で、その逆は成立するとは限りません。ただ、エージェントたちの選好が完備性、推移性、そして狭義選好の仮定を満たす場合には、狭義コアと広義コアは一致します。したがって以下を得ます。

命題(安定性と狭義コアの関係)
1対1のマッチング問題の私的価値モデルにおいて、任意のエージェントの選好が完備性、推移性、狭義選好の仮定を満たすものとする。この場合、状態\(\succsim _{M\cup W}\in \mathcal{R}_{M\cup W}\)のもとでマッチング\(\mu \in \mathcal{M}\)が安定的であることと、\(\succsim _{M\cup W}\)のもとで\(\mu \)が狭義コアであることは必要十分である。したがって、メカニズム\(\phi \)が安定メカニズムであることと、\(\phi \)が狭義コア選択メカニズムであることは必要十分である。
Twitter
Mailで保存

質問とコメント

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

関連知識

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

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

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

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

非分割財の交換問題における個人合理的メカニズム

非分割財の交換問題(シャプレー・スカーフの住宅市場)におけるメカニズムが与えられたとき、メカニズムの均衡において、メカニズムが定める配分が任意のプレイヤーにとって初期配分以上に望ましいことが保証されるならば、そのようなメカニズムは個人合理性を満たすと言います。

単一財オークションにおけるメカニズムのもとでのベイジアンゲーム

単一財オークション市場においてメカニズムを提示された入札者たちが直面する戦略的状況はベイジアンゲームとして定式化されます。そのようなゲームにおいて、それぞれの入札者は自身のタイプと信念にもとづいて他の入札者たちのタイプを予想し、その予想から算出される中間期待利得を最大化するような純粋戦略を採用するものとします。

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

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

非分割財の交換問題におけるパレート効率的メカニズム

ある配分を出発点に誰かの満足度を高めようとすると他の人の犠牲が伴うような状態であるとき、その配分はパレート効率的であると言います。また、パレート効率的な配分を常に選び取るメカニズムをパレート効率的なメカニズムと呼びます。

非分割財の交換問題におけるコア選択メカニズム

ある配分を出発点に、そこからプレイヤーのグループ(提携)が内部で商品を交換することでグループ内でのパレート改善が可能である場合、その配分はその提携によってブロックされると言います。また、いかなる提携によってもブロックされない配分をコアと呼び、コアを常に選び取るメカニズムをコア選択メカニズムと呼びます。