维克瑞-克拉克一格 罗夫斯机制 维克瑞-克拉克一格罗夫斯机制（Vickrey-Clarke-Grovesmechanisms，VCG）是一类被广 泛研究的伴随货币的机制。这类机制是在放松吉伯德一萨特思韦特定理其中一个必要条件的 基础上得到的。VCG机制使用了限制性较强的环境，即拟线性环境（quasilinearenviron- ment)，在这种情形下，任何社会选择函数都不是独裁的，而且机制可以漂亮地分解为配置 规则和支付规则。另外，事后效率性质可以分解为两个性质：一是配置效率（allocativeeffi- ciency，配置规则的性质）；二是严格预算平衡（strictbudgetbalance，支付规则的性质）。 维克瑞-克拉克-格罗夫斯机制 VCG机制是合意的，因为它们满足配置效率以及优势策略激励相容。本章首先讨论拟线性环 境，然后讨论格罗夫斯机制（Grovesmechanisms，这是VCG机制类中最具一般性的机制）。 接下来，我们讨论克拉克机制（Clarkemechanism，也称关键人机制），维克瑞机制是克拉克 机制的一种特殊情形。我们还用一些例子说明VCG机制。 18.1.拟线性环境 在拟线性环境中，结果x∈X是一个向量形式，r=（k，t，，t），其中k是集 合K的元素，集合K称为项目选择集（setofprojectchoices）或项目配置集（setof projectallocations）。通常假设集合K为有限的。t∈R项代表转移给智能体i的钱数。 如果t>0，按照惯例，这表示智能体i得到了t：的钱数；如果t<0，这表示智能体i 支付t的钱数。需要注意，任一结果都被分成两个部分：一是配置部分，即k；二 是支付部分，即t，，tn。因此，备选方案集X为 X={（k,t1,,tn):kEK;t;ER；ViEN} 通常，在我们考察的系统中，智能体没有外部融资渠道，而且我们隐含地假设：

这个条件称为弱预算平衡（weakbudgetbalance）。在这个条件下，备选方案集变为 X={(k,ti,..,tn):k∈K;ti∈R；Vi∈N;∑t;<0} iEN 在拟线性环境下，社会选择函数f：O→X的结果采取如下形式：f（0)=（k（0)， t（0)，"，t（0））。其中，对于每个θ∈，我们有k（θ）∈K。如果弱预算平衡得以满 足，我们还有t:（0)≤0，θ∈。 注释我们说明符号k和k（θ）以及t：和t：（0）的用法。如果类型组θ是隐含但又 是明确的，我们使用k和t；。然而，当0必须出现时，我们使用k（θ）和t；（0）。注意， k（·）是一个从到K的映射，而t；（·）是一个从到R的映射，i=1，，n。 对于这种环境下的直接显示机制9=（（O）∈N，f（·）），智能体i的效用函数取拟 线性形式 ui（x，0:）=ui（（k，t1，",tn），0;）=u;（k，0;)+mi+t; 其中，m:是智能体i的初始货币票赋，函数（·，·）称为智能体i的价值函数或评 价函数（valuationfunction）。 回顾我们对机制设计环境的讨论（第16章）：我们假设效用函数u（·）是共同知 识。在拟线性环境下，这意味着对于任何智能体i的任何给定类型0，社会计划者和每 个其他智能体j能设法知道函数u（·，0:）、t（0）以及m。 拟线性环境的直接例子包括我们以前讨论过的很多例子，例如第一价格密封拍卖和第 二价格密封拍卖（例14.4）、双边交易（例14.6）以及公共项目问题（例14.7），等等。 在拟线性环境下，我们可以定义社会选择函数的两个重要性质，即配置效率和预算平衡。 口配置效率 配置效率是拟线性环境下配置函数k（·）的性质。 定义18.1（配置效率）给定社会选择函数f（·）=（k（·），t（·），，t（·））， 如果对于每个0EO，k（0）满足下列条件 k(θ)∈argmax U;(k,0:) KEK i=1 或等价地满足 U;(k（0）,0:)=max 0;(k,0;) kEK=1 那么我们说社会选择函数f（·）有配置效率（allocativeefficiency，AE）。 上面的定义意味着对于每个0EO，配置k（9）使得智能体的价值之和最大。换句话 说，每个配置都是价值最大化的配置，或者说，商品配置给对该商品评价最高的智能 体。这个性质对于任何社会选择函数来说都是极其合意的。通常，我们用符号k*（·） 表示满足式（18.1）的函数k（·），用来表明它使得所有配置的总评价最大。

