組合せオークションにおけるVCGオークション

VCGオークション

組合せオークション環境において準線型性、リスク中立性、私的価値の仮定が成り立つものとします。つまり、入札者\(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*}という形で表されます。特に、この関数\(h_{i}\)がそれぞれの\(\hat{\theta}_{-i}\in\Theta _{-i}\)に対して定める値が、\begin{equation*}h_{i}\left( \hat{\theta}_{-i}\right) =\max_{a_{I}\in A}\sum_{j\in
I\backslash \left\{ i\right\} }v_{j}\left( a_{I},\hat{\theta}_{j}\right)
\end{equation*}である場合、このような関数\(h_{i}\)をクラークのピボットルール（Clarke pivot rule）と呼びます。また、関数\(h_{i}\)がピボットルールであるようなグローヴスメカニズムをヴィックリー＝クラーク＝グローブス・オークション（Vickrey-Clarke-Grove）やVCGオークション（VCG auction）、VCGメカニズム（VCG mechanism）、クラークメカニズム（Clarke mechanism）またはピボタルメカニズム（pivotal mechanism）などと呼びます。

改めて整理すると、VCGオークション\(\left( a,t\right) :\Theta_{I}\rightarrow A\times \mathbb{R} ^{n}\)が入札の組\(\hat{\theta}_{I}\in \Theta _{I}\)に対して定める結果は、\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) &=&\max_{a_{I}\in
A}\sum_{j\in I\backslash \left\{ i\right\} }v_{j}\left( a_{I},\hat{\theta}_{j}\right) -\sum_{j\in I\backslash \left\{ i\right\} }v_{j}\left( a\left(
\hat{\theta}_{I}\right) ,\hat{\theta}_{j}\right)
\end{eqnarray*}という形で表されます。これはどのような意味を持つのでしょうか。

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

VCGオークションが入札者\(i\)に課す支払い\begin{equation*}\max_{a_{I}\in A}\sum_{j\in I\backslash \left\{ i\right\} }v_{j}\left( a_{I},\hat{\theta}_{j}\right)
\end{equation*}は、入札者\(i\)を除くすべての入札者たちの間で商品を効率的に配分した場合に、入札者\(i\)を除く入札者たちが得る社会的余剰に相当します。一方、VCGオークションが選択する配分\(a\left( \hat{\theta}_{I}\right) \)は配分効率的であるため、VCGオークションが入札者\(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\)を除く入札者たちが得る社会的余剰に相当します。したがって、VCGオークションにおいて入札者\(i\)に課される所得移転\begin{equation*}\max_{a_{I}\in A}\sum_{j\in I\backslash \left\{ i\right\} }v_{j}\left( a_{I},\hat{\theta}_{j}\right) -\sum_{j\in I\backslash \left\{ i\right\}
}v_{j}\left( a\left( \hat{\theta}_{I}\right) ,\hat{\theta}_{j}\right)
\end{equation*}は、オークションの参加者の間で商品を効率的に配分することを前提とした場合、入札者\(i\)がオークションに参加することにより他の入札者たちが被る被害額に相当します。つまり、VCGオークションのもとでは、入札者\(i\)は自身がオークションに参加することにより発生する「外部性」に相当する金額を支払うことを要求されます。

VCGオークションの耐戦略性

組合せオークション環境におけるメカニズム\(\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*}が成り立つことを意味します。

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

