組合せオークションのモデル

組合せオークション

異なる種類の商品が同時に売りに出され、それらをめぐって複数の買い手たちが入札を行うオークションを想定します。ただし、入札者が購入できる商品は1つに限定されず、売りに出されている商品の中から好きなものをいくつか選び、それらをまとめて購入することも可能であるものとします。商品の組合せをパッケージ（package）と呼びます。異なる商品が同時に売りに出されているため、それらを組合せることにより様々なパッケージを作ることができます。入札者は個々の商品に対する評価額、すなわち商品に対して支払ってもよい金額を想定していますが、同時に、商品の組合せであるパッケージへの評価額も持っています。特筆すべきは、あるパッケージへの評価額は、そのパッケージに含まれる個々の商品への評価額の和と一致するとは限らないということです。なぜなら、異なる商品を組合せて使うことにより機能や便益に相乗的なプラスの効果が発生したり、逆にマイナスの効果が発生するような事態が起こり得るからです。後ほど提示する具体例から明らかであるように、商品の組合せがもたらす相乗効果を想定した場合、商品を1つずつ売るのではなく、パッケージとして売るメリットが生まれます。いずれにせよ、パッケージへの評価額は入札者ごとに異なりますが、これは入札者の私的情報であり、他の人たちはそれを事前に観察できません。以上のような資源配分問題を組合せオークション（combinatorial auction）やパッケージオークション（package auction）などと呼びます。

以下は組合せオークションの具体例です。

プレイヤー集合

組合せオークションをモデルとして定式化します。まずはプレイヤーの表現です。組合せオークションに参加するすべての入札者（bidder）からなる集合を入札者集合（bidder set）と呼び、これを\(I\)で表記します。特に、有限\(n\)人の入札者がオークションに参加する場合、入札者集合を、\begin{equation*}I=\left\{ 1,2,\cdots ,n\right\}
\end{equation*}と特定します。入札者集合\(I\)に属する\(i\ \left(=1,2,\cdots ,n\right) \)番目のプレイヤーを入札者\(i\)（bidder \(i\)）と呼びます。\(i\in I\)です。

商品の売り手をオークションのプレイヤーに含めるべきかどうかは重要な問題です。商品の所有者がオークションの主催者に商品の販売を委託する場合や、売り手自身がオークションを主催する場合などには、売り手をオークションのプレイヤーに含める必要はありません。一方、売り手もまた商品ないしパッケージの販売希望額を提示するタイプのオークション（ダブルオークション）では、売り手もまた入札者とともにオークションのプレイヤーとみなした上で分析を行う必要があります。以降では、特に断りのない場合において、入札者だけをオークションのプレイヤーとみなした上で分析を行います。

商品集合

組合せオークションにおいて売りに出されるすべての商品からなる集合を\(X\)で表記し、個々の商品を\(x\in X\)で表記します。商品集合\(X\)の要素であるすべての商品は分割不可能であり、なおかつ個数は有限です。仮に、商品の個数が有限\(m\)個である場合、\(l\ \left( =1,\cdots ,m\right) \)番目の商品を\(x_{l}\)と表記するのであれば、商品集合を、\begin{equation*}X=\left\{ x_{1},\cdots ,x_{m}\right\}
\end{equation*}と表現できます。

組合せオークションでは商品の組合せに相当するパッケージ（package）が取引単位になります。それぞれのパッケージは商品集合\(X\)の部分集合\begin{equation*}P\subset X
\end{equation*}として定義されます。すべてのパッケージからなる集合は商品集合\(X\)のベキ集合\begin{equation*}2^{X}=\left\{ P\ |\ P\subset X\right\}
\end{equation*}に他なりませんが、これをパッケージ集合（set of packages）と呼びます。\(P\in 2^{X}\)すなわち\(P\subset X\)です。

評価関数