注释上面的定义隐含地假设对于任何给定的0E0，函数 u;(·,0）:K→R在 i=1 集合K上实现了一个最大值。 例18.1（公共项目问题）在某公共项目问题中，N={1，2}。令公共项目的成本 为50元。令两个智能体的类型集为=2={20，60}。每个智能体要么有低的支付意 愿（20元），要么有高的支付意愿（60元）。令项目选择集为K={0，1），其中1表示 项目上马，0表示项目不上马。 假设如果K=1，那么这两个智能体均摊项目成本，即每个人支付25元。如果 K=0，由于项目不上马，智能体不需要支付钱。考虑价值函数（评价函数） u;（k，0;)=k（0;-25) 这表示，若k=0，则智能体i得到零价值；若k=1，则智能体i得到的价值是他的支付 意愿减去25。定义下列配置函数： k（θ，02）=0若θ=02=20 =1 其他情形 这表示项目上马仅当至少其中一个智能体有高支付意愿。这个社会选择函数是有配置效 率的，这一点可从表18一1看出。表18—1给出了智能体在不同类型组情形下得到的价 值，其中第二列给出了k的实际值。口 表18-1 当v（k，0:）=k（0一25）时，各个不同类型组得到的价值 第 （k，0) （k，02) （k，θ） 2（k，02) (0，0) k 当k=0时 当k=0时 当k=1时 当k=1时 (20，20) -5 -5 维克瑞|克拉克|格罗夫斯切 (20，60) -5 (60，20) -5 (60，60) 例18.2（没有配置效率的社会选择函数）令评价函数的定义为 v;（k，0;）=k0i=1,2 对于上面的函数，例18.1中的配置函数k没有配置效率。各个类型组下的价值如表 18—2所示。 机制 表18-2 当v（k，0:）=k0：时，各个不同类型组得到的价值 （k，01) 2（k，02) （k，0) （k，02) (0，02) k 当k=0时 当k=0时 当k=1时 当k=1时 (20，20) (20,60) (60，20) (60，60) 如果类型组为（20，20），配置为k=0，因此配置的总价值为0。然而，当配置为 k=1时，总价值为40。这立即表明k没有配置效率。口

口预算平衡 预算平衡是拟线性环境下支付函数t（·），，t（·）的性质。 定义18.2（预算平衡）给定社会选择函数f（·）=（k（·），t（·），，t（·））， 如果对于每个0E⊙，t（0），，t（0）满足下列条件 ∑t;(θ)=0 (18.1) iEN 那么，我们说社会选择函数f（·）是预算平衡的（budgetbalanced，BB）。 按照惯例，这个性质称为强预算平衡（strongbudgetbalance，SBB）。类似地，弱 预算平衡（weakbudgetbalance，WBB）是指

() iEN 在本书中，我们所说的预算平衡（BB）是指强预算平衡。 预算平衡保证了总收入等于总支出。这表示系统是封闭的，没有盈余也没有亏损。 弱预算平衡性质表示总支出大于或等于总收入。假设我们有一个双边交易系统，这个系 统有一组卖者和一组买者，买者用钱换卖者的物。假设t（θ）是智能体i（i=1，2，"， n）在其类型为0时得到的钱数。这里有三种可能性。 严格预算平衡 严格预算平衡或称强预算平衡，是指所有智能体在所有类型组中的所有货币转移之 博奔论与机制设计 和等于零。这表示智能体得到的钱数之和等于智能体支付的钱数之和。这是一个合意的 情形，因为在这种情形下，没有盈余也没有亏损。这样的交易制度能独立运行（事实 上，它以完全自治的方式运行）。 弱预算平衡 弱预算平衡是指所有智能体在所有类型组中的所有货币转移之和小于或等于零。这 表示智能体支付的钱数之和不大于他们得到的钱数之和。此时，这个系统有盈余。这个 盈余可由运营该系统（交易制度）的市场创立者或经纪人获得。 预算不平衡 预算不平衡指至少在一个类型组下，智能体支付的钱数之和严格小于智能体得到的 钱数之和。因此，这个系统有亏损。在这种情形下，为了维持预算平衡，必须有外部机 构弥补这个亏损。这是我们试图避开的情形。一般来说，预算平衡性质必须根据具体制 度架构进行详细解释。 注释在本章，我们假设可行结果集为 X={(k,t,,tn):k∈K;t;∈R;Vi∈N;∑ti<O} iEN 因此，本章讨论的所有社会选择函数都是弱预算平衡的。在下一章（第19章），我们讨 论的社会选择函数未必是弱预算平衡的。 口拟线性的重要结果 我们现在证明拟线性的两个结果：

