組合せオークションにおける誘因両立的メカニズム

誘因両立的なメカニズム

組合せオークション環境におけるメカニズム\(\left( a,t\right) \)のもとでのベイジアンゲーム\(G\left(a,t\right) \)において純粋戦略の組\(s_{I}\in S_{I}\)が均衡になる場合には（均衡の具体的な内容は後述）、状態\(\theta _{I}\in \Theta _{I}\)を任意に選んだとき、それぞれの入札者\(i\in I\)は自身の均衡戦略\(s_{i}\)にもとづいて最適な評価関数\(s_{i}\left( \theta _{i}\right) \in \Theta _{i}\)を申告するため、エージェントたちが均衡において申告する評価関数からなる組は、\begin{equation*}s_{I}\left( \theta _{I}\right) =\left( s_{i}\left( \theta _{i}\right)
\right) _{i\in I}\in \Theta _{I}
\end{equation*}であり、これに対してメカニズム\(\left( a,t\right) \)は以下の結果\begin{equation*}\left( a\left( s_{I}\left( \theta _{I}\right) \right) ,t\left( s_{I}\left(
\theta _{I}\right) \right) \right) =\left( \left( a_{i}\left( s_{I}\left(
\theta _{I}\right) \right) \right) _{i\in I},\left( t_{i}\left( s_{I}\left(
\theta _{I}\right) \right) \right) _{i\in I}\right) \in A\times \mathbb{R} ^{n}
\end{equation*}を選択します。このとき、メカニズム\(\left(a,t\right) \)は状態\(\theta _{I}\)において上の結果を遂行する（implement）と言います。また、上の結果を状態\(\theta _{I}\)における均衡結果（equilibrium outcome）と呼びます。

一般に、メカニズム\(\left( a,t\right) \)のもとでのベイジアンゲーム\(G\left( a,t\right) \)に均衡は存在するとは限りません。しかし、仮にオークションの主催者が、ゲーム\(G\left( a,t\right) \)に均衡が存在するようなメカニズム\(\left( a,t\right) \)の設計に成功したとしましょう。均衡\(s_{I}\)はそれぞれの入札者たちにとって最適な純粋戦略からなる組であるため、入札者たちが自身にとってより望ましい結果を達成するために利己的に行動することを前提とした場合においても、そのようなメカニズム\(\left( a,t\right) \)のもとでは、それぞれの状態\(\theta _{I}\)において、主催者は均衡結果\(\left( a\left( s_{I}\left( \theta _{I}\right) \right) ,t\left( s_{I}\left(\theta _{I}\right) \right) \right) \)を遂行できることになります。言い換えると、均衡\(s_{I}\)が存在するようなメカニズム\(\left( a,t\right) \)の設計に成功すれば、入札者たちの行動を均衡へ導くことに成功し、それぞれの状態\(\theta _{I}\)において均衡結果\(\left( a\left( s_{I}\left( \theta _{I}\right) \right) ,t\left( s_{I}\left(\theta _{I}\right) \right) \right) \)が実現することを理論的に予測できるようになります。

では、主催者は入札者たちをどのような均衡へ誘導すべきでしょうか。組合せオークション市場においてインセンティブの問題が発生する原因は、入札者たちがパッケージどうしを比較する評価関数を私的情報として持っていることにあります。インセンティブの問題を解決するためには何らかの方法を通じて情報の非対称性を解消する必要があります。具体的には、それぞれの入札者にとって、自身の評価関数を正直に申告することが得であるようなメカニズムを設計すれば、そのようなメカニズムのもと、入札者たちは真の評価関数を自ら進んで正直に申告するため、結果として情報の非対称性は解消されます。