組合せオークションにおいて、それぞれの入札者\(i\in I\)はそれぞれのパッケージ\(P\in 2^{X}\)に対して支払ってもよい金額を頭の中で想定しているものとします。そのような金額の最大値を入札者\(i\)によるパッケージ\(P\)への評価額（valuation）や支払い意思額（willingness to pay）などと呼び、これを、\begin{equation*}\theta _{i}\left( P\right) \in \mathbb{R} \end{equation*}で表記します。入札者\(i\)は特定のパッケージに対する評価額を持っているだけではなく、パッケージ集合\(2^{X}\)の要素であるすべてのパッケージに対して評価額をそれぞれ持っているのであれば、そのような評価体系を集合関数\begin{equation*}\theta _{i}:2^{X}\rightarrow \mathbb{R} \end{equation*}として総体的に表現できます。これを入札者\(i\)の評価関数（valuation function）と呼びます。つまり、評価関数\(\theta _{i}\)を持つ入札者\(i\)は、それぞれのパッケージ\(P\in 2^{X}\)に対して最大で\(\theta_{i}\left( P\right) \in \mathbb{R} \)まで支払ってもよいと考えているということです。

すべての入札者の評価関数からなる組を\(\theta _{I}=\left( \theta _{i}\right) _{i\in I}\)で表記し、これを評価関数プロファイル（profile of valuation functions）やタイププロファイル（type profile）などと呼びます。入札者\(i\)以外の入札者たちの評価関数からなる組を\(\theta _{-i}=\left( \theta _{j}\right) _{j\in I\backslash\left\{ i\right\} }\)で表記します。\(\theta _{I}=\left( \theta _{i},\theta _{-i}\right) \)です。