·在拟线性环境下不存在独裁的社会选择函数。 ·在拟线性环境下，事后效率等价于有预算平衡的配置效率。 第一个引理给出了拟线性环境下关于社会选择函数的一个重要事实。这个事实让我 们能够绕开吉伯德一萨特思韦特定理（定理17.1）中条件（2）造成的不可能情形。 引理18.1在拟线性环境下，任何含有至少两个智能体的社会选择函数都不是独 裁的。 证明：反证法。假设在拟线性环境下，社会选择函数f（·）是独裁的。这意味着 存在一个独裁者比如dEN，使得对于每个0EO，我们有 ua(f(0),0a)≥ua(x,0a)xEX 由于环境是拟线性的，我们有 ua(f(0),0a)=Ua(k(θ),0a)+ta(θ) 由于我们当前假设社会选择函数是弱预算平衡的（参见前面的注释），因此给定， 这里只有两种可能：智能体的支付之和要么等于零，要么小于零。考虑下列备选方案 rEX: (k(θ）,(t;=t；(0）)idta=ta(0)-∑t;(0）):t；(0）<0 (k（0),（t;=t;(0）)i≠djta=ta(0)+e,t;=t;(0)—∈):∑t;(θ)=0 第 18章 其中：e>0是任一实数，j是独裁者d之外的任何智能体。容易验证，对于上面的结果 维克瑞|克拉克|格罗夫斯机制 x，我们有ua（x，θa）>ua（f（θ），θa），这与我们一开始的假设（d是一个独裁者）矛 盾。 我们再次强调，配置效率是配置函数的性质，而预算平衡是支付函数的性质。如果 环境是拟线性的，那么这两个性质一起等价于事后效率。下面的引理说明了这个结果。 引理18.2在拟线性环境下，社会选择函数f（·）=（k（·），t（·），，t（·）） 有事后效率，当且仅当f（·）有配置效率而且是预算平衡的。 证明：假设f（·）=（k（·），t（·），，t（·））有配置效率而且是预算平衡的。 这意味着对于任何9E?，我们有 u；(f(0)0)=u;(k(0）,0)+∑t:(0) 0;(k(0),0)+0 ti；Vx=（k,t,,tn）∈X [= ∑ui(x,0;);Vx=(k,t,,tn)∈X 也就是说，如果社会选择函数有配置效率而且是预算平衡的，那么对于智能体的任何类

型组0E0，社会选择函数选定的结果将是使所有智能体在任何配置下的总效用最大的 那个结果。这自动意味着社会选择函数有事后效率（参见命题16.1）。 为了证明另外一个方向上的结论，我们分两步走。第一步，证明如果f（·）没有 配置效率，那么它不可能有事后效率；第二步，证明如果f（·）不是预算平衡的，那 么它不可能有事后效率。这两个事实一起意味着如果f（·）有事后效率，那么它必定 有配置效率而且是预算平衡的，这样我们就完成了该引理的证明。 第一步，假设f（·）没有配置效率。这意味着存在0EO与k∈K使得 ∑u;(k,0)> U;(k（0),0;) i=1 i=1 这意味着至少存在一个智能体j使得（k，0)>u（k（θ)，θ）。现在考虑备选方案x： （k，（t=t;(0)+u;(k(0）0;)-u;(k,0;))it;=t;(0)+u;(k(0)，0;)-u;(k，0;)+∈) 其中e>0。容易验证我们有u（x，0）=u（f（θ），θ;），Vi≠j以及u;（x，0;）>u;（f（θ)， 0），这意味着f（·）没有事后效率。 第二步，假设f（·）不是预算平衡的。这表示存在着至少一个智能体j使得 t;（0)<0。我们考虑下面的备选方案x： x=（k’，（t;=t;（0））i≠i，t;=t;（0）+e) 容易验证对于上面的备选方案x，我们有 博 奔论与机制沿 u;（x，0)=u;（f（0)，0;)，Vi≠j以及u;（x，0;)>u;（f（0），0;) 这意味着f（·）没有事后效率。这样，我们就完成了该引理的证明。■ 根据引理18.1可知，社会计划者不需要担心拟线性环境下社会选择函数存在独裁 者问题，他只需要考察是否存在同时满足事后效率（EPE）与优势策略激励相容 设计 （DSIC）的社会选择函数即可。另外，根据引理18.2可知，社会计划者可寻找满足配 置效率（AE）、强预算平衡（SBB）和优势策略激励相容（DSIC）的社会选择函数。再 一次地，问题出现了：是否存在同时满足AE、SBB和DSIC的社会选择函数？我们在 下面几节讨论这个问题以及其他相关问题。 威廉·维克瑞（WilliamVickrey）是著名的维克瑞拍卖 的创造者，它被视为拍卖设计的重大突破。维克瑞在他的经 典论文《反投机、拍卖与竞争性的密封投标》（Counterspecu lation，Auctions，and Competitive Sealed Tenders;载于 《金融学》期刊，1961年）中证明：第二价格密封拍卖是优势 策略激励相容的。这个结果第一次说明博弈论在拍卖设计中 的价值。除了维克瑞拍卖之外，他还发现了收入等价理论的 早期版本，这是拍卖理论的一个重要结果。 维克瑞对拥挤定价也做出了开创性贡献，他将道路和服 务的定价视为对过度需求的一种自然管制方法。他的这一思想后来被运用到伦敦市的交

