WIIS

教材一覧
教材一覧
教材検索
ONE-TO-ONE-MATCHING PROBLEM

1対1のマッチング問題におけるコア選択メカニズム

目次

Share on twitter
Twitterで共有
Share on email
メールで共有

狭義コア

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) \succsim
_{i}\mu \left( i\right) \\
&&\left( c\right) \ \exists 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\)が存在する場合、\(\succsim_{M\cup W}\)においてマッチング\(\mu \)は提携\(T\)によってマッチング\(\mu^{\prime }\)を通じて広義にブロックされる(\(\mu \) isweakly blocked by \(T\) via \(\mu ^{\prime }\) at \(\succsim _{M\cup W}\))と言います。

条件\(\left( a\right) \)は、提携\(T\)に属するそれぞれのエージェント\(i\)がマッチング\(\mu ^{\prime }\)においてマッチする相手\(\mu ^{\prime }\left(i\right) \)が、同じ提携\(T\)に属するエージェントであることを意味します。したがって\(\left( a\right) \)が成り立つことは、提携\(T\)に属するエージェントたちが内部でマッチする相手を交換することを通じて局所的なマッチング\(\mu^{\prime }\left( T\right) =\left( \mu ^{\prime }\left( i\right) \right) _{i\in T}\)を自力で達成できることを意味します。条件\(\left( b\right) \)は、提携\(T\)に属するすべてのエージェントにとって\(\mu^{\prime }\)が\(\mu \)以上に望ましいことを意味し、条件\(\left( c\right) \)は、提携\(T\)に属する少なくとも1人のエージェントにとって\(\mu ^{\prime }\)が\(\mu \)よりも望ましいことを意味します。以上を踏まえると、状態\(\succsim _{M\cup W}\)においてマッチング\(\mu \)が提携\(T\)によってマッチング\(\mu ^{\prime }\)を通じて広義にブロックされることとは、エージェントたちが\(\mu \)に直面した場合に、提携\(T\)に属するエージェントたちが提携の内部でマッチする相手を交換して局所的なマッチング\(\mu ^{\prime }\left( T\right) \)を実現することにより、提携の内部で広義にパレート改善可能であることを意味します。この場合、提携\(T\)に属するエージェントたちはマッチング\(\mu \)を受け入れる道理がありません。このような意味において、何らかの提携によって広義ブロックされるマッチングは望ましくありません。

状態\(\succsim _{M\cup W}\in \mathcal{R}_{M\cup W}\)においてマッチング\(\mu \in \mathcal{M}\)がいかなる提携\(T\subset M\cup W\)とマッチング\(\mu^{\prime }\in \mathcal{M}\)によっても広義にブロックされない場合には、すなわち、マッチング\(\mu \)に対して、\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) \succsim
_{i}\mu \left( i\right) \\
&&\left( c\right) \ \exists i\in T:\mu ^{\prime }\left( i\right) \succ
_{i}\mu \left( i\right)
\end{eqnarray*}をすべて満たす提携\(T\)とマッチング\(\mu ^{\prime }\)の組が存在しない場合、\(\succsim _{M\cup W}\)において\(\mu \)は狭義コア(strict core)であると言います。狭義コアなマッチングは状態\(\succsim _{M\cup W}\)に依存して変化します。つまり、ある状態\(\succsim _{M\cup W}\)において狭義コアであるようなマッチングが別の状態\(\succsim _{M\cup W}^{\prime }\)においても狭義コアであるとは限りません。

