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

メカニズムのもとでのベイジアンゲーム

仮に、オークションの主催者が組合せオークション市場の真の状態、すなわち入札者たちがパッケージどうしを比較する評価関数の真の形状を観察できるのであれば、観察した真の状態を基準に社会的に望ましい結果を特定し、それを遂行すればよいことになります。しかし、実際には、評価関数は入札者が持つ私的情報であるため、主催者は真の状態を観察できず、したがって社会的に望ましい結果を事前に特定できません。そこで、主催者は入札者たちに評価関数を申告させた上で、申告された評価関数を基準に社会的に望ましい結果を特定し、それを遂行しようとします。このような資源配分ルールをメカニズムと呼ばれる概念として定式化しました。ただ、メカニズムに直面したそれぞれの入札者は自身の真の評価関数を正直に申告するとは限りません。入札者は望ましい結果を得るために戦略的に行動しますが、その一環として、偽りの評価関数を申告する可能性があるからです。入札者にとって評価関数は私的情報であるため、入札者が嘘をついて真の評価関数とは異なる評価関数を申告しても、主催者はそれが嘘であるかどうかを知る術はありません。入札者たちが偽りの評価関数を申告する場合、主催者は偽りの評価関数を基準に結果を決定することとなり、それは真の意味で社会的に望ましい結果とは異なるものになってしまう可能性があります。情報の非対称に起因するこのような問題をインセンティブの問題と呼びます。

インセンティブの問題を引き起こす原因が情報の非対称性である以上、インセンティブの問題を解決するためには、何らかの方法を通じて情報の非対称性を解消する必要があります。具体的には、それぞれの入札者にとって真の評価関数を正直に申告することが得であるようなメカニズムを設計すれば、そのようなメカニズムのもと、入札者たちは真の評価関数を自ら進んで正直に申告するため、結果として情報の非対称性は解消されます。以上のことをよりテクニカルに表現すると、メカニズムを提示された入札者たちが直面する戦略的状況をゲームとして記述したとき、そのゲームにおいて、「すべての入札者が自身の真の評価関数を正直に申告する」ことが均衡になるのであれば、そのようなメカニズムのもとで情報の非対称性は解消されるということです。ただ、そもそも、そのようなメカニズムを設計することは可能なのでしょうか。こうした問いについて考えるために、まずは、メカニズムを提示された入札者たちが直面する戦略的状況をゲームとして記述します。

組合せオークション市場において、主催者はメカニズム\(\left( a,t\right):\Theta _{I}\rightarrow A\times \mathbb{R} ^{n}\)を設計し、それを入札者たちに提示します。仮にすべての入札者が提示されたメカニズム\(\left( a,t\right) \)に同意するのであれば、それぞれの入札者\(i\in I\)は自身の評価関数\(\theta _{i}\in\Theta _{i}\)を申告することになります。その際、他の入札者たちが申告する評価関数を観察できません。また、入札者は真の評価関数を正直に申告するとは限りません。いずれにせよ、入札者たちが申告してきた評価関数からなる組\(\theta _{I}\in \Theta _{I}\)に対し、主催者はあらかじめ提示したメカニズム\(\left(a,t\right) \)にもとづいて結果\(\left( a\left( \theta _{I}\right) ,t\left( \theta _{I}\right) \right) \in A\times \mathbb{R} ^{n}\)を選び取り、これを遂行します。その結果、それぞれの入札者\(i\)はパッケージ\(a_{i}\left(\theta _{I}\right) \)で入手するとともに所得移転\(t_{i}\left( \theta_{I}\right) \)を課せられます。メカニズム\(\left( a,t\right) \)を提示された入札者たちが直面する以上の戦略的状況をゲームとみなした上で、それを\(G\left( a,t\right) \)と表記し、これをメカニズム\(\left( a,t\right) \)のもとでのゲームと呼ぶこととします。以降では、このゲーム\(G\left( a,t\right) \)を構成する要素を具体的に特定します。

まず、このゲームのプレイヤーはオークションに参加する入札者たちであるため、ゲーム\(G\left( a,t\right) \)のプレイヤー集合は問題としている組合せオークション市場の入札者集合\(I\)と一致します。

