ヴィックリーオークション

ヴィックリーオークション、または封印入札第二価格オークション（SBSPA ）は、封印入札オークションの一種です。入札者は、オークションに参加している他の人の入札額を知らずに、書面で入札します。最高額の入札者が落札しますが、実際に支払われる価格は2番目に高い入札額です。このタイプのオークションは、戦略的にはイングリッシュオークションに似ており、入札者に真の価値で入札するインセンティブを与えます。このオークションは、1961年にコロンビア大学のウィリアム・ヴィックリー教授によって初めて学術的に記述されました^{[ 1 ]}が、切手収集家は1893年から使用していました^{[ 2 ]。} 1797年には、ヨハン・ヴォルフガング・フォン・ゲーテが封印入札第二価格オークションを使用して原稿を売却しました^{[ 3 ] 。}

ヴィックリーの原著論文は、主に単一の不可分な財のみが販売されるオークションを対象としていた。この場合に限って、ヴィックリーオークションと第二価格封印入札オークションという用語は同義であり、互換的に使用される。複数の同一財の場合、入札者は逆需要曲線を提出し、機会費用を支払う。^{[ 4 ]}

ヴィックリーオークションは経済学の文献ではよく研究されているが、実際にはあまり一般的ではない。複数ユニットオークション向けのヴィックリーオークションの一般化された変種が存在し、例えば、GoogleやYahoo!のオンライン広告プログラムで使用されている一般化第2価格オークション^{[ 5 ] [ 6 ]} （インセンティブ適合性なし）やヴィックリー・クラーク・グローブスオークション（インセンティブ適合性あり）などがある。

単一の分割不可能なアイテムを扱うヴィックリーオークションにおける支配的な戦略は、各入札者がそのアイテムの真の価値を入札することである。^{[ 7 ]}

