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

维克里-克拉克-格罗夫斯机制(英语:Vickrey–Clarke–Groves mechanism)简称VCG机制,是机制设计中实现社会最优解的通用真实机制,该机制是维克里-克拉克-格罗夫斯拍卖的泛化。VCG拍卖的任务只是在一群人中分配物品,VCG机制比VCG拍卖更具有普适性,它能用于在可行结果的集合中选择任何结果。[1]:216–233

表示符号

编辑

 表示所有可行解的集合。

 个参与者,它们对每个结果有不同的估价。参与者 对结果估值的函数可以表示为:

 

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

假设参与者具有拟线性效用函数;这意味着,如果结果是 ,加上参与者收到的报酬 (如果是代价则为负),则参与者 的总效用为:

 

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

 

换句话说,我们的社会选择函数完全是基于功利主义的。

解族

编辑

VCG族是一个实现功利福利函数的机制族。在VCG族中,有一种典型的机制是这样工作的:

1.该机制需要参与者提供它们的估值函数,比如说每个参与者 都需要提供  是每一个选择。

2.根据参与者所提供的估值, ,用公式 求最佳解。

3.该机制给每个参与者 一笔等于其他参与者总估值的钱:

 

4该机制再给每个参与者 一笔基于任意函数 和其他参与者估值的钱:

 

其中 ,任意函数 是一个只依赖于对其他参与者的估值的函数。

真实性

编辑

所有的VCG机制都是真实机制,也就是说参与者在这类机制中会选择给出真实的估价。

克拉克枢轴规则

编辑

函数 是该机制的参数。 的每一个选择都会在VCG解族中产生不同的机制。

我们可以举这样一个例子:

 

但是这样一来我们需要付钱给参与竞拍的人,我们原本的计划是从竞拍者那里收钱。

经过调整后的函数是:

 

这就是所谓的克拉克枢轴规则,在这一规则之下,竞拍者 所需付的钱是:

(竞拍者 不在时拍卖产生的社会总福利)-(竞拍者 在时拍其他人的社会福利之和)

这就是竞拍者 所产生的外部性[2]

参考文献

编辑
  1. ^ Vazirani, Vijay V.; Nisan, Noam; Roughgarden, Tim; Tardos, Éva. Algorithmic Game Theory (PDF). Cambridge, UK: Cambridge University Press. 2007. ISBN 0-521-87282-0. 
  2. ^ Avrim Blum. Algorithms, Games, and Networks - Lecture 14 (PDF). 2013-02-28 [2015-12-28]. (原始内容 (PDF)存档于2022-03-15).