状態\(\succsim _{M\cup W}\)においてマッチング\(\mu \)が狭義コアであるものとします。これに対して、\begin{eqnarray*}&&\left( a\right) \ \forall i\in T:\mu ^{\prime }\left( i\right) \in T \\
&&\left( b\right) \ \exists i\in T:\mu ^{\prime }\left( i\right) \succ
_{i}\mu \left( i\right)
\end{eqnarray*}をともに満たす提携\(T\)とマッチング\(\mu ^{\prime }\)の組を任意に選びます。つまり、提携\(T\)に属するエージェントたちは内部においてマッチする相手を交換することにより局所的なマッチング\(\mu ^{\prime}\left( T\right) \)を実現でき、なおかつ、そのような交換により提携\(T\)に属する少なくとも1人のエージェント\(j\)の満足度が高まるということです。さて、狭義コアの定義よりマッチング\(\mu \)は提携\(T\)によってマッチング\(\mu ^{\prime }\)を通じて広義にブロックされないため、\begin{equation*}\forall i\in T:\mu ^{\prime }\left( i\right) \succsim _{i}\mu \left( i\right)
\end{equation*}は成り立ちません。完備性が成り立つ場合、上の条件が成り立たないことは、\begin{equation*}
\exists i\in T:\mu \left( i\right) \succ _{i}\mu ^{\prime }\left( i\right)
\end{equation*}が成り立つことと必要十分です。つまり、狭義コアなマッチング\(\mu \)を出発点に、提携\(T\)に属するあるエージェント\(j\)の満足度を高める形で別のマッチング\(\mu ^{\prime }\)へ移行しようとすると、提携\(T\)に属する少なくとも1人の満足度が低下してしまいます。狭義コアなマッチングが与えられたとき、任意の提携はその内部で広義パレート改善を実現するのは不可能であるため、狭義コアなマッチングは目指すべき目標になり得ます。

例(狭義コア)
1対1のマッチング問題の私的価値モデルにおいて、エージェント集合が、\begin{eqnarray*}
M &=&\left\{ m_{1},m_{2}\right\} \\
W &=&\left\{ w_{1},w_{2}\right\}
\end{eqnarray*}であるとともに、任意のエージェント\(i\in M\cup W\)の選好関係\(\succsim _{i}\)は完備性と推移性に加えて狭義選好の仮定を満たすものとします。具体的には、エージェントたちの選好プロファイル\(\succsim _{M\cup W}\)が以下の表によって与えられているものとします。

$$\begin{array}{cccc}\hline
エージェント\diagdown 順位 & 1 & 2 & 3 \\ \hline
m_{1} & w_{1} & w_{2} & m_{1} \\ \hline
m_{2} & w_{1} & w_{2} & m_{2} \\ \hline
w_{1} & m_{1} & m_{2} & w_{1} \\ \hline
w_{2} & m_{1} & m_{2} & w_{2} \\ \hline
\end{array}$$

表:エージェントの選好

