查看“︁维克里-克拉克-格罗夫斯机制”︁的源代码

'''维克里-克拉克-格罗夫斯机制'''（{{lang-en|Vickrey–Clarke–Groves mechanism}}）简称'''VCG机制'''，是[[机制设计]]中实现社会最优解的通用真实机制，该机制是[[维克里-克拉克-格罗夫斯拍卖]]的泛化。VCG拍卖的任务只是在一群人中分配物品，VCG机制比VCG拍卖更具有普适性，它能用于在可行结果的集合中选择任何结果。<ref name=AGT07>{{cite book
 | last1 = Vazirani | first1 = Vijay V. | author1-link = Vijay Vazirani
 | last2 = Nisan | first2 = Noam | author2-link = Noam Nisan
 | last3 = Roughgarden | first3 = Tim  | author3-link = Tim Roughgarden
 | last4 = Tardos | first4 = Éva | author4-link = Éva Tardos
 | isbn = 0-521-87282-0
 | location = Cambridge, UK
 | publisher = Cambridge University Press
 | title = Algorithmic Game Theory
 | url = http://www.cs.cmu.edu/~sandholm/cs15-892F13/algorithmic-game-theory.pdf
 | year = 2007
 | chapter = {{{chapter|}}}
}}</ref>{{rp|216–233}}
==表示符号==
<math>X</math>表示所有可行解的集合。

有<math>n</math>个参与者，它们对每个结果有不同的估价。参与者<math>i</math>对结果估值的函数可以表示为：

: <math>v_i : X \longrightarrow R_+</math>

该函数用金钱表示了代理人对每一种结果的估值。

假设参与者具有拟线性效用函数；这意味着，如果结果是<math>x</math>，加上参与者收到的报酬<math>p_i</math>（如果是代价则为负），则参与者<math>i</math>的总效用为：

: <math>u_i := v_i(x) + p_i</math>

我们的目标是选择一个结果，使价值的总和最大化，即：

: <math>x^{opt}(v) = \arg\max_{x\in X} \sum_{i=1}^n v_i(x) </math>

换句话说，我们的社会选择函数完全是基于[[功利主义]]的。
==解族==
VCG族是一个实现功利福利函数的机制族。在VCG族中，有一种典型的机制是这样工作的：

1.该机制需要参与者提供它们的估值函数，比如说每个参与者<math>i</math>都需要提供<math>v_i(x)</math>，<math>x</math>是每一个选择。

2.根据参与者所提供的估值，<math>v</math>，用公式<math>x^* = x^{opt}(v)</math>求最佳解。

3.该机制给每个参与者<math>i</math>一笔等于其他参与者总估值的钱：
: <math>p_i := \sum_{j\neq i} v_j(x^*)</math>

4该机制再给每个参与者<math>i</math>一笔基于任意函数<math>h_i</math>和其他参与者估值的钱：
: <math>p_i += h_i(v_{-i})</math>
其中<math>v_{-i} = (v_1, \dots, v_{i-1}, v_{i+1}, \dots, v_n)</math>，任意函数<math>h_i</math>是一个只依赖于对其他参与者的估值的函数。
== 真实性 ==
所有的VCG机制都是真实机制，也就是说参与者在这类机制中会选择给出真实的估价。

== 克拉克枢轴规则 ==
函数<math>h_i</math>是该机制的参数。<math>h_i</math>的每一个选择都会在VCG解族中产生不同的机制。

我们可以举这样一个例子：
: <math>h_i(v_{-i}) = 0</math>
但是这样一来我们需要付钱给参与竞拍的人，我们原本的计划是从竞拍者那里收钱。

经过调整后的函数是：
: <math>h_i(v_{-i}) = - \max_{x \in X} \sum_{j \neq i} v_j(x)</math>
这就是所谓的克拉克枢轴规则，在这一规则之下，竞拍者<math>i</math>所需付的钱是：
::（竞拍者<math>i</math>不在时拍卖产生的社会总福利）-（竞拍者<math>i</math>在时拍其他人的社会福利之和）
这就是竞拍者<math>i</math>所产生的[[外部性]]。<ref>{{cite web | url=https://www.cs.cmu.edu/~arielpro/15896/docs/notes14.pdf | title=Algorithms, Games, and Networks - Lecture 14 | date=2013-02-28 | access-date=2015-12-28 | author=Avrim Blum | archive-date=2022-03-15 | archive-url=https://web.archive.org/web/20220315201110/http://www.cs.cmu.edu/~arielpro/15896/docs/notes14.pdf }}</ref>

==参考文献==
{{reflist}}

[[Category:机制设计]]