組合せオークションにおけるメカニズムのもとでの提携型ゲーム

組合せオークションと協力ゲーム

組合せオークションにおいてメカニズムを提示された入札者たちが直面する戦略的状況を不完備情報ゲームとみなした上で、それをベイジアンゲームとして表現しました。不完備情報ゲームは非協力ゲームであるため、そこでは入札者たちの間に拘束的な合意が成立せず、それぞれの入札者の意思決定は、他の入札者たちの意思決定から独立した形で行われる状況を想定しています。言い換えると、入札者たちがオークションに参加する前に交渉を行う場合、そこで到達した合意通りに行動することを強制する仕組みが存在しない状況を想定するということです。

一方、そのような立場とは別に、入札者の間に拘束的な合意が成立する状況を想定した上で、入札者たちがグループを形成して協力的な意思決定を行う状況を明示的に分析することもできます。言い換えると、入札者たちが直面する戦略的状況を協力ゲーム（cooperative game）とみなすということです。協力ゲームを用いれば、プレイヤー間の戦略的相互依存関係だけでなく、グループ間の戦略的相互依存関係を明示的に分析することができます。そこで以下では、メカニズムを提示された入札者たちが直面する戦略的状況を協力ゲームとみなした上で、それを提携型ゲーム（coalitional form game）として記述します。

基本的な仮定

組合せオークション環境において非外部性、準線型性、リスク中立性、私的価値の仮定が成り立つものとします。つまり、入札者\(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) =\theta _{i}\left( a_{i}\right)
-t_{i}
\end{equation*}であるということです。ただし、\(\theta_{i}:2^{X}\rightarrow \mathbb{R} \)はパッケージへの支払い意思額を特定する評価関数であり、以下の2つの条件\begin{eqnarray*}&&\left( a\right) \ \theta _{i}\left( \phi \right) =0 \\
&&\left( b\right) \ \forall P,P^{\prime }\in 2^{X}:\left[ P\subset P^{\prime
}\Rightarrow \theta _{i}\left( P\right) \leq \theta _{i}\left( P^{\prime
}\right) \right] \end{eqnarray*}を満たすものと仮定します。条件\(\left( a\right) \)は、商品を含まないパッケージへの評価額が\(0\)であることを意味しますが、これを標準化（normalization）の仮定と呼びます。条件\(\left( b\right) \)は、パッケージ\(P\)とそれを部分集合として含むパッケージ\(P^{\prime }\)をそれぞれ任意に選んだとき、\(P^{\prime }\)への評価額が\(P\)への評価額を下回らないことを意味しますが、これを単調性（monotonicity）の仮定と呼びます。これは、パッケージ\(P\)に何らかの商品を加えて得られるパッケージ\(P^{\prime }\)への評価額が、もとのパッケージ\(P\)への評価額以上であるということです。言い換えると、\(P^{\prime }\backslash P\)に属する商品、すなわち\(P\)から\(P^{\prime }\)へ移行するために新たに加えた商品が入札者\(i\)にとって不要である場合でも、それらの商品を所有ないし処分することに伴う負の効用は発生しないため、それらの商品を\(P\)に加えても評価額は低下しないということです。そのような事情を踏まえた上で、条件\(\left( b\right) \)を無償廃棄の可能性（free disposal）と呼ぶこともあります。標準化と単調性の仮定を認める場合、パッケージ\(P\in 2^{X}\)を任意に選んだとき、\begin{eqnarray*}\theta _{i}\left( P\right) &\geq &\theta _{i}\left( \phi \right) \quad
\because \phi \subset P\text{および単調性の仮定} \\
&=&0\quad \because \text{標準化の仮定}
\end{eqnarray*}すなわち、\begin{equation*}
\theta _{i}\left( P\right) \geq 0
\end{equation*}を得ます。つまり、以上の仮定のもとでは、任意のパッケージへの評価額が非負の実数になることが保証されます。

