組合せオークションにおけるグローヴスメカニズム

グローヴスメカニズム

組合せオークション環境において準線型性、リスク中立性、私的価値の仮定が成り立つものとします。つまり、入札者\(i\in I\)が状態\(\theta _{I}\in \Theta _{I}\)において結果\(\left( a_{I},t_{I}\right) \in A\times \mathbb{R} ^{n}\)から得る利得が、\begin{equation*}u_{i}\left( a_{I},t_{I},\theta _{I}\right) =v_{i}\left( a_{I},\theta
_{i}\right) -t_{i}
\end{equation*}であるということです。ただし、\(v_{i}\left( \cdot ,\theta_{i}\right) :A\rightarrow \mathbb{R} \)は配分の価値を特定する評価関数です。以上の状況において、メカニズム\(\left( a,t\right) :\Theta_{I}\rightarrow A\times \mathbb{R} ^{n}\)が入札者たちによる入札からなる組\(\hat{\theta}_{I}\in\Theta _{I}\)に対して定める結果が、任意の関数\(h_{i}:\Theta _{-i}\rightarrow \mathbb{R} \)を用いて、\begin{eqnarray*}\left( a\right) \ a\left( \hat{\theta}_{I}\right) &\in &\mathrm{argmax}_{a_{I}\in A}\sum_{i\in I}v_{i}\left( a_{I},\hat{\theta}_{i}\right)
\\
\left( b\right) \ t_{i}\left( \hat{\theta}_{I}\right) &=&h_{i}\left( \hat{\theta}_{-i}\right) -\sum_{j\in I\backslash \left\{ i\right\} }v_{j}\left(
a\left( \hat{\theta}_{I}\right) ,\hat{\theta}_{j}\right)
\end{eqnarray*}という形で表される場合、このようなメカニズムをグローヴスメカニズム（Groves mechanism）と呼びます。これはどのような意味を持つのでしょうか。

準線型環境を想定しているため、入札の組が\(\hat{\theta}_{I}\)であるとき、配分\(a_{I}\in A\)がもたらす社会的余剰は、\begin{equation*}\sum_{i\in I}v_{i}\left( a_{I},\hat{\theta}_{i}\right)
\end{equation*}となります。グローヴスメカニズムは、この社会的余剰を最大化するような配分を選び取る配分効率的なメカニズムです。

グローヴスメカニズムが選択する配分\(a\left( \hat{\theta}_{I}\right) \)は配分効率的であるため、グローヴスメカニズムが入札者\(i\)に対して移転する金額\begin{equation*}\sum_{j\in I\backslash \left\{ i\right\} }v_{j}\left( a\left( \hat{\theta}_{I}\right) ,\hat{\theta}_{j}\right)
\end{equation*}は、入札者\(i\)を含めたすべての入札者の間で商品を効率的に配分したときに、入札者\(i\)以外のすべての入札者たちが得る社会的余剰に相当します。グローヴスメカニズムは入札者\(i\)に対して以上の金額を支払う一方で、\(h_{i}\left( \hat{\theta}_{-i}\right) \)に相当する金額を支払わせることにより支出の穴埋めを行います。

グローヴスメカニズムの耐戦略性