それぞれの入札者\(i\in I\)はパッケージどうしを比較する評価関数\(\theta _{i}\in \Theta _{i}\)を私的情報として持っています。つまり、ゲーム\(G\left( a,t\right) \)におけるプレイヤー\(i\)のタイプは評価関数\(\theta _{i}:2^{X}\rightarrow \mathbb{R} \)であり、タイプ集合は評価関数がとり得る形状からなる集合\(\Theta _{i}\)と一致します。入札者\(i\)のタイプ\(\theta _{i}\)はタイプ集合\(\Theta _{i}\)に属する様々な値を取り得ますが、\(\theta _{i}\)の真の値を知っているのは入札者\(i\)だけです。他の任意の入札者や主催者は\(\theta _{i}\)がとり得る値の範囲\(\Theta _{i}\)を知っていますが、その中のどの値が真の値であるかは知らないものと仮定することにより、入札者\(i\)にとって評価関数が私的情報である状況を表現します。

メカニズム\(\left( a,t\right) \)に直面したそれぞれの入札者\(i\)は自身の評価関数\(\theta _{i}\)を申告する必要があります。したがって、ゲーム\(G\left( a,t\right) \)において入札者\(i\)に与えられた行動は自身が申告する評価関数\(\theta _{i}\)であり、選択し得るすべての行動からなる集合はタイプ集合\(\Theta _{i}\)と一致します。それぞれのプレイヤーは真の評価関数を正直に申告するとは限りません。

入札者たちが選択する行動の組、すなわち申告された評価関数からなる組が\(\theta _{I}\in\Theta _{I}\)であるとき、それに対してメカニズム\(\left( a,t\right) \)は結果\(\left( a\left( \theta_{I}\right) ,t\left( \theta _{I}\right) \right) \in A\times \mathbb{R} ^{n}\)を選び取ります。申告内容\(\theta _{I}\)が変われば結果\(\left( a\left( \theta _{I}\right) ,t\left( \theta_{I}\right) \right) \)も変化しますが、どのように変化するかはメカニズム\(\left(a,t\right) \)の内容に依存します。以上がゲーム\(G\left(a,t\right) \)において起こり得る結果です。

入札者\(i\)が結果どうしを比較する評価体系は結果集合\(A\times \mathbb{R} ^{n}\)上に定義された利得関数\(u_{i}:A\times \mathbb{R} ^{n}\rightarrow \mathbb{R} \)として記述されます。一般に、入札者が結果どうしを比較する利得関数\(u_{i}\)の形状はすべての入札者のタイプからなる組\(\theta _{I}\)に依存するため、そのことを明示するために、入札者\(i\)の利得関数を、\begin{equation*}u_{i}\left( \cdot ,\theta _{I}\right) :A\times \mathbb{R} ^{N}\rightarrow \mathbb{R} \end{equation*}と表記します。その上で、それぞれの状態における入札者\(i\)の利得関数からなる集合を、\begin{equation*}u_{i}=\left\{ u_{i}\left( \cdot ,\theta _{I}\right) \right\} _{\theta
_{I}\in \Theta _{i}}
\end{equation*}で表記します。

以上でゲーム\(G\left( a,t\right) \)の要素がすべて出揃いました。つまり、このゲームはプレイヤーである入札者が私的情報を持つ不完備情報ゲームであり、以下のようなベイジアンゲーム\begin{equation*}G\left( a,t\right) =\left( I,\left\{ \Theta _{i}\right\} _{i\in I},\left\{
u_{i}\right\} _{i\in I}\right)
\end{equation*}として定式化されます。ただし、\(\Theta _{i}\)は入札者\(i\)のタイプ集合と行動集合を兼ねています。これをメカニズム\(\left( a,t\right) \)のもとでのゲームと呼ぶこととします。

