ヴィックリー・クラーク・グローブスオークション

ヴィックリー・クラーク・グローブス（VCG）オークションは、複数の品物を対象とする密封入札オークションの一種である。入札者は、他の入札者の入札額を知らずに、品物に対する自分の評価額を記載した入札を行う。オークションシステムは、社会的に最適な方法で品物を割り当て、各入札者に他の入札者に与えた損害を請求する。^{[1]各入札者にとって最適な戦略が品物の}本当の評価額で入札することであることを保証することにより、入札者に本当の評価額で入札するインセンティブを与える。これは、入札者の共謀や、特に状況によっては1人の入札者が異なる名前で複数の入札を行うことによって損なわれる可能性がある。これは、複数の品物に対する ヴィックリーオークションの一般化である。

このオークションは、このアイデアを次々に一般化した論文を発表した ウィリアム・ヴィックリー^[2]、 エドワード・H・クラーク^[3]、セオドア・グローブス^[4]にちなんで名付けられました。

VCGオークションは、より一般的なVCGメカニズムの特殊な使用法です。VCGオークションは社会的に最適なアイテムの割り当てを試みますが、VCGメカニズムは、一連の可能な結果の中から社会的に最適な結果を選択することを可能にします。入札者間で共謀が発生する可能性が高い場合、VCGは、売り手に生み出される収益と配分効率の両方において、一般化された第2価格オークションよりも優れています。 ^[5]

同一製品のセットが販売されているオークションを考えてみましょう。入札者は、N 個の製品を受け取るために支払う意思のある最高価格を宣言することで、オークションに参加できます。各購入者は、受け取るユニットの合計数に応じてユニットあたりの支払意思が異なる可能性があるため、複数の入札を宣言できます。入札者は、他の人の入札をいつでも見ることはできません。入札は封印されているため (オークション システムでのみ表示されます)。すべての入札が行われると、オークションは終了します。

オークション システムでは、入札の可能な組み合わせがすべて検討され、入札の合計額が最大になる組み合わせが保持されます。ただし、その合計額が利用可能な製品の合計額を超えず、各入札者から最大 1 つの入札が使用されるという条件が付きます。入札に成功した入札者は、入札で指定した数量の製品を受け取ります。ただし、入札者が支払う価格は、最初に入札した金額ではなく、入札が他の入札者に与えた限界的な損害 (最大でも最初の入札額と同じ) のみです。

他の参加者に生じる限界的な損害（つまり、入札に成功した各個人が支払う最終価格）は、次のように計算できます。（検討中の参加者を除いた最良の入札の組み合わせによるオークションの入札額の合計）−（現在の（最良の）入札の組み合わせで他の落札者が入札した金額）。2番目に良い入札の組み合わせの入札額の合計が最良の組み合わせの入札額と同じ場合、購入者が支払う価格は最初の入札額と同じになります。その他の場合はすべて、購入者が支払う価格は低くなります。

オークションの終了時には、すべての商品が最高の支払意思額を持つ人々に帰属するため、総効用は最大化されます。エージェントが完全に合理的で共謀がない場合、他の入札者への限界損害のみが各参加者に請求されるため、支払意思額は正直に報告されたと想定でき、正直な報告は弱優位戦略になります。ただし、このタイプのオークションでは、2番目に良い入札の組み合わせの入札額の合計が、最も良い入札の組み合わせの入札額の合計と等しくない限り、売り手の収益は最​​大化されません。

オークションにかけられた品物の任意の集合と入札者の任意の集合について、与えられた入札の組み合わせに対する VCG オークションの社会的価値を とします。つまり、各人が落札した品物にどれだけの価値を置いているかを全員で合計したものです。落札しなかった場合、品物の価値は 0 です。入札者と品物について、品物に対する入札者の入札額を とします。この表記は、B の要素ではない A の要素の集合を意味します。 ${\displaystyle M=\{t_{1},\ldots ,t_{m}\}}$${\displaystyle N=\{b_{1},\ldots ,b_{n}\}}$${\displaystyle V_{N}^{M}}$${\displaystyle b_{i}}$${\displaystyle t_{j}}$${\displaystyle v_{i}(t_{j})}$${\displaystyle A\setminus B}$

ある品物に対して「入札額超過額」、つまり の入札を行った入札者は、その品物を落札しますが、 を支払います。これは、残りのエージェントが被る落札の社会的コストです。 ${\displaystyle b_{i}}$${\displaystyle t_{j}}$${\displaystyle v_{i}(t_{j})}$${\displaystyle V_{N\setminus \{b_{i}\}}^{M}-V_{N\setminus \{b_{i}\}}^{M\setminus \{t_{j}\}}}$

