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

インセンティブの問題

異なる種類の商品が同時に売りに出され、入札者が商品の組合せ、すなわちパッケージに対して入札を行うオークションを組合せオークションと呼ばれる環境として定式化しました。続いて問題になるのは、どの入札者にどの商品を落札させいくら支払わせるか、その最適な結果を特定し実行することです。ただ、話がそう単純ではないことを以下で順を追って解説します。

それぞれの入札者は様々なパッケージ、すなわち商品の組合せに対する評価額を持っていますが、これは自分だけが知っている情報であり、他の入札者たちやオークションの主催者はそれを事前に観察できません。仮に、オークションが行われる前にある入札者が他の人たちに対して自身にとっての評価額を打ち明けたとしましょう。しかし、それを聞いた他の人たちは、その発言の真偽を確認する術がありません。その入札者は嘘をついているかもしれないし、本当のことを言っているかもしれない。入札者にとってパッケージへの評価額は自身の頭の中にある情報である以上、その人の発言が嘘であるか見破ることは原理的に不可能です。すべて入札者にとっての評価額についても同様の議論が成り立ちます。このとき、それぞれの入札者にとってパッケージへの評価額は私的情報（private information）であると言います。それぞれの入札者にとっての真の評価額はその人だけが私的に持っている情報であり、他の人たちはそれを事前に知ることはできないということです。一般に、市場参加者の中に私的情報を持つプレイヤーが存在する場合、その市場では情報の非対称性（asymmetric information）が成立していると言います。組合せオークション市場ではプレイヤーの間に情報の非対称性が成立しています。

オークションのルールを設計する主催者は、何らかの意味において社会的に望ましい結果を実現しようとします。仮に主催者が入札者たちにとっての真の評価額を観察できるならば、観察した評価額を基準に社会的に望ましい結果を特定し、それを遂行すればよいことになります。しかし、実際には、先に解説したような情報の非対称性が成立しているため、主催者は入札者たちにとっての真の評価額を観察できず、したがって社会的に望ましい結果を事前に特定できません。主催者は入札者たちに評価額を入札させた上で、入札額を基準に社会的に望ましい結果を特定し、それを遂行せざるを得ません。ただ、それぞれの入札者による入札額は、その入札者にとっての真の評価額と一致するとは限りません。入札者はより望ましい結果（例えば、より安く落札する）を実現するために戦略的に行動しますが、その一環として、偽りの評価額を入札する可能性があるからです。入札者にとって真の評価額は私的情報であるため、入札者が嘘をついて真の評価額とは異なる入札を行っても、主催者はそれが嘘であるかどうかを知る術がないのです。入札者たちが偽りの評価額を入札する場合、主催者は偽りの評価額を基準に結果を決定することとなり、それは真の意味で社会的に望ましい結果とは異なるものになってしまう可能性があります。情報の非対称性に起因するこのような問題をインセンティブの問題（incentive problem）と呼びます。

インセンティブの問題を引き起こす原因が情報の非対称性である以上、問題を解決するためには何らかの方法を通じて情報の非対称性を解消する必要があります。言い換えると、何らかの方法を通じて、それぞれの入札者にとっての真の評価額を特定する必要があります。ただ、繰り返しになりますが、入札者は正直に入札するとは限りませんし、そもそも正直に入札しているかどうかを判別する方法が存在しません。

ただ、それぞれの入札者にとって、自分にとっての真の評価額を正直に入札することが最も得であるようなオークションルールを設計すれば、そのようなルールのもと、入札者たちは自分にとっての真の評価額をみずから進んで正直に入札するため、結果として情報の非対称性は解消されます。さらに、そのオークションルールが同時に、申告された入札額を基準に社会的に望ましい結果を導くような形で設計されていれば、真の意味で社会的に望ましい結果を遂行できることになります。ただ、そもそも、そのようなオークションルールを設計することは可能なのでしょうか。また、可能である場合、具体的にはどのようなルールがそのような要件を満たすのでしょうか。このような問題への解を得ることが私たちの目標です。