ゲーム\(G\left( a,t\right) \)を構成するすべての要素は入札者たちの共有知識です。それぞれの入札者\(i\in I\)は自身のタイプの真の値（便宜的にこれを\(\theta _{i}^{\ast }\)で表記します）を知っていますが、他の任意の入札者\(j\ \left( \not=i\right) \)のタイプ\(\theta _{j}\)の真の値\(\theta _{j}^{\ast }\)を知りません。入札者\(i\)が他の入札者\(j\)について知っていることは\(\theta _{j}\)がとり得る値の範囲\(\Theta _{j}\)だけです。したがって、入札者\(i\)が直面し得る状態からなる集合は、\begin{equation*}\left\{ \left( \theta _{i}^{\ast },\theta _{-i}\right) \right\} _{\theta
_{-i}\in \Theta _{-i}}
\end{equation*}となります。他の任意の入札者についても同様の議論が成立します。また、ベイジアンゲームの静学性と不完備性より、ゲーム\(G\left( a,t\right) \)において入札者たちは以下の手順で意思決定を行います。

1. 自身の真の評価関数\(\theta _{i}^{\ast }\in \Theta _{i}\)を知っているが他のプレイヤーたちの真の評価関数\(\theta _{-i}^{\ast }\in \Theta _{-i}\)を知らないそれぞれの入札者\(i\in I\)は自身のタイプ集合\(\Theta _{i}\)の中から特定の評価関数\(\theta _{i}\)を選択し、それを申告する。その際、他の入札者が申告する評価関数を観察できない。また、入札者\(i\)が申告する評価関数\(\theta _{i}\)は自身の真の評価関数\(\theta_{i}^{\ast }\)であるとは限らない。
2. 入札者たちが申告してきた評価関数からなる組\(\theta _{I}\in \Theta _{I}\)に対して、メカニズム\(\left(a,t\right) :\Theta _{I}\rightarrow A\times \mathbb{R} ^{n}\)が結果\(\left( a\left( \theta _{I}\right) ,t\left(\theta _{I}\right) \right) \in A\times \mathbb{R} ^{n}\)を定める。
3. それぞれの入札者\(i\)は真の状態\(\theta _{I}^{\ast }\)にもとづく利得関数\(u_{i}\left( \cdot,\theta _{I}^{\ast }\right) \)のもとでメカニズムが定める結果\(\left( a\left( \theta _{I}\right) ,t\left( \theta _{I}\right) \right) \)を評価する。つまり、入札者\(i\)が得る利得は\(u_{i}\left( a\left( \theta _{I}\right) ,t\left( \theta _{I}\right),\theta _{I}^{\ast }\right) \)である。特に、準線型環境の場合には、\begin{equation*}u_{i}\left( a\left( \theta _{I}\right) ,t\left( \theta _{I}\right) ,\theta_{I}^{\ast }\right) =\theta _{i}^{\ast }\left( a_{i}\left( \theta
   _{I}\right) \right) -t_{i}\left( \theta _{I}\right)
   \end{equation*}となる。

入札者の純粋戦略

メカニズムのもとでのゲーム\(G\left( a,t\right) \)において、仮にすべての入札者が真の状態\(\theta _{I}^{\ast }\)を把握しており、なおかつそのことが共有知識であるならば、それぞれの入札者\(i\in I\)の利得関数が\(u_{i}\left( \cdot,\theta _{I}^{\ast }\right) \)であることが確定するため、入札者たちが直面する戦略的状況はもはや不完備情報ゲームではなく、以下のような完備情報ゲーム\begin{equation*}G\left( a,t,\theta _{I}^{\ast }\right) =\left\{ I,\left\{ \Theta
_{i}\right\} _{i\in I},\left\{ u_{i}\left( \cdot ,\theta _{I}^{\ast }\right)
\right\} _{i\in I}\right\}
\end{equation*}となります。ただし、\(I\)は入札者集合、\(\Theta_{i}\)は入札者\(i\)の行動集合、\(u_{i}\left( \cdot ,\theta _{I}^{\ast }\right) \)は入札者\(i\)の利得関数です。これを\(\theta _{I}^{\ast }\)のもとでの状態ゲームと呼ぶこととします。状態ゲーム\(G\left( a,t,\theta _{I}^{\ast}\right) \)は完備情報ゲームであるため、そこでの入札者の戦略とは、単純に、入札者が選択可能な行動の中から1つの行動を選ぶことを意味します。