以下のマッチング\begin{equation*}
\mu =\begin{pmatrix}
m_{1} & m_{2} \\
w_{1} & w_{2}\end{pmatrix}\end{equation*}は先の選好プロファイル\(\succsim _{M\cup W}\)のもとで狭義コアです。実際、\(\mu \)においてすべてのエージェントは自分自身よりも望ましい相手とマッチしているため、1人からなる提携はいずれも\(\mu \)を広義ブロックしません。また、\(m_{1},w_{1}\)は\(\mu \)において自身にとって最も望ましい相手とマッチしているため、彼らがマッチする相手を変更する形での提携内の取引を通じた提携内での広義パレート改善は不可能です。仮に2人以上からなる提携が\(\mu \)を広義にブロックするのであれば、その提携には\(m_{2}\)と\(w_{2}\)の少なくとも一方が含まれます。\(m_{2}\)や\(w_{2}\)の状態を向上させるためには\(m_{1}\)や\(w_{1}\)がマッチする相手が変化するため矛盾です。したがって、2人以上からなる任意の提携もまた\(\mu \)を広義にブロックせず、ゆえに\(\mu \)は\(\succsim _{M\cup W}\)のもとで狭義コアであることが明らかになりました。以下のマッチング\begin{equation*}\mu ^{\prime }=\begin{pmatrix}
m_{1} & m_{2} \\
w_{2} & w_{1}\end{pmatrix}\end{equation*}もまた先の選好プロファイル\(\succsim _{M\cup W}\)のもとで狭義コアです。実際、\(\mu ^{\prime }\)においてすべてのエージェントは自分自身よりも望ましい相手とマッチしているため、1人からなる提携はいずれも\(\mu ^{\prime }\)を広義ブロックしません。また、\(m_{2},w_{2}\)は\(\mu ^{\prime }\)において自身にとって最も望ましい相手とマッチしているため、彼らがマッチする相手を変更する形での提携内の取引を通じた提携内での広義パレート改善は不可能です。仮に2人以上からなる提携が\(\mu ^{\prime }\)を広義にブロックするのであれば、その提携には\(m_{1}\)と\(w_{1}\)の少なくとも一方が含まれます。\(m_{1}\)や\(w_{1}\)の状態を向上させるためには\(m_{2}\)や\(w_{2}\)がマッチする相手が変化するため矛盾です。したがって、2人以上からなる任意の提携もまた\(\mu ^{\prime }\)を広義にブロックせず、ゆえに\(\mu ^{\prime }\)は\(\succsim _{M\cup W}\)のもとで狭義コアであることが明らかになりました。以下のマッチング\begin{equation*}\mu ^{\prime \prime }=\begin{pmatrix}
m_{1} & m_{2} & w_{1} & w_{2} \\
m_{1} & m_{2} & w_{1} & w_{2}\end{pmatrix}\end{equation*}は先の選好プロファイル\(\succsim _{M\cup W}\)のもとで狭義コアではありません。実際、例えば、提携\(\left\{ m_{1},w_{1}\right\} \)について、\begin{eqnarray*}w_{1} &\succ &_{m_{1}}m_{1}=\mu ^{\prime \prime }\left( m_{1}\right) \\
m_{1} &\succ &_{w_{1}}w_{1}=\mu ^{\prime \prime }\left( w_{1}\right)
\end{eqnarray*}が成り立つからです。

 

広義コア

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\)が存在する場合、\(\succsim_{M\cup W}\)においてマッチング\(\mu \)は提携\(T\)によってマッチング\(\mu^{\prime }\)を通じて狭義にブロックされる(\(\mu \) isstrictly blocked by \(T\) via \(\mu ^{\prime }\) at \(\succsim _{M\cup W}\))と言います。

条件\(\left( a\right) \)は、提携\(T\)に属するそれぞれのエージェント\(i\)がマッチング\(\mu ^{\prime }\)においてマッチする相手\(\mu ^{\prime }\left(i\right) \)が、同じ提携\(T\)に属するエージェントであることを意味します。したがって\(\left( a\right) \)が成り立つことは、提携\(T\)に属するエージェントたちが内部でマッチする相手を交換することを通じて局所的なマッチング\(\mu^{\prime }\left( T\right) =\left( \mu ^{\prime }\left( i\right) \right) _{i\in T}\)を自力で達成できることを意味します。条件\(\left( b\right) \)は、提携\(T\)に属するすべてのエージェントにとって\(\mu^{\prime }\)が\(\mu \)よりも望ましいことを意味します。以上を踏まえると、状態\(\succsim _{M\cup W}\)においてマッチング\(\mu \)が提携\(T\)によってマッチング\(\mu^{\prime }\)を通じて狭義にブロックされることとは、エージェントたちが\(\mu \)に直面した場合に、提携\(T\)に属するエージェントたちが提携の内部でマッチする相手を交換して局所的なマッチング\(\mu^{\prime }\left( T\right) \)を実現することにより、提携の内部で狭義にパレート改善可能であることを意味します。この場合、提携\(T\)に属するエージェントたちはマッチング\(\mu \)を受け入れる道理がありません。このような意味において、何らかの提携によって狭義ブロックされるマッチングは望ましくありません。