一般に、情報の非対称性が成立する市場において、私的情報を持っている参加者をエージェント（agent）と呼びます。市場において情報の非対称性が成立する場合、エージェントが自身の利益を最大化するために戦略的に振る舞う結果、その市場ではインセンティブの問題が発生します。インセンティブの問題を解消することを目的に設計される資源配分ルールをメカニズム（mechanism）と呼び、メカニズムを設計する主体をプリンシパル（principal）と呼びます。プリンシパルは適切なメカニズムを設計することを通じて、エージェントたちの行動を社会的に望ましい方向へ誘導しようとします。組合せオークションにおけるエージェントは入札者たちです。入札者は様々なパッケージへの評価額を私的情報として持っています。入札者たちが自身にとってより望ましい結果を実現するために真の評価額とは異なる金額を入札する結果、組合せオークション市場ではインセンティブの問題が発生します。そこで、マッチメイカーはプリンシパルとして適切なメカニズム、すなわちオークションルールを設計し、入札者たちの行動を社会的に望ましい方向へ誘導しようとします。以上の視点を踏まえた上で、組合せオークションを描写するモデルを見直します。

タイプと状態

組合せオークションにおいて、それぞれの入札者は様々なパッケージへの評価額を私的情報として持つエージェントです。入札者\(i\in I\)が持つ私的情報を入札者\(i\)のタイプ（type）と呼びます。具体的には、それぞれの入札者\(i\)のタイプは、パッケージどうしを比較する評価関数\(\theta _{i}:2^{X}\rightarrow \mathbb{R} \)として集約的に表現できるものとみなします。

入札者\(i\)の真のタイプ、すなわち真の評価関数は1つだけですが、それを観察できるのは入札者\(i\)だけであり、他の任意の入札者やオークションの主催者はそれを事前に観察できません。このような事情をモデル化するために、入札者\(i\)にとっての評価関数\(\theta _{i}\)は様々な形状を取り得るものとし、その中の真の形状を知っているのは入札者\(i\)自身だけであるものとみなします。具体的には、入札者\(i\)にとっての評価関数がとり得る形状からなる集合を\(\Theta _{i}\)で表し、これを入札者\(i\)のタイプ集合（type set）や評価関数集合（setof value function）などと呼びます。\(\theta _{i}\in \Theta _{i}\)です。入札者\(i\)のタイプ\(\theta _{i}\)はタイプ集合\(\mathcal{\Theta }_{i}\)に属する様々な形状を取り得ますが、\(\theta _{i}\)の真の形状を知っているのは入札者\(i\)だけです。他の任意の入札者やオークションの主催者は、\(\theta _{i}\)のとり得る形状の範囲\(\Theta _{i}\)を知っていますが、その中のどの形状が真の形状であるかは知らないものと仮定することにより、入札者\(i\)による評価関数が私的情報であるという状況を表現するということです。

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

すべての入札者のタイプ集合からなる直積を\(\mathcal{\Theta }_{I}=\prod_{i\in I}\Theta _{i}\)で表記します。\(\theta _{I}\in \Theta _{I}\)です。また、入札者\(i\)以外の入札者たちのタイプ集合の直積を\(\mathcal{\Theta }_{-i}=\prod_{j\in I\backslash \{i\}}\Theta _{j}\)で表記します。\(\theta _{-i}\in \Theta _{-i}\)です。

入札者たちのタイプからなる組\(\theta _{I}\)は、問題としている組合せオークション市場の状態（state of the world）とも呼ばれます。すべての入札者たちの真のタイプから構成される状態\(\theta _{I}\)は、そのオークション市場の真の状態（true state）に相当します。ただ、それぞれの入札者\(i\)が知っているのは自身の真のタイプ\(\theta _{i}\)だけであり、真の状態\(\theta _{I}\)を構成する残りの要素\(\theta _{-i}\)については正確に知らず、\(\theta _{-i}\)がとり得る値の範囲\(\mathcal{\Theta }_{-i}\)だけを知っています。つまり、評価関数\(\theta _{i}\)を持つ入札者\(i\)が直面し得る状態からなる集合は、\begin{equation*}\left\{ \left( \theta _{i},\theta _{-i}\right) \right\} _{\theta _{-i}\in
\Theta _{-i}}
\end{equation*}であり、入札者\(i\)はこのことを認識しています。他の任意の入札者についても同様です。