通实践中。维克瑞与詹姆斯·A.莫里斯（JamesA.Mirrlees）一起获得了1996年诺 贝尔经济学奖，因为他们对信息不对称下的激励理论作出了基础性的贡献。然而，在诺 贝尔奖公布三天之后，即1996年10月11日，维克瑞去世了。 维克瑞1914年6月21日出生于加拿大维多利亚市。他于1948年获得哥伦比亚大 学博士学位。他的博士论文《论累进税》（AgendaforProgressiveTaxation）被视为该 领域的开创性成果。维克瑞从1946年起就任教于哥伦比亚大学直到1982年退休。 爱德华·克拉克（EdwardClarke）是美联邦行政管理 和预算局（信息与管制事务局）的一名杰出的高级经济师， 这些部门主要从事交通管制事务。克拉克本科毕业于普林斯 顿大学，在芝加哥大学获得硕士（MBA）和博士（1978年） 学位。他先后在市/区（芝加哥）、州、联邦和国际部门从事 公共政策研究工作。 在公共经济学领域，他提出了公共项目选择的需求显示 机制；诺贝尔奖委员会在给维克瑞颁发诺奖时指出了这一点。克拉克的论文《公共物品 的多部分定价》（Multi-partPricingofPublicGoods，载于《公共选择》期刊，1971年） 是机制设计领域的一篇经典之作。在VCG机制中，克拉克机制是一种自然而流行的 方法。 在著名的VCG机制中，西奥多·格罗夫斯（Theodore 维克瑞-克拉克-格罗夫斯机制 Groves）机制最具一般性。在经典论文《团队激励》（In- centivesinTeams，载于《计量经济学》期刊，1973年） 中，他提出了一类满足配置效率和优势策略相容性的 机制。 格罗夫斯机制推广了克拉克机制（1971年提出），这又 推广了维克瑞拍卖（1961年提出）。格罗夫斯获得了加州大 学伯克利分校的经济学博士学位，他目前任教于加州大学圣 地亚哥分校。 18.2格罗夫斯机制 本节的主要结果是在拟线性环境下存在着同时满足配置效率和优势策略激励相容的 社会选择函数。它们一般被称为维克瑞-克拉克-格罗夫斯（VCG）机制。 VCG机制是以他们的发现者威廉姆·维克瑞（WilliamVickrey）、爱德华·克拉克 （EdwardClarke）以及西奥多·格罗夫斯（TheodoreGroves）的名字命名的。维克瑞