ただ、実際にはゲーム\(G\left( a,t\right) \)において真の状態\(\theta _{I}^{\ast }\)を把握している入札者は存在せず、それぞれの入札者\(i\)は真の状態\(\theta _{I}^{\ast }\)に関する断片的な知識、すなわち自身の真のタイプ\(\theta _{i}^{\ast }\)に関する情報しか持っていないため、入札者は複数の状態ゲームに直面し得る中で意思決定を行う必要があります。具体的には、入札者\(i\)が直面し得る状態ゲームからなる集合は、\begin{equation}\left\{ G\left( a,t,\theta _{i}^{\ast },\theta _{-i}\right) \right\}
_{\theta _{-i}\in \Theta _{-i}} \quad \cdots (1)
\end{equation}です。しかも、それぞれの入札者\(i\)は自身が直面し得るそれぞれの状態ゲーム\(G\left( a,t,\theta_{i}^{\ast },\theta _{-i}\right) \)に対して、そこで選択する行動を個別に指定することはできません。なぜなら、入札者\(i\)は他の入札者たちのタイプ\(\theta _{-i}\)を観察できず、ゆえに自分が\(\left( 1\right) \)に属するどの状態ゲームをプレーしているかを判別できないからです。したがって、入札者\(i\)は特定の行動\(\theta _{i}\)を事前に選び、その1つの行動のもとで、自分が直面し得る\(\left( 1\right) \)に属するすべての状態ゲームに備えなければなりません。

入札者\(i\)は自身のタイプ\(\theta _{i}\)の真の値\(\theta _{i}^{\ast }\)を知っているため、\(\theta _{i}^{\ast }\)のもとで直面し得る状態ゲームの集合\(\left( 1\right) \)に対してのみ1つの行動を定めればよいと考えるかもしれませんが、この考えは誤りです。他の入札者\(j\ \left( \not=i\right) \)の視点から考えてみると、入札者\(j\)にとっての最適な行動は入札者\(i\)の行動に依存するため、入札者\(j\)は入札者\(i\)の行動を予想しながら自身の行動を決定します。入札者\(i\)の行動は自身のタイプに依存しますが、入札者\(j\)は入札者\(i\)の真のタイプを知らない以上、\(\Theta _{i}\)に属するそれぞれのタイプごとに、そこでの入札者\(i\)の行動を予想した上で、その予想を踏まえた上で自身の行動を決定します。つまり、入札者\(j\)の行動は入札者\(i\)のそれぞれのタイプのもとでの行動に依存します。逆に、入札者\(i\)の最適な行動は入札者\(j\)の行動に依存しますが、入札者\(j\)の行動が入札者\(i\)のそれぞれのタイプのもとでの行動に依存する以上、入札者\(i\)が自身の最適な行動を考えるためには、入札者\(i\)は自身の真のタイプとは限らない自身のそれぞれのタイプにおいて自分が何をするであろうか考える必要があります。つまり、真のタイプ\(\theta _{i}^{\ast }\)とは異なるそれぞれのタイプ\(\theta _{i}\)についても、入札者\(i\)はその場合に自身が選択するであろう行動をあらかじめ定める必要があります。

以上を踏まえると、メカニズム\(\left( a,t\right) \)のもとでのベイジアンゲーム\(G\left( a,t\right) \)においてそれぞれの入札者は、自身のそれぞれのタイプごとに自身が選択するであろう行動を包括的に定めておく必要があります。具体的には、ゲーム\(G\left( a,t\right) \)における入札者\(i\)の戦略は写像\begin{equation*}s_{i}:\Theta _{i}\rightarrow \Theta _{i}
\end{equation*}として定式化されます。この戦略\(s_{i}\)のもとで、入札者\(i\)は自分のタイプが\(\theta _{i}\in \Theta _{i}\)の場合には行動\(s_{i}\left( \theta_{i}\right) \in \Theta _{i}\)を選択します。言い換えると、自身のタイプが\(\theta _{i}\)である場合、戦略\(s_{i}\)のもとでは、入札者\(i\)は主催者に対して自身の評価関数が\(s_{i}\left( \theta _{i}\right) \)であると申告するということです。このような行動計画\(s_{i}\)を入札者の純粋戦略（pure strategy）と呼びます。

