教材一覧
教材一覧
教材検索

1対1のマッチング問題

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

目次

Twitter
Mailで保存

誘因両立的なメカニズム

1対1のマッチング問題におけるメカニズム\(\phi :\mathcal{R}_{M\cup W}\rightarrow \mathcal{M}\)のもとでのベイジアンゲーム\(G\left( \phi \right) \)において純粋戦略の組\(s_{M\cup W}\in S_{M\cup W}\)が均衡になる場合(均衡の具体的な内容は後述)、それぞれの状態\(\succsim _{M\cup W}\in \mathcal{R}_{M\cup W}\)において、それぞれのエージェント\(i\in M\cup W\)は自身の均衡戦略\(s_{i}\)にもとづいて最適な選好\(s_{i}\left( \succsim _{i}\right) \in \mathcal{R}_{i}\)を申告します。状態\(\succsim_{M\cup W}\)においてエージェントたちが申告する選好からなるの組を\(s_{M\cup W}\left( \succsim _{M\cup W}\right) =\left( s_{i}\left( \succsim_{i}\right) \right) _{i\in M\cup W}\)と表記するのであれば、それに対してメカニズム\(\phi \)は以下のマッチング\begin{equation*}\phi \left( s_{M\cup W}\left( \succsim _{M\cup W}\right) \right) =\left(
\phi _{i}\left( s_{M\cup W}\left( \succsim _{M\cup W}\right) \right) \right)
_{i\in M\cup W}\in \mathcal{M}
\end{equation*}を選択します。このとき、メカニズム\(\phi \)は状態\(\succsim _{M\cup W}\)において上のマッチングを遂行する(implment)と言います。また、上のマッチングを状態\(\succsim_{M\cup W}\)における均衡マッチング(equilibrium matching)や均衡結果(equilibrium outcome)などと呼びます。

一般に、メカニズム\(\phi \)のもとでのベイジアンゲーム\(G\left( \phi \right) \)に均衡は存在するとは限りません。しかし、仮にマッチメイカーが、ゲーム\(G\left( \phi \right) \)に均衡が存在するようなメカニズム\(\phi \)の設計に成功したとしましょう。均衡はエージェントたちにとっての最適戦略の組であるため、エージェントたちが自身にとってより望ましいマッチングを達成するために利己的に行動することを前提とした場合においても、そのようなメカニズム\(\phi \)のもとでは、それぞれの状態\(\succsim _{M\cup W}\)において、マッチメイカーは均衡結果\(\phi \left(s_{M\cup W}\left( \succsim _{M\cup W}\right) \right) \)を遂行できることになります。言い換えると、均衡が存在するようなメカニズムの設計に成功すれば、エージェントたちの行動を均衡へ誘導することに成功し、それぞれの状態\(\succsim _{M\cup W}\)において、そこでの均衡結果\(\phi \left( s_{M\cup W}\left( \succsim _{M\cup W}\right)\right) \)が実現することを理論的に予測できるようになるということです。

では、マッチメイカーはエージェントたちをどのような均衡へ誘導すべきでしょうか。1対1のマッチング問題においてインセンティブの問題が発生する原因は、エージェントたちが自身の真の選好を私的情報として持っていることにあります。インセンティブの問題を解決するためには、何らかの方法を通じて情報の非対称性を解消する必要があります。具体的には、それぞれのエージェントにとって、自分の真の選好を正直に申告することが得であるようなメカニズムを設計すれば、そのようなメカニズムのもと、エージェントたちは自分の真の選好を自ら進んで正直に申告するため、結果として情報の非対称性は解消されます。