于1961年首先引人了著名的维克瑞拍卖（第二价格密封拍卖)1]。直到今天，维克瑞 拍卖在机制设计中仍有特殊位置。克拉克[2]与格罗夫斯[3]将维克瑞拍卖一般化，并且 在拟线性环境下定义了一大类优势策略激励相容机制。在拟线性机制中，迄今为止， VCG机制的使用最为广泛。原因不仅在于它们在数学上很优雅，更在于它们满足了现 实应用环境要求的很强的性质。 口格罗夫斯定理 在拟线性环境下，有配置效率的社会选择函数何时是优势策略相容的？下列著名结 果为这个问题提供了充分条件。我们将这个定理称为格罗夫斯定理。这个定理是机制设 计理论的里程碑之一。 定理18.1（格罗夫斯定理）令社会选择函数f（·）=（k*（·），t（·）， t（·））有配置效率，如果它满足下列支付结构［格罗夫斯支付（激励）规则]： t;(0，0-)=[∑o;(k*（0)，0;)]+h;(0-i）Vi=1,..,n (18.2) j≠i 其中h;：O-；→R是任意函数。那么f（·）是优势策略激励相容的。 证明：反证法。假设f（·）满足配置效率和格罗夫斯支付结构，但不是优势策略 激励相容的（DSIC)。这意味着f（·）不满足DSIC的下列必要充分条件： u;(f（0,0-i),0)≥u;（f（0,0-i),0i)0∈O,θEO,0-iEO-i,Vi∈N 博奔论与机制设 这意味着至少存在一个智能体使得对他来说上式不成立。令这个智能体为i。也就是说， 对于智能体i，对于某个0∈、0-∈-以及某个0∈， u;（f（0，0-i）,0;）>ui（f（0，0-）,0;) 设计 将上面的u表达式展开，可知：对于智能体i，存在着0∈、0∈、0-∈-使得 0;（k*（0，0-;）,0;)+t;（0，0-;)+m>0;（k*（0，0-;）,0;)+t;（0，0-i)+m 记住格罗夫斯支付结构： t;(0，0-i)=∑u;(k*(0;,0-i),0;)]+h;(0i) t;(00i)=[∑u;（k*（0，0-i),0;)]+h;(0-i） j#i 代人前面的展开式，可得 u(k（，0),0)+0;（k*（00),0;)>;(k*(00),0;)+0;(k(0，0),0;) 这意味着 u;(k*（00-i),0)> 0;（k*（0，0-;）,0:）

上式与f（·）有配置效率相矛盾。这样，我们就完成了证明。

下面是格罗夫斯定理的一些直接且有趣的含义。 注释给定智能体i≠i报告的类型0-，转移给智能体i的钱数仅取决于他通过项 目选择k*（0，0-）报告的类型0。 注释当智能体i的类型从0变为0时，他的货币转移的变化（即t（0， 0-）一t（0，0-：））等于相应项目选择变化对所有其他智能体的总评价的影响。也 就是说， t；(0，0-)-t;（0，0-;）=[u;(k*（0，0-i),0;)-u;（k*（0，0-i）,0;）] j#i 换句话说，转移给智能体i钱数的变化反映了他施加在其他智能体身上的外部性（ex ternality)。* 下面我们介绍格罗夫斯机制（GrovesMechanism），它源于格罗夫斯定理。所谓格 罗夫斯机制是一种直接显示机制，此时被实施的社会选择函数有配置效率而且满足格罗 夫斯支付规则。正式定义如下。 定义18.3（格罗夫斯机制）给定直接显示机制9=（（O）i∈N，f（·）），若该机制 中的f（·）=（k（·），t（·），，t（·））满足配置效率式（18.1）以及格罗夫斯支 付规则式（18.2），则9称为一个格罗夫斯机制。 在机制设计领域，格罗夫斯机制通常指维克瑞-克拉克-格罗夫斯（VCG）机制， 这是因为克拉克机制是格罗夫斯机制的一种特殊情形，而维克瑞机制文是克拉克机制的 一种特殊情形。稍后我们将讨论这个关系。 第 格罗夫斯定理为下列问题提供了充分条件：有配置效率的社会选择函数何时是优势 策略激励相容的（DSIC）。我们也对这个问题的必要条件感兴趣。下列定理，即格林一 章 拉丰第一特征定理（firstcharacterizationtheoremofGreen-Laffont）为此提供了必要条 维 件（GreenandLaffont[4]）。在这个定理中，我们令9表示所有可能函数f：K→R组成 克 的集合。 克 定理18.2（格林-拉丰第一特征定理）假设对于每个智能体iEN都有（v（·，0）： 拉 0∈O}=，也就是说，每个可能的评价函数f：K→R都对应着某个0∈O。于是，任 克 -格 何有配置效率的社会选择函数f（·）是优势策略激励相容的，当且仅当f（·）满足格 罗 罗夫斯支付规则（18.2）。 夫 注意，在上面的定理中，每个可能的函数f：K→R都对应着某个0∈O。在下列特征 斯 机 定理（GreenandLaffont4]）中，被换为，其中表示所有可能的连续函数f：K→R 制 组成的集合。 定理18.3（格林-拉丰第二特征定理）假设对于每个智能体iEN都有{v（·，0）： 0EO}=，也就是说，每个可能的连续评价函数f：K→R都对应着某个0E。于 是，任何有配置效率的社会选择函数f（·）是优势策略激励相容的，当且仅当f（·） 满足格罗夫斯支付规则式（18.2）。 移”等，但它们的意思是一样的，读者记住下面一点即可：xEX可正可负，t>0表示智能体i得到的钱数，t<0 表示智能体i支付的钱数。—译者注