状態\(\succsim _{M\cup W}\in \mathcal{R}_{M\cup W}\)においてマッチング\(\mu \in \mathcal{M}\)がいかなる提携\(T\subset M\cup W\)とマッチング\(\mu^{\prime }\in \mathcal{M}\)によっても狭義にブロックされない場合には、すなわち、マッチング\(\mu \)に対して、\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*}をともに満たす提携\(T\)とマッチング\(\mu ^{\prime }\)の組が存在しない場合、\(\succsim _{M\cup W}\)において\(\mu \)は広義コア(weak core)であると言います。広義コアなマッチングは状態\(\succsim _{M\cup W}\)に依存して変化します。つまり、ある状態\(\succsim _{M\cup W}\)において広義コアであるようなマッチングが別の状態\(\succsim _{M\cup W}^{\prime }\)においても広義コアであるとは限りません。

状態\(\succsim _{M\cup W}\)においてマッチング\(\mu \)が広義コアであるものとします。これに対して、\begin{eqnarray*}&&\left( a\right) \ \forall i\in T:\mu ^{\prime }\left( i\right) \in T \\
&&\left( b\right) \ \exists i\in T:\mu ^{\prime }\left( i\right) \succ
_{i}\mu \left( i\right)
\end{eqnarray*}をともに満たす提携\(T\)とマッチング\(\mu ^{\prime }\)の組を任意に選びます。つまり、提携\(T\)に属するエージェントたちは内部においてマッチする相手を交換することにより局所的なマッチング\(\mu ^{\prime}\left( T\right) \)を実現でき、なおかつ、そのような交換により提携\(T\)に属する少なくとも1人のエージェント\(j\)の満足度が高まるということです。さて、広義コアの定義よりマッチング\(\mu \)は提携\(T\)によってマッチング\(\mu ^{\prime }\)を通じて狭義にブロックされないため、\begin{equation*}\forall i\in T\backslash \left\{ i\right\} :\mu ^{\prime }\left( i\right)
\succ _{i}\mu \left( i\right)
\end{equation*}は成り立ちません。完備性が成り立つ場合、上の条件が成り立たないことは、\begin{equation*}
\exists i\in T\backslash \left\{ i\right\} :\mu \left( i\right) \succsim
_{i}\mu ^{\prime }\left( i\right)
\end{equation*}が成り立つことと必要十分です。つまり、広義コアなマッチング\(\mu \)を出発点に、提携\(T\)に属するあるエージェント\(j\)の満足度を高める形で別のマッチング\(\mu ^{\prime }\)へ移行しようとすると、提携\(T\)に属する少なくとも1人の満足度が低下する可能性があります。広義コアなマッチングが与えられたとき、任意の提携はその内部で狭義パレート改善を実現するのは不可能であるため、広義コアなマッチングは目指すべき目標になり得ます。

例(広義コア)
1対1のマッチング問題の私的価値モデルにおいて、エージェント集合が、\begin{eqnarray*}
M &=&\left\{ m_{1},m_{2}\right\} \\
W &=&\left\{ w_{1},w_{2}\right\}
\end{eqnarray*}であるとともに、任意のエージェント\(i\in M\cup W\)の選好関係\(\succsim _{i}\)は完備性と推移性に加えて狭義選好の仮定を満たすものとします。具体的には、エージェントたちの選好プロファイル\(\succsim _{M\cup W}\)が以下の表によって与えられているものとします。

$$\begin{array}{cccc}\hline
エージェント\diagdown 順位 & 1 & 2 & 3 \\ \hline
m_{1} & w_{1} & w_{2} & m_{1} \\ \hline
m_{2} & w_{1} & w_{2} & m_{2} \\ \hline
w_{1} & m_{1} & m_{2} & w_{1} \\ \hline
w_{2} & m_{1} & m_{2} & w_{2} \\ \hline
\end{array}$$

表:エージェントの選好