実際、 以外の入札者の集合はです。品目が入手可能な場合、入札者は福祉 を達成できます。による品目の落札により、入手可能な品目の集合が に減少するため、達成可能な福祉は になります。したがって、2 つの福祉レベルの差は、落札者が品目 を入手したと仮定した場合の予測どおり、残りの入札者が被る達成可能な福祉の損失です。この量は、残りのエージェントのオファーによって決まり、エージェント には不明です。 ${\displaystyle b_{i}}$${\displaystyle N\setminus \{b_{i}\}}$${\displaystyle t_{j}}$${\displaystyle V_{N\setminus \{b_{i}\}}^{M}.}$${\displaystyle b_{i}}$${\displaystyle M\setminus \{t_{j}\}}$${\displaystyle V_{N\setminus \{b_{i}\}}^{M\setminus \{t_{j}\}}}$${\displaystyle b_{i}}$${\displaystyle t_{j}}$${\displaystyle b_{i}}$

入札額が商品の真の価値である落札者は、最大の効用を得る。${\displaystyle A}$${\displaystyle t_{j}}$${\displaystyle v_{i}(t_{j})=A,}$${\displaystyle A-\left(V_{N\setminus \{b_{i}\}}^{M}-V_{N\setminus \{b_{i}\}}^{M\setminus \{t_{j}\}}\right).}$

2 個のリンゴが 3 人の入札者の間でオークションにかけられているとします。

• 入札者 A はリンゴを 1 個欲しがっており、そのリンゴに対して 5 ドルを支払うつもりです。
• 入札者 B はリンゴ 1 個を希望しており、2 ドルを支払うつもりです。
• 入札者 C はリンゴを 2 個欲しがっており、両方手に入れるために 6 ドルを支払う用意はありますが、片方だけ購入してもう片方を買うつもりはありません。

まず、入札額を最大化することでオークションの結果が決定されます。リンゴは入札者 A と入札者 B に渡ります。彼らの入札額の合計は 5 ドル + 2 ドル = 7 ドルで、リンゴ 2 個に対して 6 ドルしか支払わない入札者 C の入札額よりも高いからです。したがって、オークション後、入札者 A が獲得した価値は 5 ドル、入札者 B は 2 ドル、入札者 C は 0 ドルになります (入札者 C は何も得られないため)。勝者の決定は本質的にナップサック問題であることに注意してください。

次に、支払いを決定するための式は次のようになります。

• 入札者Aの場合: A に要求される落札額は次のように決定されます。まず、入札者 A を除外したオークションでは、社会的福祉を最大化する結果として、両方のリンゴが入札者 C に割り当てられ、合計社会的価値は 6 ドルになります。次に、A の価値を除外した元のオークションの合計社会的価値は、7 ドル - 5 ドル = 2 ドルと計算されます。最後に、最初の値から 2 番目の値を減算します。したがって、A に要求される支払額は 6 ドル - 2 ドル = 4 ドルです。
• 入札者Bの場合: 上記と同様に、入札者 B を除外したオークションの最良の結果は、両方のリンゴを 6 ドルで入札者 C に割り当てることです。元のオークションの合計社会的価値からB の部分を引いた値は 5 ドルです。したがって、B に要求される支払いは 6 ドル - 5 ドル = 1 ドルです。
• 最終的に、入札者 C の支払額は (($5 + $2) − ($5 + $2)) = $0 となります。

オークション後、A はオークション前よりも 1 ドル得ており (4 ドル支払って 5 ドルの効用を得ている)、B はオークション前よりも 1 ドル得ており (1 ドル支払って 2 ドルの効用を得ている)、C は中立 (何も勝っていない) です。

入札者が 2 人、が2 つのアイテム、 が あり、各入札者は 1 つのアイテムを取得できると仮定します。 をアイテム に対する入札者の評価額とします。、、、および と仮定します。 と はどちらもアイテム の受け取りを好むことがわかります。ただし、社会的に最適な割り当てでは、アイテム が入札者 (したがって達成値は ) に与えられ、アイテムが入札者(したがって達成値は) に与えられます。したがって、達成値の合計は となり、最適です。 ${\displaystyle b_{1}}$${\displaystyle b_{2}}$${\displaystyle t_{1}}$${\displaystyle t_{2}}$${\displaystyle v_{i,j}}$${\displaystyle b_{i}}$${\displaystyle t_{j}}$${\displaystyle v_{1,1}=10}$${\displaystyle v_{1,2}=5}$${\displaystyle v_{2,1}=5}$${\displaystyle v_{2,2}=3}$${\displaystyle b_{1}}$${\displaystyle b_{2}}$${\displaystyle t_{1}}$${\displaystyle t_{1}}$${\displaystyle b_{1}}$${\displaystyle 10}$${\displaystyle t_{2}}$${\displaystyle b_{2}}$${\displaystyle 3}$${\displaystyle 13}$

人がオークションに参加していなかった場合、人はに割り当てられたままとなり、したがって人はそれ以上何も得ることができません。現在の結果は であり、したがって に課金されます。 ${\displaystyle b_{2}}$${\displaystyle b_{1}}$${\displaystyle t_{1}}$${\displaystyle b_{1}}$${\displaystyle 10}$${\displaystyle b_{2}}$${\displaystyle 10-10=0}$

