ヴィックリー・クラーク・グローブス機構

メカニズム設計において、ヴィックリー・クラーク・グローブス（VCG）メカニズムは、社会的に最適な解決策を達成するための一般的な真実のメカニズムです。これは、ヴィックリー・クラーク・グローブスオークションの一般化です。VCGオークションは、アイテムを人々の間で分配するという特定のタスクを実行します。VCGメカニズムはより一般的で、一連の可能な結果から任意の結果を選択するために使用できます。^{[1] ：216〜233}

考えられる結果はいくつかあります。 ${\displaystyle X}$

エージェントにはそれぞれ結果の評価のセットがあります。エージェントの評価は関数として表されます。 ${\displaystyle n}$${\displaystyle i}$

${\displaystyle v_{i}:X\to \mathbb {R} _{+}}$

これは、各選択肢の価値を金銭的に表したものです。

エージェントは準線形効用関数を持つと仮定します。つまり、結果が であり、さらにエージェントが支払い（正または負）を受け取る場合、エージェントの総効用は次のようになります。 ${\displaystyle x}$${\displaystyle p_{i}}$${\displaystyle i}$

${\displaystyle u_{i}:=v_{i}(x)+p_{i}}$

私たちの目標は、値の合計を最大化する結果を選択することです。

${\displaystyle x^{opt}(v)=\arg \max _{x\in X}\sum _{i=1}^{n}v_{i}(x)}$

言い換えれば、私たちの社会的選択機能は功利主義的です。

VCG ファミリは、功利主義的な福祉機能を実装するメカニズムのファミリです。VCG ファミリの典型的なメカニズムは次のように動作します。

1. エージェントに価値関数を報告するよう求めます。つまり、各エージェントは各オプションについて報告する必要があります。 ${\displaystyle i}$${\displaystyle v_{i}(x)}$${\displaystyle x}$

2. エージェントのレポートベクトルに基づいて、上記のように計算します。 ${\displaystyle v}$${\displaystyle x^{*}=x^{opt}(v)}$

3. 各エージェントに、他のエージェントの合計価値に等しい金額を支払います。 ${\displaystyle i}$

${\displaystyle p_{i}:=\sum _{j\neq i}v_{j}(x^{*})}$

4. 各エージェントに、他のエージェントの価値の任意の関数に基づいて追加の金額 を支払います。${\displaystyle i}$

${\displaystyle p_{i}+h_{i}(v_{-i})}$

ここで 、つまりは他のエージェントの評価のみに依存する関数です。 ${\displaystyle v_{-i}=(v_{1},\dots ,v_{i-1},v_{i+1},\dots ,v_{n})}$${\displaystyle h_{i}}$

VCG ファミリーのすべてのメカニズムは真実のメカニズム、つまり、真の評価額で入札することが優位な戦略となるメカニズムです。

秘訣はステップ 3 にあります。エージェントには他のエージェントの合計価値が支払われます。したがって、エージェント自身の価値と合わせると、エージェントの合計福祉は社会の合計福祉とまったく同じになります。したがって、エージェントのインセンティブは社会のインセンティブと一致し、エージェントはメカニズムが目標を達成できるように誠実であるよう動機付けられます。

ステップ 4 の関数は、他のエージェントの宣言にのみ依存するため、エージェントのインセンティブには影響しません。 ${\displaystyle h_{i}}$

関数はメカニズムのパラメータです。 を選択するたびに、VCG ファミリーの異なるメカニズムが生成されます。 ${\displaystyle h_{i}}$${\displaystyle h_{i}}$

たとえば、次のようなことが考えられます。

${\displaystyle h_{i}(v_{-i})=0}$、

しかし、オークションに参加するために実際にプレイヤーにお金を払わなければなりません。私たちはむしろ、プレイヤーがメカニズムにお金を払ってくれることを望んでいます。

代替関数は次のとおりです。

${\displaystyle h_{i}(v_{-i})=-\max _{x\in X}\sum _{j\neq i}v_{j}(x)}$

これはクラーク ピボット ルールと呼ばれます。クラーク ピボット ルールでは、プレイヤーが支払う合計金額は次のようになります。

(不在の場合の他者の社会福祉) - (存在する場合の他者の社会福祉)。${\displaystyle i}$${\displaystyle i}$

これはまさにプレイヤーの外部性である。^[2]${\displaystyle i}$

すべてのエージェントの評価が弱正の場合、クラーク ピボット ルールには 2 つの重要な特性があります。

• 個人的合理性: 各プレイヤーiについて。これは、オークションに参加することですべてのプレイヤーが正の効用を得ていることを意味します。誰も入札を強制されません。${\displaystyle v_{i}(x)+p_{i}\geq 0}$
• 正の転送なし: すべてのプレイヤーiに対して、。このメカニズムは入札者に何も支払う必要はありません。${\displaystyle p_{i}\leq 0}$

