跳转到内容

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

维基百科,自由的百科全书

维克里-克拉克-格罗夫斯机制(英語: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).