準線型性、リスク中立性、私的価値の仮定が成り立つ環境においてVCGオークション\(\left( a,t\right) \)が運用されているものとします。VCGオークション\(\left( a,t\right) \)は耐戦略性を満たすため、真の状態が\(\theta _{I}=\left( \theta_{i},\theta _{-i}\right) \)であるとき、均衡における入札額の組は\(\theta _{I}\)となるため、均衡において入札者\(i\)が獲得する利得は、\begin{eqnarray*}&&v_{i}\left( a\left( \theta _{I}\right) ,\theta _{i}\right) -t_{i}\left(
\theta _{I}\right) \\
&=&v_{i}\left( a\left( \theta _{I}\right) ,\theta _{i}\right) -\left[
\max_{a_{I}\in A}\sum_{j\in I\backslash \left\{ i\right\} }v_{j}\left(
a_{I},\theta _{j}\right) -\sum_{j\in I\backslash \left\{ i\right\}
}v_{j}\left( a\left( \theta _{I}\right) ,\theta _{j}\right) \right] \quad
\because t\text{の定義} \\
&=&\sum_{j\in I}v_{j}\left( a\left( \theta _{I}\right) ,\theta _{j}\right)
-\max_{a_{I}\in A}\sum_{j\in I\backslash \left\{ i\right\} }v_{j}\left(
a_{I},\theta _{j}\right) \\
&=&\max_{a_{I}\in A}\sum_{j\in I}v_{j}\left( a_{I},\theta _{j}\right)
-\max_{a_{I}\in A}\sum_{j\in I\backslash \left\{ i\right\} }v_{j}\left(
a_{I},\theta _{j}\right) \quad \because a\text{の定義}
\end{eqnarray*}となります。最後の辺の第1項\begin{equation*}
\max_{a_{I}\in A}\sum_{j\in I}v_{j}\left( a_{I},\theta _{j}\right)
\end{equation*}は、すべての入札者がオークションに参加し、すべての入札者の間で商品を効率したときに、すべての入札者が得る社会的余剰に相当します。一方、第2項\begin{equation*}
\max_{a_{I}\in A}\sum_{j\in I\backslash \left\{ i\right\} }a_{j}\cdot \theta
_{j}
\end{equation*}は、入札者\(i\)以外の入札者たちがオークションに参加し、入札者\(i\)以外の入札者の間で商品を効率的に配分したときに、入札者\(i\)以外の入札者たちが得る社会的余剰に相当します。したがって、それらの差と一致する入札者\(i\)の利得は、オークションの参加者の間で商品が効率的に配分されることを前提とした場合に、入札者\(i\)がオークションに参加したことにより生み出される社会的余剰の増分に相当します。そこで、この余剰の増加分を入札者\(i\)の限界貢献度（marginal contribution）と呼びます。VCGオークションにおいて、それぞれの入札者は自身の限界貢献度に等しい利得を獲得するということです。

VCGオークションの事後効率性

引き続き、組合せオークション環境において準線型性、リスク中立性、私的価値の仮定が成り立つ状況を想定します。この場合、メカニズム\(\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*}が成り立つことを意味します。VCGオークションの配分ルール\(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}\)と一致するとは限らないからです。ただ、先に示したように、VCGオークションは誘因両立的（耐戦略的）であるため、入札者たちにとって真の評価関数を正直に入札することが最適であり、均衡において入札の組\(\hat{\theta}_{I}\)は真の状態\(\theta _{I}\)と一致します。その結果、VCGオークションは均衡において真の状態\(\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}\)のもとで狭義パレート効率的であること意味します。準線型性とリスク中立性を認める場合、メカニズムが配分効率的であることと狭義事後効率的であることは必要十分であるため、先の命題より以下を得ます。

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

VCGオークションの事後個人合理性

組合せオークション環境におけるメカニズム\(\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}\)のもとで事後個人合理的であること、すなわち、\begin{equation*}\forall \hat{\theta}_{I}\in \Theta _{I},\ \forall i\in I:u_{i}\left( a\left(
\hat{\theta}_{I}\right) ,t\left( \hat{\theta}_{I}\right) ,\hat{\theta}_{I}\right) \geq 0
\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) \)が事後個人合理的であることとは、\begin{equation*}\forall \hat{\theta}_{I}\in \Theta _{I},\ \forall i\in I:v_{i}\left( a\left(
\hat{\theta}_{I}\right) ,\hat{\theta}_{i}\right) -t_{i}\left( \hat{\theta}_{I}\right) \geq 0
\end{equation*}が成り立つことを意味します。VCGオークションは一定の条件のもとで事後個人合理性を満たします。以下で解説します。

組合せオークションの環境において、入札者集合\(I\)に属するすべての入札者がオークションに参加する場合に起こり得るすべての配分からなる集合を\(A\)で表記し、入札者\(i\)以外のすべての入札者がオークションに参加する場合に起こり得るすべての配分からなる集合を\(A_{-i}\)で表記する場合、任意の入札者\(i\in I\)について、\begin{equation*}A_{-i}\subset A
\end{equation*}が成り立つのであれば、配分集合に関する単調性（allocation set monotonicity）が成り立つと言います。この仮定は、ある入札者がオークションへの参加をやめても、その人の参加時には実現不可能であった配分が実現可能になるような事態は起こり得ないことを要求します。逆に言うと、ある入札者がオークションへ参加した場合、その人が参加する前に実現可能であった配分は相変わらず実現可能であるということです。組合せオークションにおいては、たとえ入札者が増加しても、それ以前から参加している入札者たちに対して以前と同様の配分を割り当てることは物理的に可能であるため、単調性の仮定が常に満たされます。