これにより、VCG メカニズムはwin-win ゲームになります。つまり、プレイヤーは望む結果を受け取り、その利益よりも少ない金額を支払います。したがって、プレイヤーは純利益を得て、メカニズムは純利益を得ます。

値の合計を最大化するのではなく、加重合計を最大化したい場合があります。

${\displaystyle x^{opt}(v)=\arg \max _{x\in X}\sum _{i=1}^{n}w_{i}v_{i}(x)}$

ここで、 はエージェントに割り当てられた重みです。 ${\displaystyle w_{i}}$${\displaystyle i}$

上記の VCG メカニズムは、ステップ 3 の価格関数を次のように変更することで簡単に一般化できます。

${\displaystyle p_{i}:={1 \over w_{i}}\sum _{j\neq i}w_{j}v_{j}(x^{*})}$

VCG メカニズムは、コストの合計を最小化すること (利益の合計を最大化することではなく) を目標とする状況に適応できます。コストは負の値として表すことができるため、コストの最小化は価値の最大化と同等になります。

ステップ 3 の支払いは負です。つまり、各エージェントは他のすべてのエージェントが負担した総コストを支払う必要があります。エージェントが参加するかどうかを自由に選択できる場合、その純支払いが負にならないようにする必要があります (この要件は、個々の合理性と呼ばれます)。この目的には、クラークのピボット ルールを使用できます。ステップ 4 では、各エージェントには、そのエージェントが参加しなかった場合に他のエージェントが負担したであろう総コストが支払われます。エージェントへの純支払いは、総コストの削減に対するそのエージェントの限界貢献です。 ${\displaystyle i}$${\displaystyle i}$${\displaystyle i}$

Vickrey–Clarke–Groves オークションは、福祉最大化のための VCG メカニズムの応用です。ここでは、エージェントへのアイテムの割り当ての可能なすべての集合です。各エージェントは、アイテムの各バンドルに個人的な金銭的価値を割り当て、すべてのエージェントの価値の合計を最大化することが目標です。 ${\displaystyle X}$

よく知られている特殊なケースは、ヴィックレイオークションです。ここでは、アイテムは 1 つだけであり、セットには、エージェントの 1 人にアイテムを販売するか、まったく販売しないかという、可能な結果が含まれます。ステップ 3 では、勝者エージェントには 0 が支払われ (他のエージェントの合計値が 0 であるため)、敗者は勝者の申告値に等しい支払いを受け取ります。ステップ 4 では、勝者は 2 番目に高い入札額 (勝者が参加しなかった場合の他のエージェントの合計値) を支払い、敗者は勝者の申告値 (勝者が参加しなかった場合の他のエージェントの合計値) を支払います。全体として、勝者は 2 番目に高い入札額を支払い、敗者は 0 を支払います。 ${\displaystyle X}$${\displaystyle n+1}$${\displaystyle n}$

VCG メカニズムはダブルオークションでも使用できます。これは、バンドル上の任意の価値関数を持つ組み合わせオークションを処理できるため、インセンティブ互換ダブルオークションの最も一般的な形式です。残念ながら、予算のバランスが取れていません。つまり、買い手が支払う合計金額は、売り手が受け取る合計金額よりも小さくなります。したがって、これを機能させるには、オークション主催者が取引を補助する必要があります。

政府は、あるプロジェクトを実施するかどうかを決定したい。プロジェクトの費用はCである。各国民は、プロジェクトから異なる価値を得る。すべての国民の価値の合計が費用を上回る場合、プロジェクトを実施すべきである。ここで、クラーク ピボット ルールを伴う VCG メカニズムは、国民がピボットである場合、つまり、申告がない場合の合計価値がC未満で、申告がある場合の合計価値がC を超える場合にのみ、そのプロジェクトに対してゼロ以外の税金を支払うことを意味する。この課税スキームはインセンティブと両立するが、これも予算の均衡が取れていない。つまり、徴収される税額の合計は通常C未満である。^{[1] : 221}

最速経路問題はコスト最小化問題です。^[3]目標は、グラフとしてモデル化された通信ネットワーク内の 2 点間でメッセージを送信することです。ネットワーク内の各コンピューターは、グラフ内のエッジとしてモデル化されます。コンピューターによって送信速度が異なるため、ネットワーク内の各エッジには、メッセージを送信するのにかかるミリ秒数に等しい数値コストがあります。私たちの目標は、できるだけ早くメッセージを送信することなので、総コストが最小のパスを見つけたいのです。