以下のマッチング\begin{equation*}
\mu =\begin{pmatrix}
m_{1} & m_{2} \\
w_{1} & w_{2}\end{pmatrix}\end{equation*}は先の選好プロファイル\(\succsim _{M\cup W}\)のもとで広義コアです。実際、\(\mu \)においてすべてのエージェントは自分自身よりも望ましい相手とマッチしているため、1人からなる提携はいずれも\(\mu \)を狭義ブロックしません。また、\(m_{1}\)と\(w_{1}\)は\(\mu \)において自身にとって最も望ましい相手とマッチしているため、彼らがマッチする相手を変更する形での提携内の取引を通じた提携内での狭義パレート改善は不可能です。仮に2人以上からなる提携が\(\mu \)を狭義にブロックするのであれば、その提携には\(m_{2}\)と\(w_{2}\)の少なくとも一方が含まれます。\(m_{2}\)や\(w_{2}\)の状態を向上させるためには\(m_{1}\)や\(w_{1}\)がマッチする相手が変化するため矛盾です。したがって、2人以上からなる任意の提携もまた\(\mu \)を狭義にブロックせず、ゆえに\(\mu \)は\(\succsim _{M\cup W}\)のもとで広義コアであることが明らかになりました。以下のマッチング\begin{equation*}\mu ^{\prime }=\begin{pmatrix}
m_{1} & m_{2} \\
w_{2} & w_{1}\end{pmatrix}\end{equation*}もまた先の選好プロファイル\(\succsim _{M\cup W}\)のもとで広義コアです。実際、\(\mu ^{\prime }\)においてすべてのエージェントは自分自身よりも望ましい相手とマッチしているため、1人からなる提携はいずれも\(\mu ^{\prime }\)を狭義ブロックしません。また、\(m_{2},w_{2}\)は\(\mu ^{\prime }\)において自身にとって最も望ましい相手とマッチしているため、彼らがマッチする相手を変更する形での提携内の取引を通じた提携内での狭義パレート改善は不可能です。仮に2人以上からなる提携が\(\mu ^{\prime }\)を狭義にブロックするのであれば、その提携には\(m_{1}\)と\(w_{1}\)の少なくとも一方が含まれます。\(m_{1}\)や\(w_{1}\)の状態を向上させるためには\(m_{2}\)や\(w_{2}\)がマッチする相手が変化するため矛盾です。したがって、2人以上からなる任意の提携もまた\(\mu ^{\prime }\)を狭義にブロックせず、ゆえに\(\mu ^{\prime }\)は\(\succsim _{M\cup W}\)のもとで広義コアであることが明らかになりました。以下のマッチング\begin{equation*}\mu ^{\prime \prime }=\begin{pmatrix}
m_{1} & m_{2} & w_{1} & w_{2} \\
m_{1} & m_{2} & w_{1} & w_{2}\end{pmatrix}\end{equation*}は先の選好プロファイル\(\succsim _{M\cup W}\)のもとで広義コアではありません。実際、例えば、提携\(\left\{ m_{1},w_{1}\right\} \)について、\begin{eqnarray*}w_{1} &\succ &_{m_{1}}m_{1}=\mu ^{\prime \prime }\left( m_{1}\right) \\
m_{1} &\succ &_{w_{1}}w_{1}=\mu ^{\prime \prime }\left( w_{1}\right)
\end{eqnarray*}が成り立つからです。

 

狭義コア選択メカニズム

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

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

 

広義コア選択メカニズム

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