これまでは商品の売り手をプレイヤーとみなしませんでしたが、組合せオークションにおける戦略的状況を協力ゲームとして分析する際には売り手をプレイヤーとみなした上で明示的な分析対象とします。入札者集合が\(I=\left\{1,\cdots ,n\right\} \)であるのに対し、商品の売り手をプレイヤー\(0\)と呼ぶこととします。その上で、すべてのプレイヤーからなる集合を、\begin{equation*}I_{0}=I\cup \left\{ 0\right\} =\left\{ 0,1,\cdots ,n\right\}
\end{equation*}で表記します。結果\(\left( a_{I},t_{I}\right) \in A\times \mathbb{R} ^{n}\)において入札者に落札されずに売れ残る商品からなるパッケージは、\begin{equation*}X\backslash \bigcup\limits_{i\in I}a_{i}
\end{equation*}であり、売り手が直面する所得移転はオークションからの収入\begin{equation*}
\sum_{i\in I}t_{i}
\end{equation*}ですが、売り手の評価関数\(\theta _{0}:2^{X}\rightarrow \mathbb{R} \)に関して、\begin{equation}\theta _{0}\left( X\backslash \bigcup\limits_{i\in I}a_{i}\right) =0
\quad \cdots (1)
\end{equation}が成り立つものと仮定します。つまり、落札されずに残った商品から売り手は利得を得たり損をすることはないということです。加えて、\(\theta _{0}\)はプレイヤーたちの共有知識であるものと仮定します。以上を踏まえると、状態\(\theta _{I}\)において結果\(\left(a_{I},t_{I}\right) \)から売り手\(0\)が得る利得は、\begin{eqnarray*}u_{0}\left( a_{I},t_{I},\theta _{I}\right) &=&\theta _{0}\left( X\backslash
\bigcup\limits_{i\in I}a_{i}\right) +\sum_{i\in I}t_{i}\quad \because \text{非外部性、準線型性、リスク中立性、私的価値} \\
&=&0+\sum_{i\in I}t_{i}\quad \because \left( 1\right) \\
&=&\sum_{i\in I}t_{i}
\end{eqnarray*}となります。つまり、売り手が結果から得る利得はオークションからの収入と一致するということです。

状態のもとでの提携型ゲーム

状態が\(\theta _{I}\in \Theta _{I}\)である場合に入札者たちが直面する戦略的状況を協力ゲームとみなした上で、それを\(\mathcal{G}\left( \theta _{I}\right) \)で表記し、これを状態\(\theta _{I}\)のもとでの提携型ゲームと呼ぶこととします。以降では、このゲーム\(\mathcal{G}\left( \theta _{I}\right) \)を構成する要素を具体的に特定します。

まず、問題としている組合せオークション市場のすべての入札者と売り手を提携型ゲーム\(\mathcal{G}\left( \theta _{I}\right) \)のプレイヤーとみなします。つまり、ゲーム\(\mathcal{G}\left( \theta _{I}\right) \)のプレイヤー集合は、\begin{equation*}I_{0}=I\cup \left\{ 0\right\} =\left\{ 0,1,\cdots ,n\right\}
\end{equation*}であるということです。プレイヤー集合の部分集合\(C\subset I_{0}\)を提携（coalition）と呼びます。真の状態\(\theta _{I}\)を事前に観察できるプレイヤーが存在しないことを考慮すると、状態\(\theta _{I}\)に関わらず、ゲーム\(\mathcal{G}\left( \theta _{I}\right) \)のプレイヤー集合は常に\(I_{0}\)で一定とみなすのが自然です。

提携型ゲーム\(\mathcal{G}\left( \theta_{I}\right) \)を構成する2つ目の要素は提携値関数（coalition value mathrmtion）や特性関数（characteristic mathrmtion）などと呼ばれる概念であり、これを、\begin{equation*}w_{\theta _{I}}:2^{I_{0}}\rightarrow \mathbb{R} \end{equation*}で表記します。提携値関数\(w_{\theta _{I}}\)はそれぞれの提携\(C\in 2^{I_{0}}\)に対して実数\(w_{\theta _{I}}\left( C\right) \in \mathbb{R} \)を1つずつ定めますが、この値を提携\(C\)の提携値（coalition value）と呼びます。提携値\(w_{\theta_{I}}\left( C\right) \)を特定するためには、まず、プレイヤー集合\(I_{0}\)を提携\(C\)とその補集合\(I_{0}\backslash C\)に分割します。その上で、\(I_{0}\backslash C\)に属するプレイヤー、すなわち提携\(C\)に属さないプレイヤーたちがどのように振る舞った場合においても、提携\(C\)に属するプレイヤーたちが互いに協力して行動した場合に確保できる利得の総和を提携値\(w_{\theta _{I}}\left( C\right) \)として採用します。具体的には以下の通りです。