各コンピュータの送信時間 (各エッジのコスト) がわかっている場合は、最短経路問題を解くための標準アルゴリズムを使用できます。送信時間がわからない場合は、各コンピュータに送信時間を教えてもらう必要があります。しかし、コンピュータには利己的な利益があるため、真実を教えない可能性があります。たとえば、コンピュータは、メッセージで煩わされないように、送信時間が非常に長いと伝える場合があります。

この問題を解決するには、VCG メカニズムを使用できます。ここでは、すべての可能なパスのセットです。目標は、総コストが最小のパスを選択することです。 ${\displaystyle X}$${\displaystyle x\in X}$

エージェントの価値 は、メッセージに費やした時間のマイナスです。つまり、 の場合は負で、 の場合はゼロです。ステップ 3 の支払いは負です。つまり、各エージェントは、他のエージェントがメッセージに費やした合計時間を私たちに支払う必要があります (値は時間単位で測定されることに注意してください。コンピュータに時間単位で支払うことが可能であるか、時間をお金に換算する標準的な方法があると想定しています)。つまり、各エージェントは、自分の費やした時間と合わせて、メッセージが宛先に到達するのにかかった合計時間を実際に失うため、エージェントはメカニズムが最短の送信時間を達成するのを支援するインセンティブを得ます。 ${\displaystyle v_{i}(x)}$${\displaystyle i\in x}$${\displaystyle i\notin x}$

クラークのピボット ルールを使用すると、メカニズムを個別に合理的にすることができます。つまり、各エージェントはコストを支払った後、私たちから正の支払いを受け取ります。これは、エージェントが存在しなかった場合にメッセージが宛先に到着するまでにかかった時間に相当します。明らかに、この時間はエージェントが存在する場合に要する時間よりも弱いほど長いため、各エージェントの純利益は弱いほど正です。直感的に、各エージェントは送信への限界貢献に応じて支払いを受けます。

他のグラフ問題も同様の方法で解くことができます。例えば、最小全域木や最大マッチングなどです。同様の解決策は、各エージェントがエッジのサブセットを保持するより一般的なケースにも適用されます。^[3]

VCG メカニズムが最適ではない近似値を提供する別の例については、「真実のジョブ スケジューリング」を参照してください。

VCG メカニズムは、値の加重合計を最大化する関数 (アフィン最大化関数とも呼ばれる) である功利主義的な社会的選択関数を実装します。ロバーツの定理は、次のことを証明します。

• エージェントの評価関数は制限されない（各エージェントは価値関数として から までの任意の関数を持つことができる）、そして -${\displaystyle X}$${\displaystyle \mathbb {R} }$
• 少なくとも3つの異なる結果が考えられます（そして、少なくとも3つの異なる結果が起こる可能性があります）。${\displaystyle |X|\geq 3}$${\displaystyle X}$

そうすると、重み付けされた功利主義機能のみが実装可能となる。^{[1] : 228、第12章} したがって、制限のない評価では、VCGメカニズムによって実装される社会的選択機能だけが、真実に実装できる機能となる。

さらに、VCGメカニズムの価格関数は次の意味でも独特である。^{[1] : 230–231}もし:

• エージェントの評価の領域は連結された集合である（特に、エージェントは整数の好みだけでなく実数値の好みを持つことができる）。
• 特定の支払い機能で特定の機能を実装する真実のメカニズムがあります。${\displaystyle 結果}$${\displaystyle p_{1},\dots ,p_{n}}$
• 異なる支払い機能で同じ機能を実装する別の真実のメカニズムがあります。${\displaystyle 結果}$${\displaystyle p'_{1},\dots ,p'_{n}}$

すると、すべての に対して、 となる関数が存在する: ${\displaystyle h_{1},\dots ,h_{n}}$${\displaystyle i}$

${\displaystyle p'_{i}(v_{i},v_{-i})=p_{i}(v_{i},v_{-i})+h_{i}(v_{-i})}$

つまり、2 つのメカニズムの価格関数は、エージェントの評価に依存せず(他のエージェントの評価のみに依存する) 関数によってのみ異なります。${\displaystyle v_{i}}$

これは、VCG メカニズムが功利主義的な社会福祉 を最大化する唯一の真実のメカニズムであることを意味します。

VCGメカニズムは、エージェントの報告に基づいて最適な結果を計算する（上記ステップ2）。場合によっては、この計算は計算上困難である。たとえば、組み合わせオークションでは、最適な割り当てを計算することはNP困難である。^{[1] ：270–273、第11章}

最適化問題には近似アルゴリズムが存在することもありますが、そのような近似を使用するとメカニズムが不正確になる可能性があります。^[3]

• アルゴリズムによるメカニズム設計
• インセンティブの互換性
• 二次投票