18.3克拉克机制（关键人机制） 格罗夫斯机制出现于1973年。L3格罗夫斯机制的一种特殊情形是克拉克于1971年 提出的机制[2]，后者被称为克拉克机制（Clarkemechanism）或称关键人机制（pivotal mechanism）。克拉克机制在下列意义上是格罗夫斯机制的一种特殊情形：前者使用了 一种特殊形式的函数h（·）。在克拉克机制中，函数h（·）由下列关系给出： h;(0-)=-∑u;(k(0-i）,0;)θ-:∈0i,Vi=1,,n (18.3) j≠i 其中k（0-）∈K-是一个项目选择，当智能体i不出现时（即对于除了智能体i之外的 所有其他智能体来说），它是一个有配置效率的选择。这里，集合K-是智能体i不出 现时的所有可及项目选择构成的集合。正式地，k-：（0-：）必定满足下列条件： ∑u;(k(0-i),0;)≥∑u;(k,0;)Vk∈K; (18.4) j#i 将式（18.3）中h：（·）的值代人式（18.2），可得到克拉克机制下智能体i的货币 转移： t;(0)=[∑u;(k*（0），0;)]-[≥u;(k(0),0;)]Vi=1,.,n (18.5) 博奔论与机制设计 上面的支付规则有合意的解释：给定类型组0=（0，"，0），转移给智能体i的钱数 不出现时所有其他智能体在该有效率的配置中的总价值。克拉克支付规则的另外一种合 意解释如下。我们把t（θ）写为 t;（0i，0-i）=

;(k*（0）,0;)-v;(k*(0）,0:)-∑u;(k;(θ-i),0;) jEN = u;(k*（0),0;)-0;(k=(0-i),0;)—0;(k*（0），0;) jEN j#i 考察上式最后一行，前两项之差代表智能体i对系统的边际贡献。因此，克拉克机制为 每个参与分配的智能体提供了一个额外的激励，即该智能体对机制的边际贡献。这个额 外激励是（在优势策略意义上）诱导智能体如实报告的关键所在。 克拉克机制也称为关键人机制，这是因为每个参与分配的智能体在决定所有其他智 能体所得价值时扮演了关键人角色。 18.4-VCG机制的例子 VCG机制比较流行，原因在于它们在数学上很漂亮，而且有着合意的经济性质； 不仅如此，VCG还为社会计划者在设计机制的过程中提供了直观的视角。因此，机制 设计研究者的第一选择总是从VCG机制人手。然而，VCG机制也有很多局限。Aus

ubelandMilgrom[5]描述了VCG的优点和局限性，RothkopfL6]总结了VCG机制在现 实应用中的局限性。在本节，我们提供若干例子，用来说明VCG机制的一些细节。 例18.3（一件不可分割商品的维克瑞拍卖）有5个竞标人（智能体）参与一件不 可分割商品的密封拍卖，N={1，2，3，4，5}；他们对商品的评价分别为v=20， U2=15，v=12，v4=10，Us=6。如果使用维克瑞拍卖，那么智能体的优势策略是如实 报价，即报价等于自己的评价。由于智能体1的报价最高，智能体1获胜，此时转移给 智能体1的钱数t（θ) =∑u;(k（0）,0;)-∑0;(k(0-1),0;) =0-15=-15 这表示智能体1需要支付15元，这正好是第二高的报价（在这种情形下，为第二高的 评价）。注意，15元是当智能体1从出现变为不出现时所有其他智能体的总价值的变 化。这是智能体1对所有其他智能体施加的外部性。当智能体1在拍卖中获胜时，这个 外部性变为智能体1支付的钱数。 计算智能体1支付钱数的另外一种方法是，计算他对系统的边际贡献（参见上一节 的讨论）。智能体1出现时的总价值为20，而智能体1不出现时的总价值为15。因此， 智能体1的边际贡献为5。在维克瑞支付机制下，这个边际贡献是智能体1得到的折扣， 因此智能体1支付的钱数为20一5=15。这个折扣称为维克瑞折扣（Vickrey discount)。 第 例18.4（多件相同商品的维克瑞拍卖）与前面的例子一样，有5个竞标人（智能 章 体）参与密封拍卖，N={1，2，3，4，5}。他们对商品的评价分别为v=20，U2=15， v3=12，v4=10，05=6。但现在拍卖物是三件相同的商品。每个竞标人只想买一件。 维克瑞 如果使用克拉克机制，那么竞标人1、2和3获胜。转移给竞标人1的钱数 克拉克|格罗夫斯 =∑u;(k*（0），0;)—∑u;(k=(0-1),0;) j≠1 j≠1 =（15+12)—（15+12+10) =-10 因此竞标人1支付的钱数等于未获胜者中给出的最高报价。类似地，读者可以验证另外 斯机 两个获胜者（智能体2和3）支付的钱数也分别等于10。 制 这与按照智能体边际贡献来计算他支付的钱数是一样的。例如： 智能体1的边际贡献=（20+15+12）-（15+12十10）=10 我们在前面说过智能体i的边际贡献是他得到的折扣（称为维克瑞折扣），因此，智能 体1支付的钱数等于他的评价（20元）减去他的边际贡献（10元），即他需要支付 10元。 类似地， 智能体2的边际贡献=（20+15+12）-（20+12+10)=5 智能体3的边际贡献=（20+15+12）一（20+15十10）=2

因此，智能体2支付的钱数为15一5=10，智能体3支付的钱数为12一2=10。 对于上面的例子，现在假设智能体1需要2件商品，其余智能体每人需要一件。现 在我们要将2件商品配置给智能体1，将1件商品配置给智能体2。 转移给智能体1的钱数=15-（15+12+10）=-22 转移给智能体2的钱数=40-（40十12）=-12 这是因为智能体1的边际贡献为55一37=18，智能体2的边际贡献为55一52=3。口 例18.5（公共项目问题的VCG机制）考虑例18.1讨论的公共项目问题。为了方 便参考，我们将这个问题复制于此。公共项目的成本为50元。两个智能体1和2的类 型集为=02={20，60}。每个智能体要么有低的支付意愿（20元），要么有高的支付 意愿（60元）。令项目选择集为K={0，1}，其中1表示项目上马，0表示项目不上马。 如果K=1，那么这两个智能体均摊项目成本，即每个人支付25元。如果K=0，由于 项目流产，智能体不需要支付钱。考虑评价函数（价值函数） 0;（k，0;）=k（0-25） 这表示，若k=0，智能体i得到零价值；若k=1，那么智能体i得到的价值是他的支付 意愿减去25。定义下列配置函数： k（0，02）=0若0=02=20 =1其他情形 博 这表示项目上马仅当至少其中一个智能体有高支付意愿。 弈论与机 对于这个公共项目问题，我们计算每个智能体在每个类型组下的克拉克支付。我们 还将计算效用。首先考虑类型组（20，20）。由于k（20，20）=0，因此每个智能体得 制 到的价值为零。因此，每个智能体的克拉克支付为零，效用也为零。 设计 接下来考虑类型组（60，20）。注意到，k（60，20）=1。智能体1得到的价值为 35，智能体2得到的价值为一5（这是因为两人平摊项目成本，即每人支付25元）。如 果智能体1不出现，那么智能体2独自面对公共项目，此时k=0，这是因为他的支付意 愿为20。因此，当智能体1不出现时智能体2得到的价值为零。这表示 t（60,20）=-5-0=-5 这意味着智能体1除了支付（平摊成本）25元之外还要支付5元，这是他对公共项目 成本的贡献。上面这个支付（25十5=30元），与边际贡献法计算的结果是一样的。注 意到，智能体1的边际贡献为（60一25）+（20-25）一0=35一5=30。 现在我们可以计算智能体1的效用了，它等于 u（60，20)=v（60,20)+t（60，20)=35-5=30 为了计算t（60，20），我们首先注意到当智能体2不出现时，智能体1得到的价值为 （60一50）。因此， t（60,20)=35-10=25 这表示智能体得到了25元；当然，这是他支付25元项目成本之外的事情。现在