すべての入札者の純粋戦略からなる組を\(s_{I}=(s_{i})_{i\in I}\)で表し、入札者\(i\)以外の入札者たちの純粋戦略からなる組を\(s_{-i}=(s_{j})_{j\in I\backslash \left\{ i\right\} }\)で表します。\(s_{I}=\left(s_{i},s_{-i}\right) \)です。

入札者\(i\)が選択可能なすべての純粋戦略からなる集合を入札者\(i\)の戦略集合（strategy set）や戦略空間（strategy space）などと呼び、これを\(S_{i}\)で表します。\(s_{i}\in S_{i}\)です。すべての入札者の戦略集合の直積を\(S_{I}=\prod_{i\in I}S_{i}\)で表します。また、\(S_{-i}=\prod_{j\in I\backslash\left\{ i\right\} }S_{j}\)とします。\(s_{I}\in S_{I}\)かつ\(s_{-i}\in S_{-i}\)です。

メカニズムのもとでのゲーム\(G\left( a,t\right) \)においてエージェントたちが選択する純粋戦略からなる組が\(s_{I}\)であるとき、以下の形でゲームが進行します。

1. 自身の真の評価関数\(\theta _{i}^{\ast }\in \Theta _{i}\)を知っているが他のプレイヤーたちの真の評価関数\(\theta _{-i}^{\ast }\in \Theta _{-i}\)を知らないそれぞれの入札者\(i\in I\)は自身の純粋戦略\(s_{i}\)にもとづき特定の評価関数\(s_{i}\left( \theta _{i}^{\ast}\right) \)を選択し、それを申告する。その際、他の入札者たちが申告する評価関数を観察できない。入札者\(i\)が申告する評価関数\(s_{i}\left( \theta _{i}^{\ast }\right) \)は自身の真の評価関数\(\theta _{i}^{\ast }\)であるとは限らない。
2. 入札者たちが申告してきた評価関数からなる組\(s_{I}\left( \theta _{I}^{\ast }\right)=\left( s_{i}\left( \theta _{i}^{\ast }\right) \right) _{i\in I}\in \Theta_{I}\)に対して、メカニズム\(\left( a,t\right) :\Theta _{I}\rightarrow A\times \mathbb{R} ^{n}\)が結果\(\left( a\left( s_{I}\left( \theta _{I}^{\ast}\right) \right) ,t\left( s_{I}\left( \theta _{I}^{\ast }\right) \right)
   \right) \in A\times \mathbb{R} ^{n}\)を定める。
3. それぞれの入札者\(i\)は真の状態\(\theta _{I}^{\ast }\)にもとづく利得関数\(u_{i}\left( \cdot,\theta _{I}^{\ast }\right) \)のもとでメカニズムが定める結果\(\left( a\left( s_{I}\left( \theta _{I}^{\ast }\right) \right) ,t\left(s_{I}\left( \theta _{I}^{\ast }\right) \right) \right) \)を評価する。つまり、入札者\(i\)が得る利得は\(u_{i}\left( a\left( s_{I}\left( \theta _{I}^{\ast }\right) \right) ,t\left(s_{I}\left( \theta _{I}^{\ast }\right) \right) ,\theta _{I}^{\ast }\right) \)である。特に、準線型環境の場合には、\begin{equation*}u_{i}\left( a\left( s_{I}\left( \theta _{I}^{\ast }\right) \right) ,t\left(s_{I}\left( \theta _{I}^{\ast }\right) \right) ,\theta _{I}^{\ast }\right)
   =\theta _{i}^{\ast }\left( a_{i}\left( s_{I}\left( \theta _{I}^{\ast
   }\right) \right) \right) -t_{i}\left( s_{I}\left( \theta _{I}^{\ast }\right)
   \right)
   \end{equation*}となる。