メカニズムを設計する段階において、制度設計者はどの状態が真の状態であるか分からないため、誘因両立的なメカニズムが広義コア選択であることを保証するためには、起こり得るあらゆる状態において、そこでの均衡マッチングが広義コア選択であることを保証する必要があります。したがって、誘因両立的なメカニズム\(\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 \)に均衡が存在することを前提としない場合にはどうなるでしょうか。この場合、メカニズム\(\phi \)が広義コア選択であることとは、エージェントたちが申告する選好プロファイル\(\succsim _{M\cup W}\in \mathcal{R}_{M\cup W}\)を任意に選んだとき、それに対して\(\phi \)が定めるマッチング\(\phi \left(\succsim _{M\cup W}\right) \)が\(\succsim _{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 \)が広義コア選択であるための条件と同様です。ただし、この場合、メカニズム\(\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のマッチング問題の私的価値モデルにおいて、エージェント集合が、\begin{eqnarray*}
M &=&\left\{ m_{1},m_{2}\right\} \\
W &=&\left\{ w_{1},w_{2}\right\}
\end{eqnarray*}で与えられているものとします。加えて、エージェントたちの選好プロファイル\(\succsim _{M\cup W}\)が、\begin{eqnarray*}w_{1} &\succ &_{m_{1}}w_{2}\succ _{m_{1}}m_{1} \\
w_{1} &\succ &_{m_{2}}w_{2}\succ _{m_{2}}m_{2} \\
m_{1} &\succ &_{w_{1}}m_{2}\succ _{w_{1}}w_{1} \\
m_{1} &\succ &_{w_{2}}m_{2}\sim _{w_{2}}w_{2}
\end{eqnarray*}で与えられているものとします。女性\(w_{2}\)の選好\(\succsim _{w_{2}}\)は狭義選好の仮定を満たしていないことに注意してください。以下のマッチング\begin{equation*}\mu =\begin{pmatrix}
m_{1} & m_{2} & w_{2} \\
w_{1} & m_{2} & w_{2}\end{pmatrix}\end{equation*}は先の選好プロファイル\(\succsim _{M\cup W}\)のもとで広義コアです。実際、\(\mu \)においてすべてのエージェントは自分自身以上に望ましい相手とマッチしているため、1人からなる提携はいずれも\(\mu \)を狭義ブロックしません。また、\(m_{1}\)と\(w_{1}\)は\(\mu \)において自身にとって最も望ましい相手とマッチしているため、彼らがマッチする相手を変更する形での提携内の取引を通じた提携内での狭義パレート改善は不可能です。2人以上の提携の中でも\(\mu \)を狭義ブロックし得るのは\(\left\{ m_{2},w_{2}\right\} \)だけですが、\begin{eqnarray*}w_{2} &\succ &_{m_{2}}m_{2}=\mu \left( m_{2}\right) \\
m_{2} &\sim &_{w_{2}}w_{2}=\mu \left( w_{2}\right)
\end{eqnarray*}が成り立つため、提携\(\left\{ m_{2},w_{2}\right\} \)は\(\mu \)を狭義にブロックしません。したがって\(\mu \)は\(\succsim_{M\cup W}\)のもとで広義コアです。その一方で、先の議論より、提携\(\left\{ m_{2},w_{2}\right\} \)は\(\mu \)を広義ブロックするため、\(\mu \)は\(\succsim _{M\cup W}\)のもとで狭義コアではありません。

ただし、エージェントたちの選好が完備性と推移性に加えて狭義選好の仮定を満たす場合には、広義コアが狭義コアになることも保証できます。したがって、広義コア選択メカニズムは狭義コア選択メカニズムでもあります。ただし、証明は必要な概念がすべて揃った段階で行います。

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

以上の2つの命題を踏まえると以下を得ます。

命題(広義コアが狭義コアと一致するための条件)
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}\)が個人合理的であることとは、\begin{equation*}\forall i\in M\cup W:\mu \left( i\right) \succsim _{i}i
\end{equation*}が成り立つことを意味します。つまり、任意のエージェント\(i\)にとって、マッチング\(\mu \)のもとで自身とマッチする相手\(\mu \left( i\right) \)が誰ともマッチしないこと\(i\)以上に望ましいということです。これは同時に、提携\(\left\{ i\right\} \)がマッチング\(\mu \)を狭義にブロックしないことを意味します。一方、マッチング\(\mu \)が広義コアであることは任意の提携が\(\mu \)を狭義ににブロックしないことを意味するため、その場合には提携\(\left\{ i\right\} \)もまた\(\mu \)を狭義にブロックせず、したがって個人合理性を満たします。つまり、広義コアは個人合理的であるということです。