繰り返しになりますが、メカニズムのもとでのベイジアンゲーム\(G\left( a,t\right) \)において、それぞれの入札者\(i\in I\)の純粋戦略は写像\(s_{i}:\Theta _{i}\rightarrow \Theta _{i}\)として定式化されます。この純粋戦略\(s_{i}\)のもとで、入札者\(i\)は自分のタイプが\(\theta _{i}\in \Theta _{i}\)である場合に評価関数\(s_{i}\left( \theta_{i}\right) \in \Theta _{i}\)を申告します。特に、入札者\(i\)の純粋戦略\(s_{i}\)が以下の条件\begin{equation*}\forall \theta _{i}\in \Theta _{i}:s_{i}\left( \theta _{i}\right) =\theta
_{i}
\end{equation*}を満たすとき、すなわち、入札者\(i\)が純粋戦略\(s_{i}\)のもとで常に真の評価関数をそのまま正直に申告する場合、このような\(s_{i}\)を正直戦略（honest strategy）と呼びます。仮に、メカニズムのもとでのベイジアンゲーム\(G\left( a,t\right) \)においてすべての入札者\(i\)が正直戦略\(s_{i}\)を選択することが均衡になるのであれば、それぞれの状態\(\theta _{I}\)において、入札者たちが申告する評価関数からなる組は、\begin{eqnarray*}s_{I}\left( \theta _{I}\right) &=&\left( s_{i}\left( \theta _{i}\right)
\right) _{i\in I} \\
&=&\left( \theta _{i}\right) _{i\in I}\quad \because s_{i}\text{は正直戦略} \\
&=&\theta _{I}
\end{eqnarray*}となり、これは真の状態と一致します。つまり、正直戦略の組が均衡になるようなメカニズム\(\left( a,t\right) \)のもとでは、それぞれの状態\(\theta _{I}\)において、任意の入札者\(i\)が真の評価関数\(\theta _{i}\)をそのまま正直に申告することが最適になるため、結果として、情報の非対称性が解消されます。そこで、このようなメカニズム\(\left( a,t\right) \)を誘因両立的（incentive compatible）なメカニズムと呼びます。組合せオークション市場におけるインセンティブの問題を解消するため、オークションの主催者は誘因両立的なメカニズムを設計する必要があります。

事後均衡誘因両立的なメカニズム

メカニズムのもとでのベイジアンゲーム\(G\left( a,t\right) \)において、入札者\(i\in I\)が他の入札者たちの純粋戦略\(s_{-i}\in S_{-i}\)に直面した状況を想定します。仮に他の入札者たちのタイプが\(\theta _{-i}\in \Theta _{-i}\)である場合、彼らが申告する評価関数からなる組は\(s_{-i}\left( \theta _{-i}\right) \in \Theta _{-i}\)となります。仮に入札者\(i\)のタイプが\(\theta _{i}\in \Theta _{i}\)であり、なおかつ純粋戦略\(s_{i}\in S_{i}\)を選ぶのであれば、入札者\(i\)が申告する評価関数は\(s_{i}\left( \theta_{i}\right) \in \Theta _{i}\)となります。全員が申告する評価関数からなる組を、\begin{equation*}s_{I}\left( \theta _{I}\right) =\left( s_{i}\left( \theta _{i}\right)
,s_{-i}\left( \theta _{-i}\right) \right) \in \Theta _{I}
\end{equation*}と表記するのであれば、これに対してメカニズム\(\left( a,t\right) \)が定める結果は、\begin{equation*}\left( a\left( s_{I}\left( \theta _{I}\right) \right) ,t\left( s_{I}\left(
\theta _{I}\right) \right) \right) \in A\times \mathbb{R} ^{n}
\end{equation*}となります。以上のタイプの組から構成される状態\(\theta _{I}=\left( \theta_{i},\theta _{-i}\right) \)における入札者\(i\)の利得関数は\(u_{i}\left(\cdot ,\theta _{I}\right) \)であるため、以上の想定のもとで入札者\(i\)が得る利得は、\begin{equation*}u_{i}\left( a\left( s_{I}\left( \theta _{I}\right) \right) ,t\left(
s_{I}\left( \theta _{I}\right) \right) ,\theta _{I}\right) \in \mathbb{R} \end{equation*}であり、入札者\(i\)はこの利得を事前に把握しています。他の入札者たちが\(s_{-i}\)を選ぶという前提のもとで自身は\(s_{i}\)を選ぶ場合、状態\(\theta _{I}\)によらず、利得を常に最大化できる場合には、すなわち、状態\(\theta _{I}\in \Theta _{I}\)と入札者\(i\)の評価関数\(\hat{\theta}_{i}\in \Theta _{i}\)をそれぞれ任意に選んだときに、\begin{equation*}u_{i}\left( a\left( s_{I}\left( \theta _{I}\right) \right) ,t\left(
s_{I}\left( \theta _{I}\right) \right) ,\theta _{I}\right) \geq u_{i}\left(
a\left( \hat{\theta}_{i},s_{-i}\left( \theta _{-i}\right) \right) ,t\left(
\hat{\theta}_{i},s_{-i}\left( \theta _{-i}\right) \right) ,\theta
_{I}\right)
\end{equation*}が成り立つ場合には、\(s_{i}\)を\(s_{-i}\)に対する事後最適反応（ex-post best response）と呼びます。つまり、メカニズムのもとでのベイジアンゲーム\(\left( a,t\right) \)において入札者\(i\)の純粋戦略\(s_{i}\)が他の入札者たちの純粋戦略\(s_{-i}\)に対する事後最適反応であることとは、他の入札者たちが\(s_{-i}\)にしたがって行動することを前提とした場合、自分は\(s_{i}\)にしたがって行動すれば、全員のタイプ\(\theta _{I}\)によらず、自身が直面する利得を常に最大化できることを意味します。したがって、入札者\(i\)が\(s_{-i}\)に対する事後最適反応\(s_{i}\)を持つ場合、入札者\(i\)は自身を含めた全員のタイプについて何も考える必要はなく、他の入札者たちが\(s_{-i}\)にしたがって行動する限りにおいて、自分は常に\(s_{i}\)にしたがって行動することが最適になります。

