WIIS

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で保存

質問とコメント

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

関連知識

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

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

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

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

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

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

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

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

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

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

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

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

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

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