u2（60,20）=v2（60，20）+t2（60，20）=-5+25=20 类似地，我们可以计算所有类型组下智能体支付的钱数和效用。参见表18一3。口 表18-3 不同类型组下转移给智能体的钱数和智能体得到的效用 (0，02) t（0，02) t2(0，02) u1(0，02) u2（01，02) (20，20) (60，20) -5 (20，60) -5 (60，60) 例18.6[防策略的网络构成（strategyproofnetworkformation）]考虑图18—1所 示的供应链构成问题。节点S代表起点，T代表终点；A和B是两个中点。SP1，SP2， SP3，SP4代表4个不同的服务商（智能体）。 SP SP2 S SP, SP T5 图18一1网络构成问题（情形1） 第 在此图中，服务商由各条边的拥有者表示。服务成本（销售意愿）已标注在每条边 章 上。买者的问题是找到一条从S到T的路径使得成本最小。令（y，y2，y3，y4）表示 维克瑞-克拉克|格罗夫斯机制 配置向量。可行配置向量为 K={（1,1,0,0),（0,0,1,1）} 其中配置（1，1，0，0）有配置效率，这是因为它使得配置成本最小。我们定义价值 如下 u;（（y1，y2，y3，y4）,0:）=-y0 上面定义价值的方式说明成本最小化问题等价于价值最大化问题。使用克拉克支付规 则，可得 t（θ）=-10-（-25）=15 t2（0）=-10-（-25）=15 如果计算边际贡献，我们发现每个智能体的边际贡献都为5；在确定智能体得到的钱数 时，这个边际贡献要加到价值上。这两个智能体的效用分别为 u（0）=-10+15=5 u2（0）=-10+15=5 对于SP和SP4，智能体得到的钱数与效用都为零。下面我们考察SP4的销售意愿发 生变化带来的影响。令SP4的销售意愿为15。于是，我们发现配置（1，1，0，0），

（0，0，1，1）都有配置效率。如果我们选择配置（1，1，0，0），我们得到 t（0)=10；t2（0）=10；u1（0)=0；u2（0）=0 这表示，买者支付给服务商的钱数等于服务成本。获胜的智能体没有得到额外支付。在 这种情形下，这个机制对买者有利，对卖者不利。 如果SP4的销售意愿为95，那么配置（1，1，0，0）是有效率的，由此可得 t（0）=90；t2（0）=90；u1（0）=80；u2（0）=80 在这种情形下，机制对买者极其不利，对卖者非常有利。 现在我们打通路径BA，从而引入一个新的服务商（智能体）SP5。如图18一2 所示。 SP SP2 SPs S SP, SP T5 图18—2网络构成问题（情形2） 此时有效率的配置为（0，1，1，0，1）。这种情形下， t2（0）=13;t3（0）=8;t5（0）=5 u2（0）=3；u（0)=3；u5（0）=3 这表示买者总的支付钱数为26，而当SP；不出现时，这个数字为20。因此，尽管增加 了一个智能体，买者支付的钱数却增加了。在这里，克拉克支付规则展现出了非单调 性。口 上面这些例子说明了当VCG机制用于现实问题时，它们表现出了什么样的特性。 18.5小结与参考文献 维克瑞-克拉克-格罗夫斯机制代表着一类在拟线性环境下满足优势策略激励相容和 配置效率的机制。下列知识点值得注意。 ·在拟线性环境下，给定任一社会选择函数，它的每个结果都可以分解为两个部 分：一是配置部分，一是支付部分。效用线性地取决于价值和支付，其中价值是配置和 私人类型的函数（可能为非线性函数）。 ·拟线性环境下的社会选择函数具有一个显著性质，即它们都不是独裁的。另外一 个别致的性质是事后效率，它等价于伴随严格预算平衡的配置效率。配置效率表示在每 个结果中，配置的价值之和（该配置的社会福利）达到最大。严格预算平衡是指在每个 结果中，智能体的总支出等于智能体的总收入。