メカニズム\(\left( a,t\right) \)のもとでのベイジアンゲーム\(G\left( a,t\right) \)において、純粋戦略の組\(s_{I}=\left( s_{i}\right)_{i\in I}\)がお互いに事後最適反応になっているのであれば、すなわち、入札者\(i\in I\)と状態\(\theta _{I}\in \Theta _{I}\)および入札者\(i\)の評価関数\(\hat{\theta}_{i}\in \Theta _{i}\)をそれぞれ任意に選んだときに、\begin{equation}u_{i}\left( a\left( s_{I}\left( \theta _{I}\right) \right) ,t\left(
s_{I}\left( \theta _{I}\right) \right) ,\theta _{I}\right) \geq u_{i}\left(
a\left( \hat{\theta}_{i},s_{-i}\left( \theta _{-i}\right) \right) ,t\left(
\hat{\theta}_{i},s_{-i}\left( \theta _{-i}\right) \right) ,\theta
_{I}\right) \quad \cdots (1)
\end{equation}が成り立つのであれば、そのような純粋戦略の組\(s_{I}\)を事後均衡（ex-post equilibrium）と呼びます。

純粋戦略の組\(s_{I}=\left( s_{i}\right)_{i\in I}\)が正直戦略の組である場合には、\begin{equation}\forall i\in I,\ \forall \theta _{i}\in \Theta _{i}:s_{i}\left( \theta
_{i}\right) =\theta _{i} \quad \cdots (2)
\end{equation}が成り立つため、正直戦略の組\(s_{I}\)が事後均衡であることとは、\(\left( 1\right) \)および\(\left( 2\right) \)より、入札者\(i\in I\)と状態\(\theta _{I}\in \Theta _{I}\)および入札者\(i\)の評価関数\(\hat{\theta}_{i}\in \Theta _{i}\)をそれぞれ任意に選んだときに、\begin{equation*}u_{i}\left( a\left( \theta _{I} \right) ,t\left(
\theta _{I} \right) ,\theta _{I}\right) \geq u_{i}\left(
a\left( \hat{\theta}_{i},\theta _{-i}\right) ,t\left( \hat{\theta}_{i},\theta _{-i}\right) ,\theta _{I}\right)
\end{equation*}が成り立つことを意味します。そこで、以上の条件が成り立つとき、すなわち、メカニズム\(\left( a,t\right) \)のもとでのベイジアンゲーム\(G\left( a,t\right) \)において正直戦略の組が事後均衡になる場合、メカニズム\(\left( a,t\right) \)は事後均衡誘因両立的（incentive compatible in ex post equilibrium：EPIC）であると言います。

メカニズム\(\left( a,t\right) \)が事後均衡誘因両立的である場合、任意の入札者は、自身を含めた全員のタイプがいかなるものであるかに関わらず、他の入札者たちが正直戦略にしたがって行動することを前提とした場合、自分もまた正直戦略にしたがって行動すれば常に利得を最大化できます。つまり、入札者は自身を含めた全員のタイプについて何も考える必要はなく、他の入札者たちが正直戦略にしたがう場合、自分もまた正直戦略にしたがうことが最適であり、そこから逸脱する動機を持たないということです。