繰り返しになりますが、メカニズム\(\phi \)のもとでのベイジアンゲーム\(G\left( \phi \right) \)において、それぞれのエージェント\(i\in M\cup W\)の純粋戦略は写像\(s_{i}:\mathcal{R}_{i}\rightarrow \mathcal{R}_{i}\)として定式化されます。この純粋戦略\(s_{i}\)のもとで、エージェント\(i\)は自分のタイプが\(\succsim _{i}\in \mathcal{R}_{i}\)の場合に選好\(s_{i}\left( \succsim _{i}\right) \in \mathcal{R}_{i}\)を申告します。特に、エージェント\(i\)の純粋戦略\(s_{i}\)が以下の条件\begin{equation*}\forall \succsim _{i}\in \mathcal{R}_{i}:s_{i}\left( \succsim _{i}\right)
=\succsim _{i}
\end{equation*}を満たすとき、すなわち、エージェント\(i\)が純粋戦略\(s_{i}\)のもとで常に自身のタイプ\(\succsim _{i}\)をそのまま正直に申告する場合、このような\(s_{i}\)を正直戦略(honest strategy)と呼びます。仮に、メカニズムのもとでのベイジアンゲーム\(G\left( \phi \right) \)において、すべてのエージェント\(i\)が正直戦略\(s_{i}\)を選択することが均衡になるのであれば、それぞれの状態\(\succsim _{M\cup W}\)において、エージェントたちが申告する選好からなる組は、\begin{eqnarray*}s_{M\cup W}\left( \succsim _{M\cup W}\right) &=&\left( s_{i}\left( \succsim
_{i}\right) \right) _{i\in M\cup W} \\
&=&\left( \succsim _{i}\right) _{i\in M\cup W}\quad \because \text{正直戦略の定義} \\
&=&\succsim _{M\cup W}
\end{eqnarray*}となり、これは真の状態と一致します。つまり、正直戦略の組が均衡になるようなメカニズム\(\phi \)のもとでは、それぞれの状態\(\succsim _{M\cup W}\)において、任意のエージェント\(i\)が自身の真の選好\(\succsim_{i}\)をそのまま正直に表明することが最適になるため、結果として、情報の非対称性が解消されます。そこで、このようなメカニズム\(\phi \)を誘因両立的(incentive compatible)なメカニズムと呼びます。1対1のマッチング問題におけるインセンティブの問題を解消するため、マッチメイカーは誘因両立的なメカニズムを設計する必要があります。

 

耐戦略的なメカニズム

メカニズム\(\phi \)のもとでのベイジアンゲーム\(G\left( \phi \right) \)において、エージェント\(i\)の純粋戦略\(s_{i}\)を選びます。状態\(\succsim _{M\cup W}=(\succsim _{i},\succsim _{-i})\)を任意に選んだとき、エージェント\(i\)が先の\(s_{i}\)を選択するならば選好\(s_{i}\left( \succsim _{i}\right) \)を申告します。このとき、他のエージェントたちが申告する選好からなる組が\(\hat{\succsim}_{-i}\)であれば、以上の選好の組に対してメカニズム\(\phi \)は以下のマッチング\begin{equation*}\phi \left( s_{i}\left( \succsim _{i}\right) ,\hat{\succsim}_{-i}\right) \in
\mathcal{M}
\end{equation*}を定めます。一方、他のエージェントたちが申告する選好が\(\hat{\succsim}_{-i}\)である一方で、エージェント\(i\)が\(s_{i}\left(\succsim _{i}\right) \)と一致するとは限らない何らかの選好\(\hat{\succsim}_{i}\)を申告する場合、メカニズム\(\phi \)は以下のマッチング\begin{equation*}\phi \left( \hat{\succsim}_{i},\hat{\succsim}_{-i}\right) \in \mathcal{M}
\end{equation*}を定めます。以上を踏まえた上で、状態\(\succsim _{M\cup W}\in \mathcal{R}_{M\cup W}\)と全員が申告する選好からなる組\(\hat{\succsim}_{M\cup W}\in \mathcal{R}_{M\cup W}\)をそれぞれ任意に選んだときに、\begin{equation*}\phi \left( s_{i}\left( \succsim _{i}\right) ,\hat{\succsim}_{-i}\right) \
\succsim _{i}^{\mathcal{M}}\left[ \succsim _{M\cup W}\right] \ \phi \left(
\hat{\succsim}_{i},\hat{\succsim}_{-i}\right)
\end{equation*}が成り立つ場合には、エージェント\(i\)にとって\(s_{i}\)は支配戦略(dominant strategy)であると言います。これは、エージェント\(i\)にとって、自身のタイプ\(\succsim _{i}\)や他のエージェントたちのタイプ\(\succsim _{-i}\)がいかなるものであるかに関わらず、また、他のエージェントたちが申告する選好\(\hat{\succsim}_{-i}\)に関わらず、自身は\(s_{i}\)にしたがって行動することで常に自身が得る満足度を最大化できることを意味します。したがって、エージェント\(i\)が支配戦略\(s_{i}\)を持つ場合、エージェント\(i\)は自身を含めた全員のタイプや他のエージェントたちが申告する選好について何も考える必要はなく、常に\(s_{i}\)にしたがって行動することが最適になります。