組合せオークション環境において準線型性、リスク中立性、私的価値の仮定が成り立つものとします。つまり、入札者\(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*}であるということです。入札者\(i\)以外のすべての入札者がオークションに参加する場合に起こり得るすべての配分からなる集合を\(A_{-i}\)で表記する場合、任意の入札者\(i\in I\)とその任意のタイプ\(\theta _{i}\in \Theta _{i}\)および任意の配分\(a_{I}\in A_{-i}\)に対して、\begin{equation*}v_{i}\left( a_{I},\theta _{i}\right) \geq 0
\end{equation*}が成り立つ場合には非負の外部性（no negative externalities）が成り立つと言います。この仮定は、入札者\(i\)がオークションに参加しない場合に実現し得る結果から入札者\(i\)が得る利得が負にならないことを要求します。言い換えると、オークションに参加しない入札者にとって、参加者の中の誰がどのパッケージを落札しても構わないということです。これは、オークションの参加者が非参加者に対して負の外部性をもたらさないことを意味します。

VCGオークションが事後個人合理性を満たすためには以上の2つの条件が必要ですが、単一財オークションの環境では単調性は常に満たされるため、結局、必要な条件は非負の外部性のみです。

先ほど例を通じて確認したように、商品を含まないパッケージへの評価額が非負である場合、非外部性が成り立つ場合には非負の外部性が成り立ちます。以上の事実と上の命題より以下を得ます。

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

VCGオークションの広義予算均衡性

組合せオークション環境におけるメカニズム\(\left( a,t\right) \)が広義の予算均衡を満たすこととは、入札の組\(\hat{\theta}_{I}\)を任意に選んだとき、それに対して移転ルール\(t\)が定める所得移転\(t\left( \hat{\theta}_{I}\right) \)のもとでオークションの主催者の収支が赤字にならないこと、すなわち、\begin{equation*}\forall \hat{\theta}_{I}\in \Theta _{I}:\sum_{i\in I}t_{i}\left( \hat{\theta}_{I}\right) \geq 0
\end{equation*}が成り立つことを意味します。VCGオークションは一定の条件のもとで広義の予算均衡を満たします。以下で解説します。

組合せオークション環境において準線型性、リスク中立性、私的価値の仮定が成り立つものとします。つまり、入札者\(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*}であるということです。状態\(\theta _{I}\in \Theta _{I}\)において、すべての入札者がオークションに参加する場合の効率的な配分を、\begin{equation*}a_{I}^{\ast }=\mathrm{argmax}_{a_{I}\in A}\sum_{i\in I}v_{i}\left(
a_{I},\theta _{j}\right)
\end{equation*}で表記します。また、入札者\(i\)以外のすべての入札者がオークションに参加する場合に起こり得るすべての配分からなる集合を\(A_{-i}\)で表記します。その上で、状態\(\theta_{I}\in \Theta _{I}\)と入札者\(i\in I\)をそれぞれ任意に選んだときに、\begin{equation*}\sum\limits_{j\in I\backslash \left\{ i\right\} }v_{j}\left( a^{\ast
}(\theta _{I}),\theta _{j}\right) \leq \sum\limits_{j\in I\backslash \left\{
i\right\} }v_{j}\left( a_{I},\theta _{j}\right)
\end{equation*}を満たす配分\(a_{I}\in A_{-i}\)が存在することが保証されるのであれば、非単一エージェント効果（no single-agent effect）を満たすと言います。左辺は入札者\(i\)を含めた全員がオークションに参加する場合の効率的配分において、入札者\(i\)以外の入札者たちが得る余剰に相当します。右辺は、入札者\(i\)がオークションに参加しない場合に入札者\(i\)以外の入札者たちが得る余剰です。したがって上の条件は、効率的な配分を出発点として入札者\(i\)がオークションから抜けても、残った入札者たちが得る余剰が減少しないような配分が存在することを保証しています。組合せオークションでは、ある入札者がオークションから離脱すると、入札者間の競争の度合いが緩和されるため、残された入札者たちが直面する配分が悪化することはなく、したがって非単一エージェント効果の仮定は成り立つものと考えられます。

非単一エージェント効果の仮定が成り立つ場合、VCGオークションは広義の予算均衡を満たします。つまり、オークションの主催者の収支が赤字になることはありません。