事後均衡誘因両立的なメカニズムは正直戦略の組が事後均衡になるようなメカニズムであるという意味において特殊な事後均衡メカニズムです。一方、正直戦略の組であるとは限らない純粋戦略の組を事後均衡として遂行するメカニズムに対して、その均衡結果と同じ結果を遂行する事後均衡誘因両立的なメカニズムが存在することを保証できます。これは事後均衡に関する表明原理です。

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

耐戦略的なメカニズム

メカニズムのもとでのベイジアンゲーム\(G\left( a,t\right) \)において、入札者\(i\in I\)が他の入札者たちの評価関数\(\hat{\theta}_{-i}\in \Theta_{-i}\)に直面した状況を想定します。仮に状態が\(\theta _{I}=\left( \theta _{i},\theta _{-i}\right) \in\Theta _{I}\)であり、なおかつ入札者\(i\)が純粋戦略\(s_{i}\in S_{i}\)を選ぶのであれば、入札者\(i\)が申告する評価関数は\(s_{i}\in \left( \theta _{i}\right)\in \Theta _{i}\)となります。全員が申告する評価関数からなる組は、\begin{equation*}\left( s_{i}\left( \theta _{i}\right) ,\hat{\theta}_{-i}\right) \in \Theta
_{I}
\end{equation*}であるため、これに対してメカニズム\(\left(a,t\right) \)が定める結果は、\begin{equation*}\left( a\left( s_{i}\left( \theta _{i}\right) ,\hat{\theta}_{-i}\right)
,t\left( s_{i}\left( \theta _{i}\right) ,\hat{\theta}_{-i}\right) \right)
\in A\times \mathbb{R} ^{n}
\end{equation*}となります。以上の状態\(\theta _{I}\)における入札者\(i\)の利得関数は\(u_{i}\left(\cdot ,\theta _{I}\right) \)であるため、以上の想定のもとで入札者\(i\)が得る利得は、\begin{equation*}u_{i}\left( a\left( s_{i}\left( \theta _{i}\right) ,\hat{\theta}_{-i}\right)
,t\left( s_{i}\left( \theta _{i}\right) ,\hat{\theta}_{-i}\right) ,\theta
_{I}\right) \in \mathbb{R} \end{equation*}であり、入札者\(i\)はこの利得を事前に把握しています。入札者\(i\)が\(s_{i}\)を選ぶ場合、他の入札者が申告する評価関数\(\hat{\theta}_{-i}\)や状態\(\theta _{I}\)によらず、利得を常に最大化できる場合には、すなわち、状態\(\theta _{I}\in \Theta _{I}\)と他の入札者たちの評価関数\(\hat{\theta}_{-i}\in \Theta _{-i}\)および自身の評価関数\(\hat{\theta}_{i}\in \Theta _{i}\)をそれぞれ任意に選んだときに、\begin{equation*}u_{i}\left( a\left( s_{i}\left( \theta _{i}\right) ,\hat{\theta}_{-i}\right)
,t\left( s_{i}\left( \theta _{i}\right) ,\hat{\theta}_{-i}\right) ,\theta
_{I}\right) \geq u_{i}\left( a\left( \hat{\theta}_{i},\hat{\theta}_{-i}\right) ,t\left( \hat{\theta}_{i},\hat{\theta}_{-i}\right) ,\theta
_{I}\right)
\end{equation*}すなわち、\begin{equation*}
u_{i}\left( a\left( s_{i}\left( \theta _{i}\right) ,\hat{\theta}_{-i}\right)
,t\left( s_{i}\left( \theta _{i}\right) ,\hat{\theta}_{-i}\right) ,\theta
_{I}\right) \geq u_{i}\left( a\left( \hat{\theta}_{I}\right) ,t\left( \hat{\theta}_{I}\right) ,\theta _{I}\right)
\end{equation*}が成り立つ場合には、\(s_{i}\)を支配戦略（dominant strategy）と呼びます。つまり、メカニズムのもとでのベイジアンゲーム\(\left( a,t\right) \)において入札者\(i\)の純粋戦略\(s_{i}\)が支配戦略であることとは、自身のタイプ\(\theta _{i}\)や他の入札者たちのタイプ\(\theta _{-i}\)がいかなるものであるかに関わらず、また、他の入札者たちが申告する評価関数\(\hat{\theta}_{-i}\)がいかなるものであるかに関わらず、自身は\(s_{i}\)にしたがって行動すれば常に自身が直面する利得を最大化できることを意味します。したがって、入札者\(i\)が支配戦略\(s_{i}\)を持つ場合、入札者\(i\)は自身を含めた全員のタイプや他の入札者たちが申告する評価関数について何も考える必要はなく、常に\(s_{i}\)にしたがって行動することが最適になります。