人がオークションに参加していなかった場合、に割り当てられ、評価額は になります。現在の結果は 3 なので、 が請求されます。 ${\displaystyle b_{1}}$${\displaystyle t_{1}}$${\displaystyle b_{2}}$${\displaystyle 5}$${\displaystyle b_{1}}$${\displaystyle 5-3=2}$

入札者それぞれが家を受け取ることになる家のオークションを考えてみましょう。 は、プレイヤーが家に対して持つ価値を表します。 起こり得る結果は、家と人をペアにする二部マッチングによって特徴付けられます。 価値がわかっていれば、社会的福祉を最大化することは、最大重み二部マッチングを計算することにつながります。 ${\displaystyle n}$${\displaystyle n}$${\displaystyle {\tilde {v}}_{ij}}$${\displaystyle i}$${\displaystyle j}$

値がわからない場合は、代わりに入札 を募り、各プレイヤーが家 にいくら入札したいかを尋ねます。入札者がマッチング で家を受け取るかどうかを定義します。次に、入札 に関する最大重み二部マッチング を計算し、計算します。 ${\displaystyle {\tilde {b}}_{ij}}$${\displaystyle i}$${\displaystyle j}$${\displaystyle b_{i}(a)={\tilde {b}}_{ik}}$${\displaystyle i}$${\displaystyle k}$${\displaystyle a}$${\displaystyle a^{*}}$

${\displaystyle p_{i}=\left[\max _{a\in A}\sum _{j\neq i}b_{j}(a)\right]-\sum _{j\neq i}b_{j}(a^{*})}$。

最初の項は別の最大重み二部マッチングであり、2 番目の項は から簡単に計算できます。 ${\displaystyle a^{*}}$

以下は、オークションに出品された品物に対して自分の本当の評価額で入札することが最適であることの証明である。^[6]

各入札者について、 をアイテムの真の評価額 とし、(一般性を失うことなく) が真の評価額を提出して落札したとします。すると、によって得られる純効用は、落札したアイテムの入札者自身の評価額から支払った価格を差し引いた値で与えられます。 ${\displaystyle b_{i}}$${\displaystyle v_{i}}$${\displaystyle t_{i}}$${\displaystyle b_{i}}$${\displaystyle t_{i}}$${\displaystyle U_{i}}$${\displaystyle b_{i}}$

${\displaystyle {\begin{aligned}U_{i}&=v_{i}-\left(V_{N\setminus \{b_{i}\}}^{M}-V_{N\setminus \{b_{i}\}}^{M\setminus \{t_{i}\}}\right)\\&=\sum _{j}v_{j}-\sum _{j\neq i}v_{j}+V_{N\setminus \{b_{i}\}}^{M\setminus \{t_{i}\}}-V_{N\setminus \{b_{i}\}}^{M}\\&=\sum _{j}v_{j}-V_{N\setminus \{b_{i}\}}^{M\setminus \{t_{i}\}}+V_{N\setminus \{b_{i}\}}^{M\setminus \{t_{i}\}}-V_{N\setminus \{b_{i}\}}^{M}\\&=\sum _{j}v_{j}-V_{N\setminus \{b_{i}\}.}^{M}\end{aligned}}}$

は とは独立して、 メカニズムによって、宣言された入札に対する企業の総効用最大化とともに、純効用最大化が追求されます。 ${\displaystyle V_{N\setminus \{b_{i}\}}^{M}}$${\displaystyle v_{i}}$${\displaystyle \sum _{j}v_{j}}$${\displaystyle v_{i}}$

より明確にするために、真実の入札で得た商品の純効用と、真実でない入札で得た商品 の入札者の真の効用 の純効用との差を形成してみましょう。 ${\displaystyle U_{i}-U_{j}=\left[v_{i}+V_{N\setminus \{b_{i}\}}^{M\setminus \{t_{i}\}}\right]-\left[v_{j}+V_{N\setminus \{b_{i}\}}^{M\setminus \{t_{j}\}}\right]}$${\displaystyle U_{i}}$${\displaystyle b_{i}}$${\displaystyle v_{i}}$${\displaystyle t_{i}}$${\displaystyle U_{j}}$${\displaystyle b_{i}}$${\displaystyle v'_{i}}$${\displaystyle t_{i}}$${\displaystyle t_{j}}$${\displaystyle v_{j}}$

${\displaystyle \left[v_{j}+V_{N\setminus \{b_{i}\}}^{M\setminus \{t_{j}\}}\right]}$は、不誠実な入札で得られる企業総効用である。しかし、割り当ては、最大の（真の）企業総効用が得られる割り当てとは異なる。したがって 、${\displaystyle t_{j}}$${\displaystyle b_{i}}$${\displaystyle t_{i}}$${\displaystyle b_{i}}$${\displaystyle \left[v_{i}+V_{N\setminus \{b_{i}\}}^{M\setminus \{t_{i}\}}\right]-\left[v_{j}+V_{N\setminus \{b_{i}\}}^{M\setminus \{t_{j}\}}\right]\geq 0}$${\displaystyle U_{i}\geq U_{j}}$

• ヴィックリー・クラーク・グローブス機構
• ヴィックリーオークション
• 好みの啓示