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

メカニズム設計において、ヴィックリー・クラーク・グローブス（VCG）メカニズムは、金銭移転が利用可能な場合に社会的に最適な解を達成するための、汎用的な真実メカニズムである。これは、ヴィックリー・クラーク・グローブスオークションを、複数の可能な結果から任意の結果を選択できる、社会選択のための汎用メカニズムへと一般化したものである。 ^{[1] : 216–233}しかしながら、VCGメカニズムには、共謀に対する脆弱性や、参加者が入札額を支払わない問題など、公共財問題を完全に解決することを妨げるいくつかの問題も存在する。

表記

考えられる結果はいくつかあります。 ${\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ゲームとなります。プレイヤーは望む結果を得て、その利益よりも少ない金額を支払います。つまり、プレイヤーは純利益を維持し、メカニズムは純支払額を得ることになります。

加重VCGメカニズム

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

${\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}$

アプリケーション

オークション

ヴィックリー・クラーク・グローブス・オークションは、VCGメカニズムを財の販売問題に応用した具体的な例です。ここでは、エージェントへのあらゆる可能なアイテムの割り当ての集合が となります。各エージェントは、各アイテムの束に個別の金銭的価値を割り当て、すべてのエージェントの価値の合計を最大化することが目標となります。 ${\displaystyle X}$

よく知られている特殊なケースは、ヴィックリーオークション、または密封された2番目に高い入札オークションです。ここでは、アイテムは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 Outcome}$ ${\displaystyle p_{1},\dots ,p_{n}}$
• 同じ機能を異なる支払い機能で実装する別の真実のメカニズムがあります。${\displaystyle Outcome}$ ${\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, chap.11}

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

参照

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

参考文献

1. ヴァジラニ、ヴィジェイ V. ;ニサン, ノーム;ティム・ラフガーデン;タルドス、エヴァ(2007)。アルゴリズムゲーム理論(PDF)。ケンブリッジ、英国: Cambridge University Press。ISBN 0-521-87282-0。
2. Avrim Blum (2013年2月28日). 「アルゴリズム、ゲーム、ネットワーク - 講義14」(PDF) . 2015年12月28日閲覧。
3. ニサン, ノアム; ロネン, アミール (2001). 「アルゴリズム的メカニズム設計」.ゲームと経済行動. 35 ( 1–2 ): 166– 196. CiteSeerX 10.1.1.16.7473 . doi :10.1006/game.1999.0790.