一般的机制设计问题
前面的讲座中只考虑了单变量机制设计问题，其中每一个参与者都只有一个私人信息，即他对每单位物品的价值。在很多问题中，一个参与者对于不同的物品有不同的私人价值。一旦我们对于一个参与者是否喜欢物品A胜过物品B不确定时，我们就进入了多变量(multi-parameter)机制设计。
下面是一个一般的，多变量的机制设计问题的组成部分：
- 个策略性参与者，或“代理人(agents)”；
- 结果的有限集；
- 对于每个结果，每个代理人都有一个私人价值。
结果集是抽象的，并且可能很大。在一个单变量环境中，仅有个元素，对应物品的获胜者（如果有的话）。在单物品拍卖的标准单变量模型中，我们假设在一个代理人没有获胜的全部个结果中，他的价值为0，从而对每一个代理人只剩下一个未知的变量。在上述的更一般的多变量框架中，一个代理人对每一种可能的拍卖结果都有一个不同的价值。这个例子不是没有合理的应用：举例来说，在对一个热门的创业公司的收购战中，代理人的最高价值也许是收购这个创业公司，但是如果他输掉的话，他倾向于这个创业公司被来自不同市场的公司收购，而不是一个直接的竞争者。
VCG机制
我们接下来的结果是算法设计理论的基石。
定理2.1 (VCG机制[1,2,3]). 在每一个一般的机制设计环境中，都有一个满足DSIC的福利最大化机制。
回顾课件2中“令人惊叹”的拍卖的三个性质。定理2.1满足了前两个性质，但没有第三个性质（多项式运行时间）。我们已经知道，即使在单变量环境中，我们也不能总是拥有第二个和第三个性质（除非）。我们会看到，在很多重要应用中，VCG机制非常地不令人惊叹。
同往常一样，设计一个（直接显示的）DSIC机制是技巧性的，因为分配和支付规则需要仔细地结合。课件4中对显示原理的证明不需要改变就可以用于多变量环境，因此限制为直接显示的机制不失一般性。我们应用一直在单变量环境中使用的相同的两步途径。
第一步是无理由地先假设所有的代理人都会真实地揭示他们的私人信息，然后搞清楚选择哪一个结果。因为定理2.1要求福利最大化，唯一的解决方法是将出价视为真实的（而不知道的）价值，挑选福利最大化的结果。也就是说，对给定的出价，我们定义分配规则为 第二步是定义一个支付规则，当跟上面的分配规则结合时，产生一个DSIC机制。上一次我们在单变量环境中到达这一步时，我们推导并证明了Myerson引理。对于这样的环境，Myerson引理是对第二步的一般解法。回顾下Myerson引理声明分配规则的单调性是可实现性的充分必要条件，而且对于单调的规则，它给出了唯一一个满足DSIC条件的支付规则的显式公式。Myerson公式对于超越单变量环境的情况不适用――对于代理人提交超过一个维度的出价的情况，甚至不清楚要如何定义一个分配规则的“单调性”。对可实现的多变量分配规则有一个类似的特征叫做“环单调性(cycle monotonicity)”。这是一个优雅的结果，类似于一个网络中存在良好定义的最短路径当且仅当其中没有负的环的事实。然而环单调性比单变量的单调性笨拙得多。由于它太难验证，环单调性在具体环境中很少被用来实施或推导DSIC支付规则。类似的，（对于0-1问题的）DSIC费用的“关键出价”描述在多变量环境中也没有一个明显的类比。
关键想法是利用福利最大化分配规则的DSIC费用的另一个特性（在练习中证明），作为代理人导致的“外部性(externality)”――由于的出现导致的其他个代理人的福利损失。举例来说，在一个单物品拍卖中，获胜的投标人会对其他人造成第二高出价的福利损失（假设真实出价），而这正是Vickrey拍卖的支付规则。“按外部性收费”的想法在一般的机制设计环境中完全合理，并且对应支付规则
其中是(1)式中选取的结果。注意到总是非负的（练习）。
我们声称这个机制，VCG机制，满足DSIC。（根据定义，假设真实出价，它最大化福利。）自从Vickrey拍卖后第一次，我们从头开始证明DSIC性质（即，不使用Myerson引理）。回顾下这意味着对每一个代理人和其他代理人的出价，代理人通过选来最大化他的拟线性效用。
固定和，当选取的结果为，的效用为
观察到第二项(B)是常数，与无关。因此，最大化代理人的效用的问题简化为第一项(A)。作为一个假想实验，假设代理人有直接选取结果的能力，而不是仅仅通过出价的选择间接地影响最终的结果。代理人当然会使用这个额外的能力来选取最大化第一项(A)的结果。如果代理人设置，那么公式(1)中机制的最大化目标跟代理人想要最大化的第一项(A)相同。因此，诚实出价会导致机制选一个最大化代理人的效用的结果；没有其他的出价能够做得更好。这就完成了定理2.1的证明。
下面是对VCG机制中的费用的另一个解释。将(2)式中的表达式改写为 因此我们可以将代理人的费用看做他的出价减去一个“回扣”，而回扣等于当存在时带来的福利增加。举例来说，在Vickrey拍卖中，出价最高的投标人支付他的出价减去一个的回扣（其中是第二高的出价），即获胜的投标人带来的福利增加。
我们将(4)式中的回扣总是非负的留作练习，这意味着，因此诚实报价的代理人能保证有非负的效用。
VCG机制的结果表明，在一般的多变量环境中，满足DSIC的福利最大化分配规则从原理上总是可能的。尽管在实践中不可能被实施，VCG机制仍然作为更加实际的机制而言有用的基准。
组合拍卖
组合拍卖在实际中很重要。在政府的频谱拍卖中，很多组合拍卖已经创造了几千亿美元的收入。它们也被用在其他的应用中，例如分配机场的起飞和降落时间段。组合拍卖也是出了名的困难，无论是理论上，还是实践中。理论工作已经确认了在合理的通信和计算代价下能够做什么的问题的许多不可能结论。时间已提供了设计糟糕的组合拍卖带来严重后果的例子。例如1990年新西兰频谱拍卖只筹集了三千六百万美元，远远低于顾问估计的两亿五千万美元（细节见[4]的第一章）。
模型
一个组合拍卖有个投标人——例如，Verizon，AT\&T和其他几个地区性的运营商。有个物品组成的集合，这些物品不等同——例如，一个许可证允许在一个给定的地理区域内在特定的频段上广播。结果集对应一个维向量，其中代表了分配给投标人的物品集合（他的“物品组合(bundle)”），同时没有一个物品被分配两次。一共有个不同的结果。对可能得到的每一个物品组合，每一个投标人有一个私人价值。因此，每个投标人有个私人变量。通常假设以及当时（即“自由丢弃(free disposal)”）。我们接下来会讨论对价值的其他假设。
一个结果的福利是。原理上，VCG机制提供了最大化福利的DSIC解决方案。当投标人的价值足够结构化时可以很有用，例如“单位需求”的投标人（见练习）。然而一般而言，实施VCG机制有几个大的障碍。
挑战
组合拍卖的第一个主要挑战是偏好获取(preference elicitation)。每一个投标人有个私人变量，当时大约是1000，当时大约是100万。没有一个投标人会在他们的右手边写下（或弄清楚）这么多的出价。没有卖家会愿意听这么多的出价。这种指数级数量的私人变量构成了VCG机制，以及每一个其他的直接显示机制，对于实际中的组合拍卖是不可取的。注意到这个挑战永远不会在单变量机制设计中出现，那里每一个投标人只需要通信一个数值。
直接显示组合拍卖的这种荒诞激励了非直接的(indirect)机制，基于一个“需要知道”的基础学习关于投标人的偏好的信息。我们还完全没有讨论过这样的机制。典型的非直接拍卖是上升的英式拍卖。你应该通过电影熟悉了这种拍卖形式——一个拍卖人纪录现在的价格和暂定的赢家，当只有一个有兴趣的投标人剩下的时候拍卖停止。有很多变形。很多电影和拍卖屋，例如Christie和Soethby，使用一种“公开喊价(open outcry)”拍卖，其中投标人可以退出和回来，也可以用“越级出价(jump bids)”来激进地太高现在的价格。当进行数学分析时，“日本”变形通常更方便：拍卖开始于一个起拍价，这个起拍价是公开的并且以恒定的速率增长。每个投标人要么选择“跟进”或“退出”。一旦一个投标人退出他就不能回来。胜者是最后一个跟进的投标人，而销售价是当倒数第二个投标人退出时的价格。每个投标人都有一个占优策略，只要当前价格低于他的价值就留在拍卖中（投标人可能会以正的效用获胜），一旦当前价格到达价值就退出（在那之后获胜只会导致负的效用）。假设所有投标人都遵循这样的策略，英式上升拍卖的结果跟Vickrey（密封出价）拍卖的一样。Vickrey拍卖就是当你对英式拍卖应用显示原理（第4讲）获得的结果。
除了对于最小的那些组合拍卖，非直接的拍卖都是不可避免的。我们会在下一讲中讨论无线频谱拍卖实际应用的拍卖形式。非直接拍卖也会在类似单物品拍卖这样的单变量环境中有用。经验研究显示投标人更有可能在一个英式拍卖中遵循占优策略，而不是在一个密封出价的次价拍卖中。在后者中，一些投标人会莫名其妙地出更高的价[5]。其次，上升拍卖泄露了更少的信息给拍卖人。在一个Vickrey拍卖中，拍卖人掌握了最高出价；而在一个英式拍卖中，拍卖人只掌握了最高出价的一个下界（即第二高出价）。一个重要的问题是：非直接的机制能否，至少在原理上，获得非平凡的福利保证，同时仅从投标人那里获取少量的信息（例如和的多项式形式）？有很多关于这个问题的优美的理论工作，而答案粗略来说，对复杂的价值是否定的，而对足够简单的价值是肯定的。我们会在下一讲中，以及在课程CS364B中进一步地讨论这个问题。在实际中，我们希望投标人的价值足够简单并且/或拍卖性能会比最差情况下的下界好很多。
设计实用的组合拍卖的第二个挑战跟我们在算法机制设计中的讨论类似。即使第一个挑战不是问题的话——举例而言，当投标人是单变量的并且直接显示是实用的——福利最大化也可能是一个棘手的问题。我们会在背包拍卖及一系列问题中遇到这个困难。这个挑战是根本性的，不可能通过一个更聪明的拍卖形式避免。在实际中，我们希望组合拍卖计算出的分配结果能够相当接近福利最大化。这是不可能直接验证的，因为投标人的价值未知且实际中使用的组合拍卖不满足DSIC，从而提供了策略化的机会。然而，有各种简单的“明智检查”能够被用于一个拍卖结果来验证好的福利最大化。举例而言，投标人是否成功获取了合理的打包（例如，在相邻地区或频段的频谱许可证）？是否相似的物品售出了相似的价格？
第三个挑战针对的是VCG机制——它被证明是唯一满足DSIC的福利最大化机制——即使当前两个挑战不重要时（例如，在一个足够小的单变量问题中，福利最大化能够在一个合理的时间内完成）。具体来说，VCG机制尽管满足DSIC，却可能带来差的收入和激励性质。
举例来说，假设有两个投标人和两个物品，A和B。第一个投标人只想同时要这两个物品，因此，其他情况为0。第二个投标人只想要物品A，因此，其他情况为0.在这个例子中VCG机制的收入为1（见练习）。但是假设我们加入了第三个只想要物品B的投标人，于是。最大福利升高到了2，但是VCG收入降到了0（见练习）！VCG机制在一个看上去竞争的环境中零收入的事实在实践中是一个大忌。这个例子中的收入非单调也暗示了许多的激励问题，包括对串通和伪造身份投标的脆弱（见练习）。这些问题完全没有出现在单物品的Vickrey拍卖中。
第一个挑战招致了第四个。几乎所有实际中使用的组合拍卖都是迭代式的，有一系列回合组成。我们会在下一讲中讨论细节。迭代式拍卖给了策略式行为新的机会。举例来说，Cramton和Schwatz[6]发现，在一个早期的相对竞争不激烈的频谱拍卖中，投标人用他们出价的低几位来有效地向其他投标人传递信息。让我们考虑这场拍卖中的许可证#378，它允许了在明尼苏达州的罗彻斯特使用频谱的权利。USWest和McLeod在竞争这个许可证，试图通过不断地增加出价来压过对方。很明显地，USWest厌倦了这场竞价战并转向了报复性的策略——竞价一些其他地理区域上的许可证，在这些许可证上McLeod出价很高，而之前的回合中USWest完全没有表现出兴趣。McLeod最终赢回了所有这些许可证，但是由于USWest的投标不得不付更高的价格。为了保证它的信息明显而清楚地表达出来，所有USWest的报复性投标都是1000的倍数加上378——大概是想警告McLeod退出罗彻斯特的市场，或其他目的。这种特殊形式的信号能够通过强制所有的出价都是一些合适的大数的组合来大大消除，但是其他不愿见到的策略性行为仍然存在。
参考文献
[1] Edward H Clarke. Multipart pricing of public goods. Public choice, 11(1):17-33, 1971.
[2] Theodore Groves. Incentives in teams. Econometrica: Journal of the Econometric Society, pages 617-631, 1973.
[3] William Vickrey. Counterspeculation, auctions, and competitive sealed tenders. The Journal of finance, 16(1):8-37, 1961.
[4] Paul Robert Milgrom. Putting auction theory to work. Cambridge University Press, 2004.
[5] Ronald M Harstad. Dominant strategy adoption and bidders' experience with pricing rules. Experimental economics, 3(3):261-280, 2000.
[6] Peter Cramton and Jesse A Schwartz. Collusive bidding: Lessons from the fcc spectrum auctions. Journal of regulatory Economics, 17(3):229-252, 2000.