メカニズム\(\phi \)のもとでのベイジアンゲーム\(G\left( \phi \right) \)において、エージェントたちの純粋戦略の組\(s_{M\cup W}=\left(s_{i}^{\ast }\right) _{i\in M\cup W}\)が支配戦略の組であるならば、すなわち、エージェント\(i\in M\cup W\)と状態\(\succsim _{M\cup W}\in \mathcal{R}_{M\cup W}\)および全員が申告する選好からなる組\(\hat{\succsim}_{M\cup W}\in \mathcal{R}_{M\cup W}\)をそれぞれ任意に選んだときに、\begin{equation}\phi \left( s_{i}\left( \succsim _{i}\right) ,\hat{\succsim}_{-i}\right) \
\succsim _{i}^{\mathcal{M}}\left[ \succsim _{M\cup W}\right] \ \phi \left(
\hat{\succsim}_{i},\hat{\succsim}_{-i}\right) \quad \cdots (1)
\end{equation}が成り立つのであれば、そのような純粋戦略の組\(s_{M\cup W}\)を支配戦略均衡(dominant strategy equilibrium)と呼びます。

純粋戦略の組\(s_{M\cup W}=\left(s_{i}\right) _{i\in M\cup W}\)が正直戦略の組である場合には、\begin{equation}\forall i\in M\cup W,\ \forall \succsim _{i}\in \mathcal{R}_{i}:s_{i}\left(
\succsim _{i}\right) =\succsim _{i} \quad \cdots (2)
\end{equation}が成り立つため、正直戦略の組\(\succsim _{M\cup W}\)が支配戦略均衡であることとは、\(\left( 1\right) \)および\(\left( 2\right) \)より、エージェント\(i\in M\cup W\)と状態\(\succsim _{M\cup W}\in \mathcal{R}_{M\cup W}\)および全員が申告する選好からなる組\(\hat{\succsim}_{M\cup W}\in \mathcal{R}_{M\cup W}\)をそれぞれ任意に選んだときに、\begin{equation*}\phi \left( \succsim _{i},\hat{\succsim}_{-i}\right) \ \succsim _{i}^{\mathcal{M}}\left[ \succsim _{M\cup W}\right] \ \phi \left( \hat{\succsim}_{i},\hat{\succsim}_{-i}\right)
\end{equation*}が成り立つことを意味します。そこで、以上の条件が成り立つとき、すなわち、メカニズムのもとでのベイジアンゲーム\(G\left( \phi \right) \)において正直戦略の組が支配戦略均衡になる場合、メカニズム\(\phi \)は耐戦略的(strategy-proofness)であるとか支配戦略均衡誘因両立的(incentive compatible inweakly dominant strategy equilibrium:DIC)であるなどと言います。

メカニズム\(\phi \)が耐戦略的である場合、任意のエージェントは、自身を含めた全員のタイプがいかなるものであるかに関わらず、また、他のエージェントたちが申告する選好がいかなるものであるかに関わらず、自分は正直戦略にしたがって行動すれば常に自身が得る満足度を最大化できます。したがって、エージェントは自身を含めた全員のタイプについて何も考える必要はなく、また、他のエージェントたちの行動について考える必要もなく、正直戦略にしたがいさえすれば最適な結果が得られます。