組合せオークション環境におけるメカニズム\(\left( a,t\right) \)が耐戦略的であることとは、そのメカニズム\(\left( a,t\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*}が成り立つということです。特に、準線型性、リスク中立性、私的価値の仮定が成り立つ場合、入札者\(i\in I\)が状態\(\theta _{I}\in \Theta _{I}\)において結果\(\left( a_{I},t_{I}\right) \in A\times \mathbb{R} ^{n}\)から得る利得は、\begin{equation*}u_{i}\left( a_{I},t_{I},\theta _{I}\right) =v_{i}\left( a_{I},\theta
_{i}\right) -t_{i}
\end{equation*}となるため、メカニズム\(\left( a,t\right) \)が耐戦略的であることとは、入札者\(i\in I\)と状態\(\theta _{I}\in \Theta _{I}\)および全員の入札からなる組\(\hat{\theta}_{I}\in \Theta _{I}\)をそれぞれ任意に選んだときに、\begin{equation*}v_{i}\left( a\left( \theta _{i},\hat{\theta}_{-i}\right) ,\theta _{i}\right)
-t_{i}\left( \theta _{i},\hat{\theta}_{-i}\right) \geq v_{i}\left( a\left(
\hat{\theta}_{I}\right) ,\theta _{i}\right) -t_{i}\left( \hat{\theta}_{I}\right)
\end{equation*}が成り立つことを意味します。

準線型性、リスク中立性、私的価値の仮定を認める場合、グローヴスメカニズムは耐戦略的なメカニズムとなります。グローヴスメカニズムに直面した任意の入札者にとって、真の評価関数を正直に入札することが支配戦略になるということです。

準線型性、リスク中立性、私的価値の仮定が成り立つ環境においてグローヴスメカニズム\(\left( a,t\right) \)が運用されているものとします。真の状態が\(\theta_{I}=\left( \theta _{i},\theta _{-i}\right) \)である状況において、入札者\(i\)以外の入札者たちが正直戦略にしたがって\(\theta _{-i}\)を入札する一方で、入札者\(i\)が真のタイプ\(\theta _{i}\)と一致するとは限らない評価関数\(\hat{\theta}_{i}\)を入札することにより得られる利得は、\begin{eqnarray*}&&v_{i}\left( a\left( \hat{\theta}_{i},\theta _{-i}\right) ,\theta
_{i}\right) -t_{i}\left( \hat{\theta}_{i},\theta _{-i}\right) \\
&=&v_{i}\left( a\left( \hat{\theta}_{i},\theta _{-i}\right) ,\theta
_{i}\right) -\left[ h_{i}\left( \theta _{-i}\right) -\sum_{j\in I\backslash
\left\{ i\right\} }v_{j}\left( a\left( \hat{\theta}_{i},\theta _{-i}\right)
,\theta _{j}\right) \right] \quad \because t\text{の定義}
\\
&=&\sum_{j\in I}v_{j}\left( a\left( \hat{\theta}_{i},\theta _{-i}\right)
,\theta _{j}\right) -h_{i}\left( \theta _{-i}\right)
\end{eqnarray*}となります。注目すべきは、入札者\(i\)による支払い\(h_{i}\left( \theta _{-i}\right) \)は自身の入札\(\hat{\theta}_{i}\)に依存しないため、入札者\(i\)のインセンティブに影響を与えないという点です。したがって、入札者\(i\)の意思決定において重要であることは社会的余剰\begin{equation}\sum_{j\in I}v_{j}\left( a\left( \hat{\theta}_{i},\theta _{-i}\right)
,\theta _{j}\right) \quad \cdots (1)
\end{equation}の部分であり、入札者\(i\)はこれを最大化するような評価関数\(\hat{\theta}_{i}\)を入札しようとします。ただ、グローヴスメカニズムの配分ルール\(a\)は、状態\(\theta _{I}\)において、\begin{equation*}a\left( \theta _{I}\right) \in \mathrm{argmax}_{a_{I}\in
A}\sum_{j\in I}v_{j}\left( a_{I},\theta _{j}\right)
\end{equation*}を満たすため、入札者\(i\)は真の評価関数を表明することにより、すなわち、\begin{equation*}\hat{\theta}_{i}=\theta _{i}
\end{equation*}を選択することにより社会的余剰\(\left( 1\right) \)を最大化し、結果として自身が得る利得を最大化できます。つまり、グローブスメカニズムの誘因両立性を支えているのは移転ルール\(t\)の中でも入札者\(i\)に社会的余剰を移転している部分です。このような仕組みを設けることにより、入札者\(i\)による入札行動がもたらす外部効果が内部化され、その結果、入札者\(i\)が自身の真の評価関数を正直に入札するインセンティブが発生します。

グローヴスメカニズムが誘因両立性であることは私的価値の仮定に依存します。グローヴスメカニズムの移転ルール\(t\)は入札の組\(\hat{\theta}_{I}\in \Theta _{I}\)に対して、\begin{equation}t_{i}\left( \hat{\theta}_{I}\right) =h_{i}\left( \hat{\theta}_{-i}\right)
-\sum_{j\in I\backslash \left\{ i\right\} }v_{j}\left( a\left( \hat{\theta}_{I}\right) ,\hat{\theta}_{j}\right) \quad \cdots (1)
\end{equation}を定めますが、上のように、入札者\(i\)の所得移転に他の入札者たちが得る余剰を組み込むことにより、メカニズムの誘因両立性を担保しています。一方、私的価値の仮定が成り立たない場合、入札者\(i\)による入札\(\hat{\theta}_{i}\)は配分\(a\left( \hat{\theta}_{I}\right) \)に影響を与えるだけでなく、主催者が想定する他の入札者\(j\ \left( \not=i\right) \)たちの（パッケージを評価する）評価関数の形状\(v_{j}\left( \cdot ,\hat{\theta}_{I}\right) \)にも影響を与えることができます。この場合、入札者\(i\)は偽りのタイプを入札することにより他の入札者たちの評価関数\(v_{j}\)の形状を誤った形で伝えることができ、そのような駆け引きを通じて\(\left( 1\right) \)の水準に影響を与えることができるため、自身の利得を高められる余地があります。私的価値の仮定が成り立つ場合、他の入札者たちの評価関数は\(v_{j}\left( \cdot ,\hat{\theta}_{j}\right) \)となり、入札者\(i\)による入札\(\hat{\theta}_{i}\)の影響を受けないため、この場合には先のような駆け引きは不可能です。

グローヴスメカニズムの狭義事後効率性

引き続き、組合せオークション環境において準線型性、リスク中立性、私的価値の仮定が成り立つ状況を想定します。この場合、メカニズム\(\left( a,t\right) \)が配分効率的であることとは、全員の入札からなる組\(\hat{\theta}_{I}\)を任意に選んだとき、それに対して配分ルール\(a\)が定める配分\(a\left( \hat{\theta}_{I}\right) \)が\(\hat{\theta}_{I}\)のもとで配分効率的であること、すなわち、\begin{equation*}\sum_{i\in I}v_{i}\left( a\left( \hat{\theta}_{I}\right) ,\hat{\theta}_{i}\right) =\max_{a_{I}\in A}\sum_{i\in I}v_{i}\left( a_{I},\hat{\theta}_{i}\right)
\end{equation*}が成り立つことを意味します。グローヴスメカニズムの配分ルール\(a\)は、\begin{equation*}a\left( \hat{\theta}_{I}\right) \in \mathrm{argmax}_{a_{I}\in
A}\sum_{i\in I}v_{i}\left( a_{I},\hat{\theta}_{i}\right)
\end{equation*}を満たすものとして定義されているため、これは明らかに配分効率的です。

一般に、配分効率的なメカニズム\(\left( a,t\right) \)は入札の組\(\hat{\theta}_{I}\)のもとで配分効率的な配分を定めるメカニズムであり、その配分は真の状態\(\theta _{I}\)のもとで配分効率的であるとは限りません。なぜなら、入札者たちが嘘をついて真のタイプとは異なる評価関数を入札する可能性があり、その場合には入札からなる組\(\hat{\theta}_{I}\)は真の状態\(\theta _{I}\)と一致するとは限らないからです。ただ、先に示したように、グローヴスメカニズムは誘因両立的（耐戦略的）であるため、入札者たちにとって真のタイプを正直に入札することが最適であり、均衡において入札の組\(\hat{\theta}_{I}\)は真の状態\(\theta _{I}\)と一致します。その結果、グローヴスメカニズムは均衡において真の状態\(\theta _{I}\)のもとで配分効率的な結果を遂行します。

メカニズム\(\left( a,t\right) \)が狭義事後効率的であることとは、全員の入札からなる組\(\hat{\theta}_{I}\)を任意に選んだとき、それに対して\(\left( a,t\right) \)が定める結果\(\left( a\left( \hat{\theta}_{I}\right) ,t\left( \hat{\theta}_{I}\right) \right) \)が\(\hat{\theta}_{I}\)のもとで狭義パレート効率的であること意味します。準線型性と中立性を認める場合、メカニズムが配分効率的であることと狭義事後効率的であることは必要十分であるため、先の命題より以下を得ます。

繰り返しになりますが、グローヴスメカニズムは誘因両立的（耐戦略的）であるため、入札者たちにとって真のタイプを正直に入札することが最適であり、均衡において入札からなる組\(\hat{\theta}_{I}\)は真の状態\(\theta _{I}\)と一致します。したがって、グローヴスメカニズムが定める均衡結果は真のタイプ\(\theta _{I}\)のもとで狭義パレート効率的です。

グローヴスメカニズムにおける主催者の収支

グローヴスメカニズムは耐戦略性を満たすため、状態が\(\theta _{I}\)であるときに均衡において入札者\(i\)に課される所得移転は、\begin{equation*}t_{i}\left( \theta _{I}\right) =h_{i}\left( \theta _{-i}\right) -\sum_{j\in
I\backslash \left\{ i\right\} }v_{j}\left( a\left( \theta _{I}\right)
,\theta _{j}\right)
\end{equation*}となります。入札者たちが配分に対して非負の評価を与える場合には、\begin{equation*}
\sum_{j\in I\backslash \left\{ i\right\} }v_{j}\left( a\left( \theta
_{I}\right) ,\theta _{j}\right) \geq 0
\end{equation*}となるため、入札者\(i\)はグローヴスメカニズムの均衡において上記の金額を主催者から受け取ります。したがって、\(h_{i}\left( \theta_{-i}\right) \)の値によっては、\begin{equation*}t_{i}\left( \theta _{I}\right) <0
\end{equation*}となるため、グローヴスメカニズムを実施した結果としてすべての入札者が主催者から支払いを受けることになり、主催者の収支は赤字になってしまいます。逆に言えば、主催者は\(t_{i}\left( \theta _{I}\right) \)が負にならないように関数\(h_{i}\)の形状を上手くデザインすることにより、自身の収支が赤字にならないように保証できる可能性があります。