メカニズム

仮にオークションの主催者が問題としているオークション市場の真の状態\(\theta _{I}\)を観察できるならば、観察した\(\theta _{I}\)を基準に社会的に望ましい結果を結果集合\(A\times \mathbb{R} ^{n}\)の中から選び取ることが原理的に可能であるため、インセンティブの問題は発生しません。しかし、実際には、主催者は真の状態\(\theta _{I}\)を事前に観察できず、状態がとり得る値の範囲\(\Theta _{I}\)だけを知っています。このような状況においてインセンティブの問題を解消するために、主催者は何らかのオークションルール、すなわちメカニズム設計する必要があります。

具体的には、主催者は入札者たちにタイプを申告させる（評価関数を入札させる）と同時に、申告されたタイプの組に応じて特定の結果を選択するルールをあらかじめ設計します。組合せオークションにおける結果は配分と所得移転の組であるため、ここでは2つのルールが必要になります。つまり、入札者たちが申告するタイプの組に対して配分を定めるルールと、所得移転を定めるルールです。

入札者たちが申告するタイプの組\(\theta _{I}\in \Theta _{I}\)に対して、何らかの配分\begin{equation*}a\left( \theta _{I}\right) =\left( a_{i}\left( \theta _{I}\right) \right)
_{i\in I}\in A
\end{equation*}を1つずつ定める写像\(a:\Theta _{I}\rightarrow A\)を配分ルール（allocation rule）や配分関数（allocation function）などと呼びます。ただし、\(a_{i}\left( \theta _{I}\right) \)は配分ルールが定める配分\(a\left( \theta_{I}\right) \)のもとで入札者\(i\)が入手するパッケージであるため、以下の条件\begin{eqnarray*}&&\left( a\right) \ \forall i\in I:a_{i}\left( \theta _{I}\right) \subset X
\\
&&\left( b\right) \ \bigcup\limits_{i\in I}a_{i}\left( \theta _{I}\right)
\subset X \\
&&\left( c\right) \ \forall i,j\in I:\left( i\not=j\Rightarrow a_{i}\left(
\theta _{I}\right) \cap a_{j}\left( \theta _{I}\right) =\phi \right)
\end{eqnarray*}を満たす必要があります。配分ルールが定める配分\(a\left( \theta _{I}\right) \)のもとでいかなる入札者に対しても割り当てられない商品からなる集合は、\begin{equation*}X\backslash \bigcup\limits_{i\in I}a_{i}\left( \theta _{I}\right)
\end{equation*}となります。

入札者たちが申告するタイプの組\(\theta _{I}\in \Theta _{I}\)に対して、何らかの所得移転\begin{equation*}t\left( \theta _{I}\right) =\left( t_{i}\left( \theta _{I}\right) \right)
\in \mathbb{R} ^{n}
\end{equation*}を1つずつ定める写像\(t:\Theta _{I}\rightarrow \mathbb{R} ^{n}\)を移転ルール（transfer rule）や支払い関数（payment function）などと呼びます。ただし、\(t_{i}\left( \theta_{I}\right) \)は移転ルールが定める所得移転\(t\left( \theta _{I}\right) \)のもとで入札者\(i\)に課される所得移転であるため、以下の条件\begin{equation*}\forall i\in I:t_{i}\left( \theta _{I}\right) \in \mathbb{R} \end{equation*}を満たす必要があります。移転ルールが定める所得移転\(t\left( \theta_{I}\right) \)のもとでオークションの主催者に課される所得移転は、\begin{equation*}\sum_{i\in I}t_{i}\left( \theta _{I}\right)
\end{equation*}となります。