多くの場合、任意の入札者\(i\)の評価関数\(\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）と呼ぶこともあります。

入札者\(i\)の評価関数\(\theta_{i}:2^{X}\rightarrow \mathbb{R} \)が標準化と単調性の仮定を満たす場合、パッケージ\(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*}を得ます。つまり、以上の仮定のもとでは、任意のパッケージへの評価額が非負の実数になることが保証されます。

オークションの結果

組合せオークションにおいて起こり得る結果を記述するためには、それぞれの入札者が入手するパッケージと、入札者に課される所得移転（落札したパッケージへの支払い額など）をそれぞれ特定する必要があります。以降で順番に解説します。

組合せオークションを行った結果として商品がどのような形で入札者たちの間に配分されるかを特定する情報を配分（allocation）と呼びます。具体的には、入札者集合\(I\)と商品集合\(X\)が与えられたとき、個々の配分は以下の条件\begin{eqnarray*}&&\left( a\right) \ \forall i\in I:a_{i}\subset X \\
&&\left( b\right) \ \bigcup\limits_{i\in I}a_{i}\subset X \\
&&\left( c\right) \ \forall i,j\in I:\left( i\not=j\Rightarrow a_{i}\cap
a_{j}=\phi \right)
\end{eqnarray*}を満たす組\(a_{I}=\left( a_{i}\right) _{i\in I}\)として定義されます。条件\(\left( a\right) \)より、配分\(a_{I}\)の成分である\(a_{i}\)は、\(a_{I}\)のもとで入札者\(i\)が入手するパッケージであることを意味します。条件\(\left( b\right) \)は、配分\(a_{I}\)において何らかの入札者に割り当てられる商品はいずれも商品集合\(X\)の要素であることを意味し、条件\(\left( c\right) \)は、同じ商品が異なる入札者に割り当てられることはないことを意味します。したがって、配分\(a_{I}\)においていかなる入札者に対しても割り当てられない商品からなる集合は、\begin{equation*}X\backslash \bigcup\limits_{i\in I}a_{i}
\end{equation*}となります。組\(a_{I}\)が配分である場合、すなわち\(a_{I}\)が以上の条件を満たす場合、\(a_{I}\)を実行することが物理的に可能です。そのようなこともあり、配分のことを実現可能な配分（feasible allocation）と呼ぶこともあります。すべての配分からなる集合を\(A\)で表記し、これを配分集合（allocation set）と呼びます。\(a_{I}\in A\)です。

組合せオークションを行った結果として入札者たちに課される所得移転を特定する情報を所得移転（transfer）と呼びます。具体的には、入札者集合\(I\)が与えられたとき、個々の所得移転は以下の条件\begin{equation*}\forall i\in I:t_{i}\in \mathbb{R} \end{equation*}を満たす組\(t_{I}=\left( t_{i}\right) _{i\in I}\)として定義されます。ただし、\(t_{I}\)の成分である\(t_{i}\)は、\(t_{I}\)のもとで入札者\(i\)に課される所得移転であり、上の条件より、これは任意の実数を値としてとり得るとともに、\begin{eqnarray*}t_{i} &>&0\Leftrightarrow \text{入札者}i\text{は}t_{i}\text{だけ支払う} \\
t_{i} &<&0\Leftrightarrow \text{入札者}i\text{は}t_{i}\text{だけ受け取る} \\
t_{i} &=&0\Leftrightarrow \text{入札者}i\text{の収支は均衡}
\end{eqnarray*}と解釈されます。

所得移転\(t_{I}\)が与えられたとき、すべての入札者による所得移転の総和\begin{equation*}\sum_{i\in I}t_{i}
\end{equation*}をとると、これはオークションの主催者に課される所得移転に相当します。つまり、\begin{eqnarray*}
\sum_{i\in I}t_{i} &>&0\Leftrightarrow \text{主催者の収支は黒字} \\
\sum_{i\in I}t_{i} &<&0\Leftrightarrow \text{主催者の収支は赤字} \\
\sum_{i\in I}t_{i} &=&0\Leftrightarrow \text{主催者の収支は均衡}
\end{eqnarray*}という関係が成り立ちます。

任意の入札者\(i\in I\)に課される所得移転は\(t_{i}\in \mathbb{R} \)を満たすため、所得移転\(t_{I}\)は\(\mathbb{R} ^{n}\)の点として表現されます。起こり得るすべての所得移転からなる集合\(\mathbb{R} ^{n}\)を所得移転集合（transfer set）と呼びます。\(t_{I}\in \mathbb{R} ^{n}\)です。

組合せオークションにおける結果（outcome）とは、配分と所得移転の組\begin{equation*}
\left( a_{I},t_{I}\right)
\end{equation*}として定義されます。結果\(\left( a_{I},t_{I}\right) \)において、入札者\(i\)はパッケージ\(a_{i}\)を入手する対価として所得移転\(t_{i}\)が課されます。また、売れ残る商品からなる集合は、\begin{equation*}X\backslash \bigcup\limits_{i\in I}a_{i}
\end{equation*}であり、オークションの主催者に課される所得移転は、\begin{equation*}
\sum_{i\in I}t_{i}
\end{equation*}となります。起こり得るすべての結果からなる集合\(A\times \mathbb{R} ^{n}\)を結果集合（outcome set）と呼びます。\(\left(a_{I},t_{I}\right) \in A\times \mathbb{R} ^{n}\)です。

利得関数

それぞれの入札者\(i\)はパッケージを評価する評価関数\(\theta _{i}:2^{X}\rightarrow \mathbb{R} \)を持っていますが、組合せオークションにおいて起こり得る帰結が結果\(\left(a_{I},t_{I}\right) \in A\times \mathbb{R} ^{n}\)として表現されることを踏まえると、入札者\(i\)は評価関数\(\theta _{i}\)だけでなく、結果どうしを比較する評価体系を持っていなければ、オークションにおいて起こり得る帰結を評価できないことになってしまいます。そこで、それぞれの入札者\(i\)は結果集合\(A\times \mathbb{R} ^{n}\)上に定義された関数\begin{equation*}u_{i}:A\times \mathbb{R} ^{n}\rightarrow \mathbb{R} \end{equation*}を持っているものとし、これを入札者\(i\)の利得関数（payoff function）と呼びます。また、利得関数\(u_{i}\)が結果\(\left(a_{I},t_{I}\right) \in A\times \mathbb{R} ^{n}\)に対して定める値\begin{equation*}u_{i}\left( a_{I},t_{I}\right) \in \mathbb{R} \end{equation*}を、入札者\(i\)が結果\(\left(a_{I},t_{I}\right) \)から得る利得（payoff）と呼びます。その上で、2つの結果\(x,y\in A\times \mathbb{R} ^{n}\)を任意に選んだとき、\begin{eqnarray*}u_{i}\left( x\right) &\geq &u_{i}\left( y\right) \Leftrightarrow \text{入札者}i\text{は}x\text{を}y\text{以上に好む} \\
u_{i}\left( x\right) &>&u_{i}\left( y\right) \Leftrightarrow \text{入札者}i\text{は}x\text{を}y\text{よりも好む} \\
u_{i}\left( x\right) &=&u_{i}\left( y\right) \Leftrightarrow \text{入札者}i\text{は}x\text{を}y\text{と同じ程度好む}
\end{eqnarray*}を満たすものとして\(u_{i}\)は定義されます。つまり、利得関数を用いれば、結果どうしの相対的な望ましさを、結果がもたらす利得の大小関係として表現できるということです。

一般に、入札者\(i\)の利得関数\(u_{i}\)の形状は、自分にとってのパッケージへの評価、すなわち評価関数\(\theta _{i}\)に依存して変化します。なぜなら、例えば、入札者\(i\)があるパッケージを不要と考えている場合には、入札者\(i\)はそのパッケージを落札せず支払いも行わないことを最も好むと考えるのが自然です。逆に、入札者\(i\)がそのパッケージを高く評価している場合には、そのような結果よりも、そのパッケージを落札し、支払いを行う結果を好むと考えるのが自然です。このような事情を踏まえると、入札者\(i\)の利得関数\(u_{i}\)は自身の評価関数\(\theta _{i}\)に依存して変化するという意味を込めて、これを\(u_{i}\left( \cdot ,\theta_{i}\right) \)と表記すべきです。

ただ、入札者\(i\)の利得関数\(u_{i}\)は、自身の評価関数\(\theta _{i}\)だけに依存するのではなく、他の入札者たちの評価関数\(\theta _{-i}\)に依存する状況も起こり得ます。なぜなら、例えば、入札者\(i\)が落札したパッケージを転売することを見越した上でオークションに参加する場合、他の入札者たちがそのパッケージを低く評価しているならば、入札者\(i\)はそのパッケージ落札せず支払いも行わないことを最も好むと考えるのが自然です。逆に、他の入札者たちがそのパッケージを高く評価している場合には、そのような結果よりも、そのパッケージを正の確率で落札し、支払いを行う結果を好むと考えるのが自然です。このような事情を踏まえると、入札者\(i\)の利得関数\(u_{i}\)は自身の評価関数\(\theta _{i}\)だけでなく、他の入札者たちの評価関数\(\theta _{-i}\)にも依存して変化するという意味を込めて、これを\(u_{i}\left( \cdot ,\theta_{i},\theta _{-i}\right) \)すなわち\(u_{i}\left( \cdot,\theta _{I}\right) \)と表記すべきです。

環境

組合せオークションを表現するモデルの要素は以上ですべてです。つまり、組合せオークションを描写するためには、そこに参加する入札者からなる集合\(I\)、商品集合\(X\)、それぞれの入札者\(i\in I\)の評価関数\(\theta _{i}:2^{X}\rightarrow \mathbb{R} \)、結果集合\(A\times \mathbb{R} ^{n}\)、それぞれの入札者\(i\)の利得関数\(u_{i}\left( \cdot ,\theta_{I}\right) :A\times \mathbb{R} ^{n}\rightarrow \mathbb{R} \)を特定することになります。以上の要素からなるモデルを、\begin{equation*}\left( I,X,\left\{ \theta _{i}\right\} _{i\in I},A\times \mathbb{R} ^{n},\left\{ u_{i}\left( \cdot ,\theta _{I}\right) \right\} _{i\in I}\right)
\end{equation*}と表記し、これによって組合せオークションの定義とします。このようなモデルを環境（environment）と呼ぶこともあります。