維克里-克拉克-格羅夫斯機制

維克里-克拉克-格羅夫斯機制（英語：Vickrey–Clarke–Groves mechanism）簡稱VCG機制，是機制設計中實現社會最優解的通用真實機制，該機制是維克里-克拉克-格羅夫斯拍賣的泛化。VCG拍賣的任務只是在一群人中分配物品，VCG機制比VCG拍賣更具有普適性，它能用於在可行結果的集合中選擇任何結果。

表示符號

$X$表示所有可行解的集合。

有$n$個參與者，它們對每個結果有不同的估價。參與者$i$對結果估值的函數可以表示為：

$v_{i}:X\longrightarrow R_{+}$

該函數用金錢表示了代理人對每一種結果的估值。

假設參與者具有擬線性效用函數；這意味著，如果結果是$x$，加上參與者收到的報酬$p_{i}$（如果是代價則為負），則參與者$i$的總效用為：

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

我們的目標是選擇一個結果，使價值的總和最大化，即：

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

換句話說，我們的社會選擇函數完全是基於功利主義的。

解族

VCG族是一個實現功利福利函數的機制族。在VCG族中，有一種典型的機制是這樣工作的：

1.該機制需要參與者提供它們的估值函數，比如說每個參與者$i$都需要提供$v_{i}(x)$，$x$是每一個選擇。

2.根據參與者所提供的估值，$v$，用公式$x^{*}=x^{opt}(v)$求最佳解。

3.該機制給每個參與者$i$一筆等於其他參與者總估值的錢：

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

4該機制再給每個參與者$i$一筆基於任意函數$h_{i}$和其他參與者估值的錢：

$p_{i}+=h_{i}(v_{-i})$

其中$v_{-i}=(v_{1},\dots ,v_{i-1},v_{i+1},\dots ,v_{n})$，任意函數$h_{i}$是一個只依賴於對其他參與者的估值的函數。

真實性

所有的VCG機制都是真實機制，也就是說參與者在這類機制中會選擇給出真實的估價。

克拉克樞軸規則

函數$h_{i}$是該機制的參數。$h_{i}$的每一個選擇都會在VCG解族中產生不同的機制。

我們可以舉這樣一個例子：

$h_{i}(v_{-i})=0$

但是這樣一來我們需要付錢給參與競拍的人，我們原本的計劃是從競拍者那裡收錢。

經過調整後的函數是：

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

這就是所謂的克拉克樞軸規則，在這一規則之下，競拍者$i$所需付的錢是：

（競拍者$i$不在時拍賣產生的社會總福利）-（競拍者$i$在時拍其他人的社會福利之和）

這就是競拍者$i$所產生的外部性。