Vickrey-Clarke-Groves (VCG) メカニズム
- 提唱者
- William Vickrey, Edward Clarke, Theodore Groves
- 年
- 1961
- 種類
- algorithm
- 系統
- Game-theoretic
この文章は機械翻訳で、まだ確認されていません。 英語の原文を読む
何をする手法か?
Vickrey-Clarke-Groves (VCG) メカニズムは、参加者に真の評価額を提示するようインセンティブを与えるための、資源配分と支払い決定を行う真実性メカニズム設計解法である。William Vickrey による1961年の密封型入札に関する研究を基盤とし、Clarke と Groves によって拡張された VCG は、すべての参加者にとって真実の報告が支配的戦略となることを保証し、配分効率を達成すると同時に総余剰を最大化する。
手法の背後にある直感
VCG メカニズムは、入札者や配分における根本的な問題、すなわち、有利になるために本来の選好を偽る可能性のある参加者から正直な評価額を引き出す方法を解決する。その鍵となる洞察は、各参加者に、他の参加者が存在しない場合に得られたであろう額、すなわち彼らが他者に課す外部性の額に等しい価格を請求することである。この設計により、嘘をつくことは不採算となり、入札者は真実に入札することで自身の余剰を最大化する。
歴史学
William Vickrey は1961年に密封型第二価格入札(Vickreyオークション)を導入し、それが真実の入札を引き出すことを証明した。Edward Clarke と Theodore Groves は独立にこの原理を、外部性に基づく支払いを持つより一般的な配分メカニズムに拡張した。彼らの貢献は現代のメカニズム設計理論の基礎を形成し、Vickrey は1996年に経済学分野でノーベル賞を受賞(死後)し、特にスペクトルオークションやオンライン広告市場において、実用的なオークション設計に深く影響を与えた。
使うべき場面
選好の真実の開示が不可欠な資源配分、入札、または公共財供給のためのメカニズムを設計する際に VCG を適用する。組合せ入札(相互依存的な価値を持つ複数の品目)、スペクトル配分、および調達に理想的である。インセンティブ両立性と配分効率の両方を達成することが優先順位であり、たとえ総支払額が代替設計よりも高くなる可能性がある場合でも使用する。
限界と注意点
- 多数の品目または参加者に対して計算上実行不可能であり、勝者決定がNP困難となる
- しばしば赤字(支払額が収入を超える)を生じ、一部の応用では補助金が必要となる
- 注意深く監視されない場合、共謀や入札者の参加/離脱に対して脆弱
- 参加者にとって直感的でない場合があり、実用的な設定での採用を減少させる可能性がある
出典に示された条件は、独立した科学的レビューや分析エンジンによる検証の代わりにはなりません。
強み
- 支配的戦略の真実性:入札者は真の評価額を入札することで余剰を最大化する
- 配分効率的:総余剰を最大化するように資源を配分する
- 一般性:任意の価値構造を持つ複雑な複数品目シナリオに適用可能
- 単純性:メカニズム設計の原理は明確で理論的にエレガント
応用
- スペクトルオークション:通信会社への無線スペクトルの配分において、真実の評価額をインセンティブ付ける
- オンライン広告:Googleの広告オークションは、入札者の価値に基づいた広告枠の配分においてVCGの要素を組み合わせている
- 調達:政府および民間の調達において、逆VCGオークションを使用して競争力のある価格で物品を取得する
- 腎臓交換プログラム:適合性の真実の開示をインセンティブ付けながら、ドナーとレシピエントをマッチングする
使い方
使い方
すべての参加者から、他の参加者に情報を開示することなく、密封入札または評価額を要求する。
総余剰(すべての参加者の評価額の合計)を最大化する結果を選択することにより、効率的な配分を見つける。
各参加者の支払いを、彼らが他者に課す損害、すなわちその参加者が存在しない場合に他者が得たであろう額に等しいと決定する。
他の参加者の真実の報告が与えられた場合に、どの参加者も自身の評価額を偽って報告することによって余剰を増やすことができないことを確認する。
よくある落とし穴
- 複雑な配分問題に対する計算上の実行可能性を仮定している。効率的な配分の発見は、組合せ入札に対してNP困難である
- VCG を第一価格入札と混同している。VCG は入札に基づく価格設定ではなく、利得に基づく価格設定を使用する
- VCG は評価額の真実性を促進するが、他の戦略的側面(参加、共謀)は促進しないことを無視している
- 効率性は局所的ではなく全体的であることを忘れている。入札が真の評価額を反映しない場合、配分誤りが発生する
よくある質問
VCGメカニズムは単一品目オークションでVickrey価格(第二価格)を請求するのはなぜか?
単一品目オークションでは、最高入札者が課す外部性は、第二最高入札者が獲得したであろう額、すなわち第二最高入札額に等しい。この価格は真実性を保証しつつ、落札者の余剰を最大化する。
VCGメカニズムはいつ収益最大化にならないのか?
VCGは収益最大化よりも配分効率と真実性を優先する。場合によっては赤字を生じる。第一価格オークションはより高い収益を生む可能性があるが、それは非真実な入札の代償を伴う。
VCGは多数の品目を持つ組合せ入札をどのように扱うか?
VCGは総余剰を最大化するようにバンドルを配分するが、最適な配分を計算することはNP困難である。実用的な実装では、近似アルゴリズムを使用するか、許容される入札の複雑さを制限する(例:バンドルサイズの制限)。