例(私的価値モデルの場合)
1対1のマッチング問題の私的価値モデルにおいては、任意のエージェント\(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\)の純粋戦略\(s_{i}\)が他のエージェントたちの純粋戦略\(s_{-i}\)に対する支配戦略であることは、\begin{equation*}\forall \succsim _{i}\in \mathcal{R}_{i},\ \forall \hat{\succsim}_{M\cup
W}\in \mathcal{R}_{M\cup W}:\phi _{i}\left( s_{i}\left( \succsim _{i}\right)
,\hat{\succsim}_{-i}\right) \succsim _{i}\phi _{i}\left( \hat{\succsim}_{i},\hat{\succsim}_{-i}\right)
\end{equation*}が成り立つことを意味し、純粋戦略の組\(s_{M\cup W}\)が支配戦略均衡であることは、\begin{equation*}\forall i\in M\cup W,\ \forall \succsim _{i}\in \mathcal{R}_{i},\ \forall
\hat{\succsim}_{M\cup W}\in \mathcal{R}_{M\cup W}:\phi _{i}\left(
s_{i}\left( \succsim _{i}\right) ,\hat{\succsim}_{-i}\right) \succsim
_{i}\phi _{i}\left( \hat{\succsim}_{i},\hat{\succsim}_{-i}\right)
\end{equation*}が成り立つことを意味します。したがって、メカニズム\(\phi \)が耐戦略的であることは、\begin{equation*}\forall i\in M\cup W,\ \forall \succsim _{i}\in \mathcal{R}_{i},\ \forall
\hat{\succsim}_{M\cup W}\in \mathcal{R}_{M\cup W}:\phi _{i}\left( \succsim
_{i},\hat{\succsim}_{-i}\right) \succsim _{i}\phi _{i}\left( \hat{\succsim}_{i},\hat{\succsim}_{-i}\right)
\end{equation*}が成り立つことを意味します。ちなみにこれは、\begin{equation*}
\forall i\in M\cup W,\ \forall \succsim _{M\cup W}\in \mathcal{R}_{M\cup
W},\ \forall \hat{\succsim}_{i}\in \mathcal{R}_{i}:\phi _{i}\left( \succsim
_{i},\succsim _{-i}\right) \succsim _{i}\phi _{i}\left( \hat{\succsim}_{i},\succsim _{-i}\right)
\end{equation*}と必要十分です(演習問題)。

 

支配戦略均衡に関する表明原理

耐戦略的なメカニズムとは、正直戦略の組が支配戦略均衡になるようなメカニズムであるという意味において、特殊な支配戦略均衡メカニズムです。一方、正直戦略の組であるとは限らない純粋戦略の組を支配戦略均衡として遂行するメカニズムに対しいて、その均衡結果と同じ結果を遂行する耐戦略的メカニズムが存在することを保証できます。これを表明原理(revelation principle)と呼びます。

命題(支配戦略均衡に関する表明原理)
1対1のマッチング問題において、メカニズム\(\phi \)のもとで純粋戦略の組\(s_{M\cup W}\in S_{M\cup W}\)が支配戦略均衡であるものとする。これに対して、任意の状態において、先のメカニズム\(\phi \)が遂行する均衡結果と同じ結果を遂行する耐戦略的メカニズム存在する。すなわち、\begin{equation*}\forall \succsim _{M\cup W}\in \mathcal{R}_{M\cup W}:\phi ^{\prime }\left(
\succsim _{M\cup W}\right) =\phi \left( s_{M\cup W}\left( \succsim _{M\cup
W}\right) \right)
\end{equation*}を満たす耐戦略的メカニズム\(\phi ^{\prime }\)が存在する。
証明

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

以上の命題より、耐戦略的なメカニズムのもとで遂行可能な配分は、誘因両立的であるとは限らないメカニズムによって支配戦略均衡として遂行される配分の全体を網羅していることが明らかになりました。したがって、支配戦略均衡メカニズムについて考える際には、耐戦略的なメカニズムに対象を限定しても一般性は失われません。

 

集団耐戦略的なメカニズム

