組合せオークションにおける予算均衡メカニズム

広義の予算均衡メカニズム

組合せオークション環境において何らかの均衡を遂行できるメカニズムの設計に成功した場合においても、オークションを行った結果として主催者の収支が赤字になってしまうのであれば、その制度は持続可能ではありません。制度を持続可能なものとするためには、オークションを行った結果として主催者の収支が赤字にならないことを保証する必要があります。

何らかの均衡を遂行するメカニズムが与えられたとき、オークションを行った結果として、オークションの主催者の収支が赤字にならないことが保証される場合、そのようなメカニズムは広義の予算均衡（weak budget balance）を満たすと言います。

組合せオークション環境におけるメカニズムが何らかの純粋戦略の組を均衡として遂行可能であるものとします。ただし、表明原理より、正直戦略の組が均衡になるケース、すなわち誘因両立的なメカニズムに対象を限定しても一般性は失われません。状態が\(\theta _{I}\)である場合、誘因両立的なメカニズム\(\left(a,t\right) \)のもとで入札者たちは正直戦略にもとづいて\(\theta _{I}\)を入札し、その入札に対してメカニズムは均衡結果\(\left( a\left( \theta _{I}\right) ,t\left( \theta _{I}\right) \right) \)を定めます。この結果のもとでオークションの主催者は以下の所得移転\begin{equation*}\sum_{i\in I}t_{i}\left( \theta _{I}\right)
\end{equation*}に直面します。ただ、入札者たちのタイプは私的情報であるため、メカニズムを設計する段階において、オークションの主催者は真の状態を特定できません。したがって、誘因両立的なメカニズム\(\left( a,t\right) \)が広義の予算均衡であることを保証するためには、起こり得るあらゆる状態\(\theta _{I}\)のもとでの均衡結果において主催者の収支が赤字にならないこと、すなわち、\begin{equation}\forall \theta _{I}\in \Theta _{I}:\sum_{i\in I}t_{i}\left( \theta
_{I}\right) \geq 0 \quad \cdots (1)
\end{equation}が成り立つことを保証する必要があります。誘因両立的なメカニズム\(\left( a,t\right) \)が広義の予算均衡を満たすことの定義は以上の通りです。

メカニズム\(\left( a,t\right) \)のもとでのベイジアンゲーム\(G\left( a,t\right) \)に均衡が存在することを前提としない場合にはどうなるでしょうか。この場合、メカニズム\(\left( a,t\right) \)が広義の予算均衡を満たすこととは、入札者たちが申告する評価関数からなる組\(\theta _{I}\in \Theta _{I}\)を任意に選んだときに、それに対して\(\left( a,t\right) \)が定める結果\(\left( a\left( \theta _{I}\right) ,t\left( \theta_{I}\right) \right) \)のもとで主催者の収支が赤字にならないこと、すなわち、\begin{equation*}\forall \theta _{I}\in \Theta _{I}:\sum_{i\in I}t_{i}\left( \theta
_{I}\right) \geq 0
\end{equation*}が成り立つこととして定義されます。この条件は形式的には\(\left( 1\right) \)と一致します。加えて、以上の条件は入札者たちの評価関数に依存しないため、これは実質的な意味においても\(\left( 1\right) \)と一致します。つまり、メカニズム\(\left( a,t\right) \)が誘因両立的であるとは限らない場合においても、そのメカニズムが広義の予算均衡を満たす場合には、オークションの主催者の収支が赤字にならないことが保証されるということです。

狭義の予算均衡メカニズム

組合せオークションを行った結果として主催者の収支が赤字にならないだけでなく、主催者の収支が黒字にならないことも同時に要求する場合があります。

何らかの均衡を遂行するメカニズムが与えられたとき、オークションを行った結果として、オークションの主催者の収支が均衡することが保証される場合、そのようなメカニズムは狭義の予算均衡（strictly budget balance）を満たすと言います。

組合せオークション環境におけるメカニズムが何らかの純粋戦略の組を均衡として遂行可能であるものとします。ただし、表明原理より、正直戦略の組が均衡になるケース、すなわち誘因両立的なメカニズムに対象を限定しても一般性は失われません。状態が\(\theta _{I}\)である場合、誘因両立的なメカニズム\(\left(a,t\right) \)のもとで入札者たちは正直戦略にもとづいて\(\theta _{I}\)を入札し、その入札に対してメカニズムは均衡結果\(\left( a\left( \theta _{I}\right) ,t\left( \theta _{I}\right) \right) \)を定めます。この結果のもとでオークションの主催者は以下の所得移転\begin{equation*}\sum_{i\in I}t_{i}\left( \theta _{I}\right)
\end{equation*}に直面します。ただ、入札者たちのタイプは私的情報であるため、メカニズムを設計する段階において、オークションの主催者は真の状態を特定できません。したがって、誘因両立的なメカニズム\(\left( a,t\right) \)が狭義の予算均衡であることを保証するためには、起こり得るあらゆる状態\(\theta _{I}\)のもとでの均衡結果において主催者の収支が均衡すること、すなわち、\begin{equation}\forall \theta _{I}\in \Theta _{I}:\sum_{i\in I}t_{i}\left( \theta
_{I}\right) =0 \quad \cdots (1)
\end{equation}が成り立つことを保証する必要があります。誘因両立的なメカニズム\(\left( a,t\right) \)が狭義の予算均衡を満たすことの定義は以上の通りです。

メカニズム\(\left( a,t\right) \)のもとでのベイジアンゲーム\(G\left( a,t\right) \)に均衡が存在することを前提としない場合にはどうなるでしょうか。この場合、メカニズム\(\left( a,t\right) \)が狭義の予算均衡を満たすこととは、入札者たちが申告する評価関数からなる組\(\theta _{I}\in \Theta _{I}\)を任意に選んだときに、それに対して\(\left( a,t\right) \)が定める結果\(\left( a\left( \theta _{I}\right) ,t\left( \theta_{I}\right) \right) \)のもとで主催者の収支が均衡すること、すなわち、\begin{equation*}\forall \theta _{I}\in \Theta _{I}:\sum_{i\in I}t_{i}\left( \theta
_{I}\right) =0
\end{equation*}が成り立つこととして定義されます。この条件は形式的には\(\left( 1\right) \)と一致します。加えて、以上の条件は入札者たちの評価関数に依存しないため、これは実質的な意味においても\(\left( 1\right) \)と一致します。つまり、メカニズム\(\left( a,t\right) \)が誘因両立的であるとは限らない場合においても、そのメカニズムが狭義の予算均衡を満たす場合には、オークションの主催者の収支が均衡することが保証されるということです。

オークションの主催者の収支が均衡することは収支が赤字にならないことを場合として含むため、狭義の予算均衡メカニズムは広義の予算均衡メカニズムでもあります。