维克里-克拉克-格罗夫斯机制

维克里-克拉克-格罗夫斯机制（）简称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所产生的外部性。

参考文献