メカニズムのもとでのベイジアンゲーム\(G\left( a,t\right) \)において、純粋戦略の組\(s_{I}=\left( s_{i}\right) _{i\in I}\)がお互いに支配戦略になっているのであれば、すなわち、入札者\(i\in I\)と状態\(\theta _{I}\in \Theta _{I}\)および全員の評価関数からなる組\(\hat{\theta}_{I}\in \Theta _{I}\)をそれぞれ任意に選んだときに、\begin{equation}u_{i}\left( a\left( s_{i}\left( \theta _{i}\right) ,\hat{\theta}_{-i}\right)
,t\left( s_{i}\left( \theta _{i}\right) ,\hat{\theta}_{-i}\right) ,\theta
_{I}\right) \geq u_{i}\left( a\left( \hat{\theta}_{I}\right) ,t\left( \hat{\theta}_{I}\right) ,\theta _{I}\right) \quad \cdots (1)
\end{equation}が成り立つのであれば、そのような純粋戦略の組\(s_{I}\)を支配戦略均衡（dominant strategy equilibrium）と呼びます。

純粋戦略の組\(s_{I}=\left( s_{i}\right)_{i\in I}\)が正直戦略の組である場合には、\begin{equation}\forall i\in I,\ \forall \theta _{i}\in \Theta _{i}:s_{i}\left( \theta
_{i}\right) =\theta _{i} \quad \cdots (2)
\end{equation}が成り立つため、正直戦略の組\(s_{I}\)が支配戦略均衡であることとは、\(\left( 1\right) \)および\(\left(2\right) \)より、入札者\(i\in I\)と状態\(\theta _{I}\in \Theta _{I}\)および全員の評価関数からなる組\(\hat{\theta}_{I}\in \Theta _{I}\)をそれぞれ任意に選んだときに、\begin{equation*}u_{i}\left( a\left( \theta _{i},\hat{\theta}_{-i}\right) ,t\left( \theta
_{i},\hat{\theta}_{-i}\right) ,\theta _{I}\right) \geq u_{i}\left( a\left(
\hat{\theta}_{I}\right) ,t\left( \hat{\theta}_{I}\right) ,\theta _{I}\right)
\end{equation*}が成り立つことを意味します。そこで、以上の条件が成り立つとき、すなわち、メカニズムのもとでのベイジアンゲーム\(G\left( a,t\right) \)において正直戦略の組が支配戦略均衡になる場合、メカニズム\(\left( a,t\right) \)は耐戦略的（strategy-proof）であるとか支配戦略均衡誘因両立的（incentive compatible indominant strategy equilibrium：DIC）であると言います。

メカニズム\(\left( a,t\right) \)が耐戦略的である場合、任意の入札者は、自身を含めた全員のタイプがいかなるものであるかに関わらず、また、他の入札者たちが申告する評価関数いかなるものであるかに関わらず、自分は正直戦略にしたがって行動すれば常に利得を最大化できます。つまり、入札者は自身を含めた全員のタイプについて何も考える必要はなく、また、他の入札者たちの行動について何も考える必要もなく、自分は正直戦略にしたがうことが常に最適であるということです。

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

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

メカニズム\(\left( a,t\right) \)が耐戦略的であるものとします。この場合、任意の入札者にとって、他の入札者が申告する評価関数とは関係なく、正直戦略が最適になっています。したがって、他の入札者たちが正直戦略を採用することを仮定した場合にも、任意の入札者にとって正直戦略は最適であるはずですが、これはメカニズム\(\left(a,t\right) \)が事後均衡誘因両立的であることを意味します。つまり、耐戦略的なメカニズムは事後均衡誘因両立的でもあります。

上の命題の逆は成り立つとは限りません。つまり、事後均衡誘因両立的なメカニズムは耐戦略的であるとは限りません。ただ、入札者たちの利得関数に関して私的価値の仮定が成り立つ場合には、事後均衡誘因両立的なメカニズムは耐戦略的でもあります。

以上の2つの命題より、私的価値の仮定のもとでは、メカニズムの耐戦略性と事後均衡誘因両立性は概念として一致することが明らかになりました。