組合せオークションにおいて、配分ルール\(a:\Theta _{I}\rightarrow A\)と移転ルール\(t:\Theta _{I}\rightarrow \mathbb{R} ^{n}\)の組を、\begin{equation*}\left( a,t\right) :\Theta _{I}\rightarrow A\times \mathbb{R} ^{n}
\end{equation*}で表記し、これをメカニズム（mechanism）や直接メカニズム（direct mechanism）もしくは結果関数（outcome function）などと呼びます。入札者たちが申告するタイプの組\(\theta _{I}\in \Theta _{I}\)に対して、メカニズム\(\left( a,t\right) \)は結果\begin{equation*}\left( a\left( \theta _{I}\right) ,t\left( \theta _{I}\right) \right) \in
A\times \mathbb{R} ^{n}
\end{equation*}を1つずつ定めます。この結果においていかなる入札者に対しても割り当てられない商品からなる集合は、\begin{equation*}
X\backslash \bigcup\limits_{i\in I}a_{i}\left( \theta _{I}\right)
\end{equation*}であり、オークションの主催者に課される所得移転は、\begin{equation*}
\sum_{i\in I}t_{i}\left( \theta _{I}\right)
\end{equation*}となります。

オークションの主催者はメカニズムを利用して以下の流れのもとで資源配分を行います。

1. オークションの主催者はメカニズム\(\left(a,t\right) :\Theta _{I}\rightarrow A\times \mathbb{R} ^{n}\)を設計し、それを入札者たちに提示する。
2. それぞれの入札者\(i\in I \)は提示されたメカニズム\(\left( a,t\right) \)に同意すれば次のステップへ進む。同意しない場合にはオークションに参加しない。
3. メカニズム\(\left( a,t\right) \)に同意したそれぞれの入札者\(i\)は、自身のタイプ\(\theta _{i}\in \Theta _{i}\)を主催者へ申告する（商品への評価関数を入札する）。その際、他の入札者たちが申告するタイプを観察することはできない。また、入札者は真のタイプを正直に申告するとは限らない（真の評価関数を正直に入札するとは限らない）。
4. 仮にすべての入札者がメカニズム\(\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) \in A\times \mathbb{R} ^{n}\)を選び取り、これを遂行する。その結果、それぞれのエージェント\(i\)は配分\(a_{i}\left( \theta_{I}\right) \)と所得移転\(t_{i}\left( \theta_{I}\right) \)に直面する（パッケージ\(a_{i}\left( \theta _{I}\right) \)を入手する対価として所得移転\(t_{i}\left( \theta _{I}\right) \)が課される）。また、集合\(X\backslash \bigcup_{i\in I}a_{i}\left( \theta _{I}\right) \)に属する商品が売れ残り、主催者は所得移転\(\sum_{i\in I}t_{i}\left( \theta _{I}\right) \)に直面する。

ここでの1つ目のポイントは、オークションの主催者は入札者たちに交渉の余地のないオファー（take-it-or-leave-it offer）をしているという点です。つまり、入札者たちは提示されたメカニズムに同意するか否かの二択に直面しており、メカニズムの内容に関して主催者と交渉する余地はありません。

2つ目のポイントは、主催者は自身が最初に提示したメカニズムを後で撤回し、別のメカニズムを再提示することはできないという点です。このとき、主催者は自身が提示したメカニズムにコミット（commit）していると言います。

3つ目のポイントは、主催者は入札者たちの真の評価関数を事前に観察できないため、直接メカニズムは入札者が申告する評価関数からなる組に対して結果を定める形にならざるを得ないということです。入札者が申告する評価関数は真の評価関数と一致するとは限りません。入札者は偽りの評価関数を申告することが得であると判断するならば戦略的に嘘をつく可能性があるからです。しかも、真の評価関数は入札者の私的情報である以上、入札者が嘘をついているか第三者は判定できません。ただ、主催者がメカニズムを巧みに設計すれば、入札者たちが真の評価関数をそのまま正直に入札するよう誘導できるとともに、社会的に望ましい結果を実現できる可能性があります。この点については後述します。

4つ目のポイントは、契約不履行（breach of contract）の可能性を考慮する必要があるという点です。例えば、落札者が支払いを拒否したり、逆に、主催者が落札者に対してメカニズムが定める支払額よりも高い金額を不当に請求するなどの問題が発生し得るため、事前に対策を講じておく必要があります。メカニズムが定める結果の履行が裁判所など第三者によって強制され得るのであれば、契約不履行の可能性は排除されているものとみなすこともできます。