·维克瑞拍卖机制是克拉克机制的一种特殊情形，而克拉克机制又是格罗夫斯机制 的一种特殊情形。格罗夫斯定理表明伴随格罗夫斯支付规则且有配置效率的社会选择函 数，将满足极其合意的优势策略激励相容性。格罗夫斯支付表达式基于下列原理：转移 身类型0，但这种“取决于”不是任意的，具体地说，t：取决于0对配置的影响。 ·克拉克机制是格罗夫斯机制的一种特殊情形；换句话说，在格罗夫斯机制中，令 转移给智能体的钱数取决于该智能体不出现时所有其他智能体的价值，就可以得到克拉 克机制。克拉克机制表明当智能体自己的边际贡献被当作一种额外激励时，每个智能体 都会如实报告自己的类型。 ·维克瑞拍卖是克拉克机制的一种特殊情形；换句话说，如果我们把克拉克机制应 用到多个相同商品被拍卖的情形，我们就得到了维克瑞拍卖。当克拉克机制被用于组合 拍卖（combinatorialauction）时，我们将这种机制称为广义维克瑞拍卖（generalized Vickreyauction，GVA）；我们将在第20章介绍这种机制。 维克瑞拍卖是威廉·维克瑞的开创性贡献[1]，著名的关键人（pivotal）机制是由 克拉克提出的[2]，克拉克机制的一般化则要归功于格罗夫斯[3]。这些经典论文是机制 设计研究者的必读之物。 口参考文献 ders".In:JournalofFinance 16(1)(1961),pp.8-37. 第 [2]E.Clarke.“Multi-part pricing ofpublic goods”.In:PublicChoice 11(1971), 章 pp.17-23. 维 [3]T.Groves.“Incentives in teams”.In:Econometrica 41 (1973),pp.617-631. 克瑞 [4]J.R.Green and J.J.Laffont.Incentives inPublicDecisionMaking.North- 克拉 Holland,Amsterdam,1979. [5]L.M.Ausubel and P. Milgrom.“The lovely but lonelyVickrey auction”.In: 克丨 Combinatorial Auctions.Ed.by P.Cramton,Y.Shoham,and R.Steinberg.The MIT 格 Press,Cambridge,Massachusetts,2006,pp.17-40. 罗 夫 [6]M. Rothkopf.“Thirteen reasons why the Vickrey-Clarke-Groves process is not 斯 practical".In:OperationsResearch 55(2)(2007)，pp.191-197. 机 制 18.6习.题 （1）某个买者试图通过密封拍卖形式采购一件不可分割的商品，有五个卖者（智能 体）{1，2，3，4，5}竞标，他们的评价分别为v=20，V2=15，U=12，U4=10， U5=6。这些评价自然可以解释为销售意愿。如果拍卖使用维克瑞拍卖机制，请计算配 置以及智能体得到的钱数。如果买者希望购买三件而不是一件商品，而且每个卖者至多 只能提供一件，请计算配置以及智能体得到的钱数。最后，如果买者希望购买六件商

品，每个卖者至多提供两件，请计算配置以及智能体得到的钱数。 （2）在某个交易系统中，每人只能买（卖）一单位商品。有4个卖者S1，S2，S3 和S4以及3个买者B1，B2，B3。下面给出了买者对一单位商品的报价和卖者的要价。 我们的目标是使得这个交易系统的剩余最大。 S1:10,S2:12,S3:14,S4:16, B1:8,B2:12,B3:18。 （a）将交易系统的剩余定义为买者支付的总钱数减去卖者得到的总钱数。如果某个 配置使得这个剩余最大，我们将其称为配置剩余最大化。求这个交易系统的这种配置。 （b）假设使用维克瑞拍卖机制，应该怎样支付？ （c）这个机制满足预算平衡吗？ （3）在某个拍卖中，有m件相同的商品待售。令买者（竞标人）有n个，其中 n>m。买者对商品的评价分别为U1，"，Un。每个买者至多购买一件商品。对于这个 拍卖情形，写出配置规则使其有配置效率。在这种情形下，克拉克支付是怎样的？你能 看到任何麻烦之处吗？如果有，你应该如何克服它们？ （4）在某个拍卖中，只有一件不可分割的待售商品。报价最高者获胜，获胜者支付 的钱数等于对商品评价最低的落败者报价的2倍。作为一个例子，考虑5个买者，他们 对商品的评价分别为20、15、12、10和8。伴随评价20的买者获胜，他支付的钱数等 于16（8的2倍）。另一方面，如果只有三个买者，他们对商品的评价分别为20、15和 博奔论与机制设 12，此时第一个买者获胜，他需要支付24。这个机制是一个克拉克机制吗？它是一个 格罗夫斯机制吗？它是激励相容的吗？ （5）（编程题）实施克拉克机制。仔细识别程序的输人。输出必须是针对任何给定 类型组的有效率配置和支付向量。这个实施也可以推广到格罗夫斯机制。 设计