命題(広義コアは個人合理的)
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のマッチング問題の私的価値モデルにおいて、エージェント集合が、\begin{eqnarray*}
M &=&\left\{ m_{1},m_{2}\right\} \\
W &=&\left\{ w_{1},w_{2}\right\}
\end{eqnarray*}であるとともに、任意のエージェント\(i\in M\cup W\)の選好関係\(\succsim _{i}\)は完備性と推移性に加えて狭義選好の仮定を満たすものとします。具体的には、エージェントたちの選好プロファイル\(\succsim _{M\cup W}\)が以下の表によって与えられているものとします。

$$\begin{array}{cccc}\hline
エージェント\diagdown 順位 & 1 & 2 & 3 \\ \hline
m_{1} & w_{1} & w_{2} & m_{1} \\ \hline
m_{2} & w_{1} & w_{2} & m_{2} \\ \hline
w_{1} & m_{1} & m_{2} & w_{1} \\ \hline
w_{2} & m_{1} & m_{2} & w_{2} \\ \hline
\end{array}$$

表:エージェントの選好

以下のマッチング\begin{equation*}
\mu =\begin{pmatrix}
m_{1} & m_{2} & w_{2} \\
w_{1} & m_{2} & w_{2}\end{pmatrix}\end{equation*}は先の選好プロファイル\(\succsim _{M\cup W}\)のもとで個人合理的です。なぜなら、全員が誰ともマッチしないこと以上に望ましい相手とマッチしているからです。その一方で、\(\mu \)は\(\succsim _{M\cup W}\)のもとで広義コアではありません。実際、提携\(\left\{m_{2},w_{2}\right\} \)に注目すると、\begin{eqnarray*}w_{2} &\succ &_{m_{2}}m_{2}=\mu \left( m_{2}\right) \\
m_{2} &\succ &_{w_{2}}w_{2}=\mu \left( w_{2}\right)
\end{eqnarray*}が成り立つため\(\left\{m_{2},w_{2}\right\} \)は\(\mu \)を狭義ブロックするからです。

 

コアとパレート効率性の関係

1対1のマッチング問題の私的価値モデルにおいて、状態\(\succsim _{M\cup W}\in \mathcal{R}_{M\cup W}\)においてマッチング\(\mu \in \mathcal{M}\)が狭義パレート効率的であることとは、それに対して、\begin{eqnarray*}&&\left( a\right) \ \forall i\in M\cup W:\mu ^{\prime }\left( i\right)
\succsim _{i}\mu \left( i\right) \\
&&\left( b\right) \ \exists i\in M\cup W:\mu ^{\prime }\left( i\right) \succ
_{i}\mu \left( i\right)
\end{eqnarray*}をともに満たすマッチング\(\mu ^{\prime }\in \mathcal{M}\)が存在しないことを意味します。つまり、\(\mu \)から広義パレート改善が不可能であるということです。これは同時に、提携\(M\cup W\)がマッチング\(\mu \)を広義ブロックしないことを意味します。一方、マッチング\(\mu \)が狭義コアであることとは任意の提携が\(\mu \)を広義ブロックしないことを意味するため、その場合には提携\(M\cup W\)もまた\(\mu \)を広義ブロックせず、したがって狭義パレート効率性を満たします。つまり、狭義コアは狭義パレート効率的であるということです。

命題(狭義コアは狭義パレート効率的)
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のマッチング問題の私的価値モデルにおいて、エージェント集合が、\begin{eqnarray*}
M &=&\left\{ m_{1},m_{2}\right\} \\
W &=&\left\{ w_{1},w_{2}\right\}
\end{eqnarray*}であるとともに、任意のエージェント\(i\in M\cup W\)の選好関係\(\succsim _{i}\)は完備性と推移性に加えて狭義選好の仮定を満たすものとします。具体的には、エージェントたちの選好プロファイル\(\succsim _{M\cup W}\)が以下の表によって与えられているものとします。