繰り返しになりますが、メカニズム\(\phi \)が耐戦略的であるためには、そのメカニズムに参加するすべてのエージェントにとって正直戦略が支配戦略になる必要があります。ただ、場合によっては、すべてのエージェントにとっては正直戦略が支配戦略にはならないものの、エージェントの部分集合\(T\subset M\cup W\)に属する任意のエージェントにとって正直戦略が支配戦略になるようなメカニズム\(\phi \)を模索することがあります。つまり、以下の条件\begin{equation*}\forall i\in T,\ \forall \succsim _{M\cup W}\in \mathcal{R}_{M\cup W},\
\forall \hat{\succsim}_{M\cup W}\in \mathcal{R}_{M\cup W}:\phi \left(
\succsim _{i},\hat{\succsim}_{-i}\right) \ \succsim _{i}^{\mathcal{M}}\left[
\succsim _{M\cup W}\right] \ \phi \left( \hat{\succsim}_{i},\hat{\succsim}_{-i}\right)
\end{equation*}を満たすメカニズム\(\phi \)について考えるということです。以上の性質を満たすメカニズム\(\phi \)を\(T\)にとって集団耐戦略的(groupstrategy-proof)なメカニズムと呼びます。

例(私的価値モデルの場合)
繰り返しになりますが、1対1のマッチング問題の私的価値モデルにおいてメカニズム\(\phi \)が耐戦略的であることは、\begin{equation*}\forall i\in M\cup W,\ \forall \succsim _{i}\in \mathcal{R}_{i},\ \forall
\hat{\succsim}_{M\cup W}\in \mathcal{R}_{M\cup W}:\phi _{i}\left( \succsim
_{i},\hat{\succsim}_{-i}\right) \succsim _{i}\phi _{i}\left( \hat{\succsim}_{i},\hat{\succsim}_{-i}\right)
\end{equation*}が成り立つことを意味します。したがって、メカニズム\(\phi \)がエージェントの部分集合\(T\subset M\cup W\)にとって集団耐戦略的であることとは、\begin{equation*}\forall i\in T,\ \forall \succsim _{i}\in \mathcal{R}_{i},\ \forall \hat{\succsim}_{M\cup W}\in \mathcal{R}_{M\cup W}:\phi _{i}\left( \succsim _{i},\hat{\succsim}_{-i}\right) \succsim _{i}\phi _{i}\left( \hat{\succsim}_{i},\hat{\succsim}_{-i}\right)
\end{equation*}が成り立つことを意味します。ちなみにこれは、\begin{equation*}
\forall i\in T,\ \forall \succsim _{M\cup W}\in \mathcal{R}_{M\cup W},\
\forall \hat{\succsim}_{i}\in \mathcal{R}_{i}:\phi _{i}\left( \succsim
_{i},\succsim _{-i}\right) \succsim _{i}\phi _{i}\left( \hat{\succsim}_{i},\succsim _{-i}\right)
\end{equation*}と必要十分です(演習問題)。

 

演習問題

問題(耐戦略的メカニズム)
1対1のマッチング問題の私的価値モデルにおいて、メカニズム\(\phi \)が耐戦略的であることは、\begin{equation*}\forall i\in M\cup W,\ \forall \succsim _{i}\in \mathcal{R}_{i},\ \forall
\hat{\succsim}_{M\cup W}\in \mathcal{R}_{M\cup W}:\phi _{i}\left( \succsim
_{i},\hat{\succsim}_{-i}\right) \succsim _{i}\phi _{i}\left( \hat{\succsim}_{i},\hat{\succsim}_{-i}\right)
\end{equation*}が成り立つことを意味しますが、この意味を説明してください。また、以上の命題は、\begin{equation*}
\forall i\in M\cup W,\ \forall \succsim _{M\cup W}\in \mathcal{R}_{M\cup
W},\ \forall \hat{\succsim}_{i}\in \mathcal{R}_{i}:\phi _{i}\left( \succsim
_{i},\succsim _{-i}\right) \succsim _{i}\phi _{i}\left( \hat{\succsim}_{i},\succsim _{-i}\right)
\end{equation*}と必要十分であることを証明した上で、この新たな命題の意味を説明してください。

解答を見る

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

Twitter
Mailで保存

質問とコメント