させて${\displaystyle v_{i}}$入札者 i の商品に対する価値を とします。${\displaystyle b_{i}}$入札者になる${\displaystyle i{\text{'s}}}$商品に入札する。入札者への報酬${\displaystyle i}$は

${\displaystyle {\begin{cases}v_{i}-\max _{j\neq i}b_{j}&{\text{if }}b_{i}>\max _{j\neq i}b_{j},\\0&{\text{otherwise.}}\end{cases}}}$

過剰入札戦略は、正直に入札すること（つまり、${\displaystyle v_{i}}$入札者が${\displaystyle i}$入札${\displaystyle b_{i}>v_{i}}$。

• もし${\displaystyle \max _{j\neq i}b_{j}<v_{i}}$その場合、入札者は正直な入札でも、過剰入札でも商品を落札できることになる。入札額は利益に影響を与えないため、この場合、2つの戦略の利益は等しくなる。
• もし${\displaystyle \max _{j\neq i}b_{j}>b_{i}}$そうなると、入札者はどちらにしても商品を失うことになるので、この場合、どちらの戦略も同等の利益を得ることになる。
• もし${\displaystyle v_{i}<\max _{j\neq i}b_{j}<b_{i}}$そうなると、競りで勝つには過剰入札戦略しか選択肢がなくなる。過剰入札戦略では、商品の価値よりも多く支払うことになるため、利益はマイナスとなる。一方、適正価格で入札した場合の利益はゼロとなる。

したがって、真の評価額よりも高い金額で入札する戦略は、正直に入札する戦略に劣勢である。低い金額で入札する戦略も、正直に入札する戦略に劣勢である。入札者が${\displaystyle i}$入札${\displaystyle b_{i}<v_{i}}$。

• もし${\displaystyle \max _{j\neq i}b_{j}>v_{i}}$その場合、入札者は正直な入札でも低めの入札でも商品を失うことになるため、この場合、どちらの戦略も同等の利益をもたらすことになる。
• もし${\displaystyle \max _{j\neq i}b_{j}<b_{i}}$そうすれば、どちらの方法でも入札者が商品を落札できるため、この場合、どちらの戦略も同等の利益が得られることになる。
• もし${\displaystyle b_{i}<\max _{j\neq i}b_{j}<v_{i}}$そうなると、正直に入札する戦略だけがオークションに勝つことになる。正直な戦略では、商品の価値よりも低い金額で落札できるため、利益はプラスになるが、低額入札の利益はゼロとなる。

したがって、低価格入札戦略は、正直入札戦略に劣勢となる。正直入札は他の可能な戦略（すなわち、低価格入札と高価格入札）に勝るため、最適な戦略である。

最も一般的なオークションは、封印された第一価格（または最高入札）オークションと、公開された上昇価格（または英国式）オークションの2種類です。前者では、各購入者が封印された入札書を提出します。最高入札者が商品を受け取り、入札額を支払います。後者では、オークション主催者が次々と高い提示価格を発表し、誰もそれ以上の価格を受け入れなくなるまで続けます。購入者の評価額が${\displaystyle v}$そして現在の希望価格は${\displaystyle b}$。 もし${\displaystyle v<b}$そうすれば、買い手は手を挙げて負けることになる。${\displaystyle v>b}$買い手が現在の最高入札者でない場合、他の誰かに落札させるよりも入札する方が有利です。したがって、提示価格が買い手の評価額に達した時点で入札から撤退することは、買い手にとって支配的な戦略となります。つまり、ヴィックリーの封印された第二価格オークションと同様に、最も高い評価額を持つ買い手が支払う価格は、2番目に高い評価額と等しくなります。

次に、封印された第二価格オークションにおける予想支払額について考えてみましょう。ヴィックリーは2人の買い手の場合を検討し、各買い手の価値は、サポートを持つ一様分布からの独立した抽出であると仮定しました。${\displaystyle [0,1]}$買い手が支配的な戦略に従って入札する場合、評価額の高い買い手は${\displaystyle v}$相手の値が${\displaystyle x<v}$仮に${\displaystyle v}$が最高値です。すると、賞金は区間内で均等に分配されます。${\displaystyle [0,v]}$したがって、勝者の予想支払額は

${\displaystyle e(v)={\tfrac {1}{2}}v.}$

ここで我々は、封印された第一価格オークションにおいて、評価額が${\displaystyle v}$は

${\displaystyle B(v)=e(v)={\tfrac {1}{2}}v.}$

つまり、封印された第一価格オークションの落札者への支払額は、封印された第二価格オークションの予想収益と等しい。

収益等価性の証明

買い手2が戦略に従って入札すると仮定します${\displaystyle B(v)=v/2}$、 どこ${\displaystyle B(v)}$買い手の評価額の入札額は${\displaystyle v}$買い手1にとって最善の対応策は、同じ戦略を用いることであることを示す必要がある。

まず、買い手2がこの戦略を使用する場合、${\displaystyle B(v)=v/2}$すると、購入者2の最大入札額は${\displaystyle B(1)=1/2}$したがって、1/2以上の入札であれば、買い手1は確率1で勝利します。次に、入札について考えてみましょう。${\displaystyle b}$インターバル中に${\displaystyle [0,1/2]}$購入者2の価値を${\displaystyle x}$すると、買い手1が勝ちます。${\displaystyle B(x)=x/2<b}$つまり、${\displaystyle x<2b}$ヴィックリーの値が一様分布しているという仮定の下では、勝率は${\displaystyle w(b)=2b}$したがって、購入者1の期待収益は

${\displaystyle U(b)=w(b)(vb)=2b(vb)={\tfrac {1}{2}}[v^{2}-(v-2b)^{2}]}$

ご了承ください${\displaystyle U(b)}$最大となるのは${\displaystyle b=v/2=B(v)}$。

ネットワークルーティングにおいて、VCGメカニズムは付加価値の概念に基づいた支払いスキームの一種です。ネットワークルーティングにおけるVCGメカニズムの基本的な考え方は、ソリューションの一部である各リンクまたはノード（ネットワークモデルによって異なります）の所有者に対し、その申告コストに付加価値を加えた金額を支払うことです。多くのルーティング問題において、このメカニズムは戦略耐性を持つだけでなく、戦略耐性を持つメカニズムの中でも最小のものです。

ネットワークフロー（ユニキャストまたはマルチキャスト）の場合、グラフGにおける最小コストフロー（MCF）は、各リンクの宣言されたコストd _{kに基づいて計算され、支払いは次のように計算されます。}

各リンク（またはノード）${\displaystyle e_{k}}$MCFでは支払われます

${\displaystyle p_{k}=d_{k}+\operatorname {MCF} (G-e_{k})-\operatorname {MCF} (G),}$

ここで、MCF( G )はグラフGにおける最小コストフローのコストを示し、G  − e _kはリンクe _kを除いたグラフGを示します。MCFに含まれないリンクには何も支払われません。このルーティング問題は、VCGが戦略耐性があり、かつ最小コストであるケースの1つです。 

2004年に、 n個のノードとエッジ確率pを持つErdős–Rényiランダムグラフの期待VCG過払いが示されました。${\displaystyle \scriptstyle G\in G(n,p)}$アプローチ

${\displaystyle {\frac {p}{2-p}}}$

nが近づくにつれて、${\displaystyle \scriptstyle \infty }$、 のために${\displaystyle np=\omega ({\sqrt {n\log n}})}$この結果が出る前は、G ( n , p )におけるVCGの過払いは 

$\displaystyle \Omega \left({\frac {1}{np}}\right)}$

そして

${\displaystyle O(1)\,}$

高い確率で

${\displaystyle np=\omega (\log n).\,}$

複数または分割可能な財への最も明白な一般化は、すべての落札者が落札できなかった最高額の入札額を支払うことです。これは均一価格オークションとして知られています。ただし、均一価格オークションでは、各入札者が単一の単位のみを需要している場合を除き、入札者が第二価格オークションのように真の評価額を入札することはありません。正直に入札するインセンティブを維持するヴィックリーオークションの一般化は、ヴィックリー・クラーク・グローブス（VCG）メカニズムとして知られています。VCGの考え方は、効用の合計を最大化するようにアイテムが割り当てられ、各入札者は、自分の存在が他のすべてのプレイヤーにもたらす「機会費用」を支払うことです。入札者にとってのこの機会費用は、最初の入札者が入札しなかった場合に落札したであろう他のすべての入札者の合計入札額から、他のすべての実際の落札者の合計入札額を差し引いたものとして定義されます。

別の一般化の例として、最低落札価格（その価格を下回ると商品は一切売れない）を設定する方法があります。場合によっては、最低落札価格を設定することで、オークション主催者の収益を大幅に増やすことができます。これは、ベイズ最適メカニズム設計の一例です。

メカニズム設計において、啓示原理はヴィックリーオークションの一般化と見なすことができる。

• オークション理論
• 第一価格入札オークション
• VCGオークション
• ベッカー・デグルート・マルシャック法

• ヴィジャイ・クリシュナ著『オークション理論』、アカデミック・プレス、2002年。
• Peter Cramton、Yoav Shoham、Richard Steinberg (編)、 『Combinatorial Auctions』、MIT Press、2006年、第1章 。ISBN 0-262-03342-9。
• ポール・ミルグロム著『オークション理論の実践』（ケンブリッジ大学出版局、2004年）。
• テック・ホー、「消費と生産」、カリフォルニア大学バークレー校、ハース・ビジネススクール、2010年卒業。