$$\begin{array}{cccc}\hline
エージェント\diagdown 順位 & 1 & 2 & 3 \\ \hline
m_{1} & w_{1} & w_{2} & m_{1} \\ \hline
m_{2} & w_{1} & m_{2} & w_{2} \\ \hline
w_{1} & m_{1} & m_{2} & w_{1} \\ \hline
w_{2} & m_{1} & m_{2} & w_{2} \\ \hline
\end{array}$$

表:エージェントの選好

以下のマッチング\begin{equation*}
\mu =\begin{pmatrix}
m_{1} & m_{2} \\
w_{1} & w_{2}\end{pmatrix}\end{equation*}は先の選好プロファイル\(\succsim _{M\cup W}\)のもとで狭義パレート効率的です。実際、\(m_{1}\)と\(w_{1}\)はお互いに最も望ましい相手とマッチしているため、このペアを解消する形での広義パレート改善は不可能です。\(m_{1}\)と\(w_{1}\)のペアを解消させずに\(m_{2}\)により望ましい相手とマッチさせようとすると\(w_{2}\)が\(w_{2}\)とマッチすることになり\(w_{2}\)の状態が悪化します。また、\(m_{1}\)と\(w_{1}\)のペアを解消させずに\(w_{2}\)により望ましい相手とマッチさせるのは不可能です。したがって\(\mu \)は\(\succsim _{M\cup W}\)のもとで狭義パレート効率的です。その一方で、提携\(\left\{ m_{2}\right\} \)に注目したとき、\begin{equation*}m_{2}\succ _{m_{2}}w_{2}=\mu \left( m_{2}\right)
\end{equation*}が成り立つため、提携\(\left\{ m_{2}\right\} \)はマッチング\(\mu \)を狭義にブロックします。したがって\(\mu \)は広義コアではなく、ゆえに狭義コアでもありません。ちなみに、狭義パレート効率的なマッチングは広義パレート効率的でもあるため、この\(\mu \)は広義パレート効率的である一方で広義コアではないマッチングの例にもなっています。

1対1のマッチング問題の私的価値モデルにおいて、状態\(\succsim _{M\cup W}\in \mathcal{R}_{M\cup W}\)においてマッチング\(\mu \in \mathcal{M}\)が広義パレート効率的であることとは、それに対して、\begin{equation*}\forall i\in M\cup W:\mu ^{\prime }\left( i\right) \succ _{i}\mu \left(
i\right)
\end{equation*}を満たすマッチング\(\mu^{\prime }\in \mathcal{M}\)が存在しないことを意味します。つまり、\(\mu \)から狭義パレート改善が不可能であるということです。これは同時に、提携\(M\cup W\)がマッチング\(\mu \)を狭義ブロックしないことを意味します。一方、マッチング\(\mu \)が広義コアであることとは任意の提携が\(\mu \)を狭義ブロックしないことを意味するため、その場合には提携\(M\cup W\)もまた\(\mu \)を狭義ブロックせず、したがって広義パレート効率性を満たします。つまり、広義コアは広義パレート効率的であるということです。

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

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

上の命題の逆は成立するとは限りません。つまり、広義パレート効率的なマッチングは広義コアであるとは限りません。先の例より明らかです。

Share on twitter
Twitterで共有
Share on email
メールで共有
RELATED KNOWLEDGE

関連知識

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

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

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

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

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

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

ベイジアンゲーム
メカニズムのもとでのゲーム

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

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

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

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

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

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

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

メカニズム
非分割財の交換問題における競争均衡メカニズム

分割財の交換問題(シャプレー・スカーフの住宅市場)に対して便宜的に価格体系を導入したとき、配分と価格ベクトルの組が予算制約条件と選好最大化条件を満たすのであれば、そのような組を競争均衡と呼びます。また、競争的な配分を常に選び取るメカニズムを競争均衡メカニズムと呼びます。

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

1対1のマッチング問題(安定結婚問題)におけるマッチングが安定的であること、また、メカニズムが安定的であることの意味を解説します。安定性は広義コアと概念として一致します。

DISCUSSION

質問とコメント

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

1対1のマッチング問題