まずは、提携\(C\)に売り手\(0\)が含まれない場合、すなわち\(0\not\in C\)である場合について考えます。提携\(C\)に属さないプレイヤーである売り手\(0\)が「メカニズムに参加せずに提携\(C\)に属する入札者に商品を販売しない」という行動を選択する場合、提携\(C\)に属するプレイヤーたちが協力しても商品を獲得できる見込みはないため、彼らが確保できる利得の総和は、\begin{eqnarray*}\sum_{i\in C}\left[ \theta _{i}\left( \phi \right) -0\right] &=&\sum_{i\in
C}\left( 0-0\right) \quad \because \phi _{i}\left( \phi \right) =0 \\
&=&0
\end{eqnarray*}となります。一方、売り手\(0\)が「メカニズムに参加して提携\(C\)に属する入札者に商品を販売するものの、提携\(C\)に属する入札者たちが得る利得の合計が負になってしまうような所得移転を課す」という行動を選択する場合、提携\(C\)に属するプレイヤーたちが協力して「メカニズムに参加しない」という行動を選択すれば負の利得を回避することは可能であり、その場合に彼らが確保できる利得の総和は、先と同様に、\begin{eqnarray*}\sum_{i\in C}\left[ \theta _{i}\left( \phi \right) -0\right] &=&\sum_{i\in
C}\left( 0-0\right) \quad \because \theta _{i}\left( \phi \right) =0\text{と仮定} \\
&=&0
\end{eqnarray*}となります。以上を踏まえると、\(0\not\in C\)を満たす任意の提携\(C\in 2^{I_{0}}\)に対しては、その提携値を、\begin{equation*}w_{\theta _{I}}\left( C\right) =0
\end{equation*}と定めることは理に適っています。ちなみに、提携\(\phi \)には誰も属さず、したがって\(0\not\in C\)であるため、定義より、\begin{equation*}w_{\theta _{I}}\left( \phi \right) =0
\end{equation*}となります。

続いて、提携\(C\)に売り手\(0\)が含まれる場合、すなわち\(0\in C\)である場合について考えます。この場合、提携\(C\)に属するプレイヤーたちが協力してメカニズムに参加せず、提携\(C\)に属する売り手\(0\)の商品を提携\(C\)の内部だけに供給すれば、提携\(C\)に属さないプレイヤーたちの行動が提携\(C\)に属するプレイヤーたちが得る利得に影響を与えることはできなくなります。その際、提携\(C\)に属するプレイヤーたちが内部において商品を効率的な形で分配すれば、提携\(C\)に属するプレイヤーたちが確保できる利得の総和は、\begin{eqnarray*}\max_{a_{I}\in A}\left[ \sum_{i\in C\backslash \left\{ 0\right\} }\theta
_{i}\left( a_{i}\right) +\theta _{0}\left( X\backslash \bigcup\limits_{i\in
C\backslash \left\{ 0\right\} }a_{i}\right) \right] &=&\max_{a_{I}\in
A}\sum_{i\in C\backslash \left\{ 0\right\} }\theta _{i}\left( a_{i}\right)
\quad \because \theta _{0}\left( X\backslash \bigcup\limits_{i\in
C\backslash \left\{ 0\right\} }a_{i}\right) =0 \\
&=&\max_{a_{I}\in A}\sum_{i\in C}\theta _{i}\left( a_{i}\right) \quad
\because a_{0}=X\backslash \bigcup\limits_{i\in C\backslash \left\{
0\right\} }a_{i}
\end{eqnarray*}となります。一方、提携\(C\)に属するプレイヤーたちが協力してメカニズムに参加する場合、彼らが得られる利得の総和が上の値よりも小さい場合には、メカニズムから離脱すれば上の値を確保することはできます。以上を踏まえると、\(0\in C\)を満たす任意の提携\(C\in 2^{I_{0}}\)に対しては、その提携値を、\begin{equation*}w_{\theta _{I}}\left( C\right) =\max_{a_{I}\in A}\sum_{i\in C}\theta
_{i}\left( a_{i}\right)
\end{equation*}と定めることは理に適っています。ただし、\begin{equation*}
\theta _{0}\left( a_{0}\right) =0
\end{equation*}です。以上によって提携値関数\(w_{\theta _{I}}\)の定義とします。

以上でゲーム\(\mathcal{G}\left( \theta_{I}\right) \)の要素がすべて出揃いました。つまり、状態\(\theta _{I}\)において入札者たちが直面する戦略的状況を協力ゲームとみなした場合、それは以下のような提携型ゲーム\begin{equation*}\mathcal{G}\left( \theta _{I}\right) =\left( I_{0},w_{\theta _{I}}\right)
\end{equation*}として定式化されます。ただし、このゲームのプレイヤー集合は、\begin{equation*}
I_{0}=I\cup \left\{ 0\right\}
\end{equation*}であり、提携値関数\(w_{\theta _{I}}:2^{I_{0}}\rightarrow \mathbb{R} \)がそれぞれの提携\(C\in2^{I_{0}}\)に対して定める提携値は、\begin{equation*}w_{\theta _{I}}\left( C\right) =\left\{
\begin{array}{cc}
\max\limits_{a_{I}\in A}\sum\limits_{i\in C}\theta _{i}\left( a_{i}\right)
& \left( if\ 0\in C\right) \\
0 & \left( if\ 0\not\in C\right)
\end{array}\right.
\end{equation*}です。