拍卖 在当前现实世界电子商务以及其他数不清的网络应用中，拍卖无处不在。拍卖为伴 随货币的机制（mechanismswithmoney）提供了一个自然例子。机制设计理论为拍卖 的设计提供了一种原则性的方法，来保证合意性质得以满足。在本章，我们讨论几种不 同的拍卖以及重要机制设计议题。特别地，我们讨论四种基本拍卖类型（买或卖一件不 可分割的商品）：英国式拍卖、荷兰式拍卖、第一价格密封拍卖、第二价格密封拍卖 （维克瑞拍卖）。我们讨论了一个关于上述四类拍卖的重要结果，即收入等价定理（rev- enueequivalencetheorem）。我们还介绍了组合拍卖（combinatorialauctions）。 拍卖是一种将一组商品配置给一组竞标人的机制，配置依据是竞标人的报价。拍卖已 有几千年历史。近年来，在基于网络的应用中，拍卖急剧增长。这些拍卖包括传统商品例 如油画和纪念品的拍卖，也包括互联网广告空间、搜索引擎网站上的关键词、企业采购、 频谱分配、机场时隙分配等的拍卖。因此，拍卖既有理论价值也有现实应用价值。 目前已有很多关于拍卖的优秀文献，例如书籍[1，2，3]和综述文章[4，5，6]。 近年来，一些综述主要集中于组合拍卖。7,8,9,10] 20.1拍卖类型与合意性质 拍卖分类 KalagnanamandParkes9]建议按照以下六个标准对拍卖进行分类。 （1）资源：资源是被拍卖物。资源可以是一种商品也可以是多种商品（每种商品可以 只有一单位，也可以有多个单位）。多种商品的拍卖称为组合拍卖（combinatorialauctions）。

（2）市场结构：有三类拍卖市场结构。一是前向拍卖（forwardauction），一个卖 者把商品卖给多个买者；二是后向拍卖（reverseauction），一个买者向多个卖者购买商 品，比如采购；三是双向拍卖或交易，这是指伴随多个买者和多个卖者的拍卖。 （3）偏好结构：偏好定义了不同拍卖结果带给智能体的效用。例如，当拍卖物涉及 一种商品的多个单位时，智能体对于额外一单位商品的边际效用可能是递减的。如果一 件商品有多个属性，例如成本、前置时间（从订货到交换的时间）、质量、可靠性等， 那么智能体的偏好结构应该能够描述他对这些属性的重要程度评价。 （4）报价结构：报价结构定义了智能体对拍卖物的要求。对于一件不可分割商品的 拍卖，报价就是购买意愿或销售意愿。对于多个单位的相同商品拍卖，报价需要说明价 格和数量。这引入了折扣优惠的可能性。在多种商品拍卖情形下，报价可能说明智能体 对商品束（即商品组）的偏好。 （5）确定获胜者：其他文献也将获胜者的确定称为市场出清（marketclearing）、评 标（bidevaluation）、标的物配置（bidallocation）或仅称配置（allocation）。在前向拍 卖中，确定获胜者是指选择一个最优买者子集，商品配置给这些买者。在后向拍卖中， 确定获胜者是指选择一个最优卖者子集，他们有资格卖掉商品。在交易（双向拍卖） 中，确定获胜者是指确定买者和卖者的最优匹配。获胜者确定问题的计算复杂性，是设 计者在设计拍卖时考虑的一个重要议题。 （6）信息反馈：拍卖规则可能伴随信息反馈，也可能不伴随信息反馈。在只有一轮 的拍卖中，智能体递交报价但得不到拍卖的信息反馈（例如价格信号）。在多轮拍卖中， 智能体可根据信息反馈调整报价。关于拍卖状态的反馈通常用价格信号（pricesignal) 第 或暂定配置（tentativeallocation）进行刻画，反馈提供了智能体们的报价信息，从而帮 章 助智能体修改自己的报价。 拍 口拍卖：合意性质 卖 我们现在考察拍卖设计者想要的合意性质。正如我们在上一章看到的，并非所有这 些性质能同时实现。根据具体环境，拍卖设计者必须仔细选择这些性质的一个最大子 集，使得这个子集中的所有性质能同时得以满足。 口解均衡 给定智能体i关于其他智能体的信息，如果任何一个智能体i都不希望改变自已的 报价，那么机制的解处于均衡状态。给定关于智能体（买者和卖者）的偏好假设、个体 理性以及信息可得性，很多类型的均衡都能计算出。我们已经了解了一些均衡类型：贝 叶斯纳什均衡、事后纳什均衡、强（弱、极弱）优势策略均衡。 口激励相容 给定一个拍卖，如果智能体通过报告他们对拍卖物的真实评价来使得自已的期望效 用最优，那么我们说该拍卖是激励相容的。根据如实报价实现的均衡性质，激励相容拍 卖可以是贝叶斯激励相容的，也可以是优势策略激励相容的。如果某个机制是优势策略 激励相容的（DSIC），那么每个智能体的决策仅取决于自己的信息，他不需要模拟或计

算其他智能体的策略。在贝叶斯激励相容（BIC）情形下，计算均衡策略要求先验概率 分布的信息。事后激励相容（ex-post incentivecompatibility，EPIC）是另外一种激励 相容，EPIC比BIC强，但比DSIC弱。我们将在第23章讨论这个性质。 口配置效率 当所有获胜者的社会效用（这些获胜者的效用之和）最大时，配置效率得以实现。 配置效率保证了拍卖物配置给评价最高者。 口个体理性 在拍卖中，如果配置没有使得任何智能体的状况比他不参与拍卖时更差，那么拍卖 是个体理性的（或称有自愿参与性质）。这意味着，每个智能体通过参与拍卖能得到非 负效用。 口预算平衡 在某个拍卖的所有可行结果中，如果买者的支出大于或等于卖者得到的收入，那么 这个拍卖是弱预算平衡的；如果净货币转移为零（买者的支出等于卖者的收入），那么 这个拍卖是强预算平衡的。换句话说，预算平衡保证了拍卖机构或机制设计者不会 亏损。 博奔论与机制设计 口收入最大化或成本最小化 在前向拍卖中，卖者有一组商品要卖，他希望使得自己的总收人最大。另一方面， 在后向拍卖（采购拍卖）中，买者希望成本最小。通常，卖者的目标不是收入最大化而 是利润最大化，其中利润等于收入减去成本。在交易环境（双向拍卖）中，有多个买者 和多个卖者。我们的目标是剩余最大化，其中剩余是总收入减去总支出。 口公平性 用于确定获胜者的算法，尤其是基于启发式的算法，可能导致不同时点出现不同获 胜者集。由于可能存在着多个最优解，因此不同算法将产生不同的获胜者集。这让竞标 人感到不公平，从而影响他们参与拍卖的意愿。落败的竞标人由于在另外一种算法下可 能是获胜者，会感觉到被暗算了。 口防欺诈 防欺诈（cheatproofness）的意思是拍卖应是稳健的，也就是说它应该能防御竞标 人用假名字攻击或者花样百出的操纵。 20.2经典机制：一件不可分割的商品的拍卖 当拍卖物为一件不可分割的商品时，有四种基本拍卖类型。我们在这里讨论前向拍

卖（销售）。这四种拍卖也可用于后向拍卖（采购）情形。 口英国式拍卖 英国式拍卖（Englishauction）也称为公开喊价拍卖或递增报价拍卖。在这里，价 格从低逐渐升高直到只剩下一个竞标人。这种拍卖可以采取以下方式：（a）拍卖师报 价；（b）竞标人自己报价；（c）通过电子方式报价。在任何时点上，每个竞标人都知道 当前最高报价水平。获胜者按最终胜出价格进行支付。 口荷兰式拍卖 荷兰式拍卖（Dutchauction）也称为递减报价拍卖。在这里，拍卖师一开始报出高 价，然后持续降低，直到有人接受当前的价格。获胜者按当前价格支付。 口第一价格密封拍卖 在这种情形下，每个潜在买者递交密封好的报价，报价最高者获胜。如果出现了多 个最高报价，则用事前规定好的规则决定谁是获胜者。获胜者按自已的报价支付。 口第二价格密封拍卖 这是经典的维克瑞（Vickrey）拍卖。与第一价格密封拍卖一样，每个潜在买者递 交密封报价，报价最高者获胜。然而，现在获胜者按第二高的报价支付（这也是落败者 中的最高报价）。 第 例20.1[经典拍卖（CanonicalAuction）]考虑下列情形。有个卖者想卖掉一件商 章 品。有两个潜在买者1和2。买者1的支付意愿为10，买者2的支付意愿为15。每个竞 拍 标人（买者）不知道另外一个竞标人的支付意愿。口 英国式拍卖 卖 典型英国式拍卖按下列方式进行。买者1报价5，然后买者2报价6。现在买者1 可能将报价增加到8。于是，买者2可能将报价增加到9。买者1再一次将报价提高到 9.5。买者2也再一次修改报价，他报价10。假设买者1不再提高自己的报价。因此， 买者2胜出，他得到了拍卖物并支付10。 荷兰式拍卖 典型荷兰式拍卖如下。卖者报价20。两个买者都不愿意按该价格购买。卖者将价 格降低到18，仍然没有人愿意购买。卖者持续降价，比如，降低到16、14、12、11。 假设在11这个价格水平上，买者2想买，因为（尽管他不知道买者1对拍卖物的评价） 他可能认为买者1先于他表达购买愿望。注意，11小于买者2的支付意愿（为15）。 第一价格密封拍卖 假设买者1报价9，买者2报价11。于是买者2获胜，他向卖者支付11。 第二价格密封拍卖（维克瑞拍卖） 每个买者知道如果他自已获胜，他必须支付另外一个买者的报价。在这里，如实报 价是一个弱优势策略。因此，买者1将报价10，买者2将报价15。买者2获胜，他向 卖者支付10，注意10是第二高报价。口

20.3第一价格密封拍卖和第二价格密封拍卖的收入等价性 在本节，我们证明在一些条件下，卖者在第一价格密封拍卖和第二价格密封拍卖下 的期望收人相等。事实上，在两种拍卖的收入等价性上，我们证明了一个更一般的结 果，这里的两种拍卖是第一价格密封拍卖和第二价格密封拍卖的自然推广。 假设一个卖者希望卖掉一件不可分割的商品，有n个潜在买者。假设0是买者智能 体i（i=1，"，n）的类型，0自然可以解释为智能体i的支付意愿。假设y（0）指当 智能体报告类型组0=（0，"，0）时，智能体i得到拍卖物的概率。买者（智能体）i 在类型组为0=（0，，0）时的期望收益为y（0)0十t（0)，其中t（0）是当类型组为 0时转移给买者i的钱数。注意，这种期望收益的表达式意味着我们处于线性环境（参 见19.7节）。配置集为 K={（y,,yn）:y∈[0,1],Vi=1,,n; y≤1} j=1 与以前一样，令y（0）=E[y（，0-)]为当智能体i报告类型θ：且所有其他智能体 如实报告类型时智能体i得到拍卖物的期望概率。类似地，（)=E[（，0-)] 表示当智能体i报告类型θ：且所有其他智能体如实报告类型时智能体i得到的期望支付。 博 奔论与机 于是， U（0）=y（0）0+t（0） 表示当所有智能体如实报告类型时智能体i的期望效用。我们现在给出和证明一个重要 制 设 命题。 计 定理20.1考虑伴随下列条件的拍卖情形： （1）n个风险中性的竞标人（买者）1，2，“，n。 （2）竞标人i的类型（即他对拍卖物的评价）位于区间=[0，0]CR，其中 <0i。 （3）竞标人i（i=1，2，"，n）对拍卖物的评价以严格正密度（·）>0抽自区 间[0：，0]。令Φ：（·）为累积分布函数。 （4）竞标人i的类型在统计上互相独立。 假设给定与两个不同拍卖机制相对应的贝叶斯纳什均衡，使得： ·对于每个竞标人i，对于（0，，0）的每个可能实现值，竞标人i在这两个拍 卖下得到拍卖物的概率相等。 ·当竞标人i（i=1，2，"，n）对拍卖物的评价位于最低可能水平时，他在这两 个拍卖下得到的期望收益相等。 那么卖者从这两个拍卖中得到的期望收人相等。 在证明这个定理之前，我们稍微说一下上述定理中的第一个假设，即风险中性。我 们已经在第8章（8.6节）讨论了参与人的三种风险态度：风险厌恶、风险中性以及风

险喜好。至于风险中性，简单地说，是指参与人的效用是他持有货币的线性函数。 证明：根据显示原理，在这个拍卖环境下，我们只要考察两个贝叶斯激励相容 （BIC）的社会选择函数就足够了。我们需要证明这两个贝叶斯激励相容的社会选择函数 （a）有相同的配置函数（y（θ)，，y（θ）），Vθ∈；（b）U（0），，U（0n）的相 同值将对卖者产生相同的期望收人。 给定任何贝叶斯激励相容机制，我们首先确定卖者的期望收人表达式 卖者的期望收入= ∑E[-t;(0)] (20.1) 现在，我们有 E[-t;(0)]=Ea[-E[t;(0)]] y;(0;)0;—U;(0;)];(0;)d: [y(0;)0;-U;(0;)]- y(s)ds(0）d0 最后一步成立的原因在于线性环境下贝叶斯激励相容函数的迈尔森特征（参见19.7 节）。现在，上面的表达式等于 。(v;(0)0: —Jy;(s)ds ):(0)do:;]U;(0;) 我们首先化简 拍 [(fy;(s)ds ):()d; 卖 化简方法是使用分部积分，其中 y（s)ds作为第一个函数。化简，可得 y：(0)dθ；—y；(0;);(0;)dθ= y：（0:）[1-Φ;（0)]dθ 0; 因此，我们得到 pi(0;) (II;(0;))do..dθ p;(0;) j=] 原因是 j=1 不含d

因此，卖者的期望收入 pi(0:） j=1 i=1 通过考察上面的表达式，我们可以看到：给定任何两个贝叶斯激励相容的社会选择函 数，如果它们产生相同的函数（y（θ)，，y（)）而且产生U（1），"，U（0）的 相同值，那么它们带给卖者的期望收入是相等的。■ 注释第一价格密封拍卖和第二价格密封拍卖满足上述定理的条件： ·在这两种拍卖中，评价最高的竞标人获胜。 ·在这两种拍卖中，竞标人的评价抽自某个实区间[0：，0]，而且给定任何竞标 人，只要他的评价等于0：，那么他的收益为零。 因此，这个定理可用于上述两种拍卖的均衡：注意，在第一价格密封拍卖情形下， 它是一个贝叶斯纳什均衡，而在第二价格密封拍卖下，它是一个弱优势策略均衡。因 此，这两种拍卖带给卖者的期望收人相等。 现在我们终于可以给出一个重要结果了，这就是一件不可分割的商品拍卖情形下的 收入等价定理（revenueequivalencetheorem）。对于这个定理，我们将给出非正式证 明。这个主题上的更多内容可以参考McAfeeandMcMillan[4]以及VijayKrishna[1]， 本节材料就来自这两份文献。 博弈论与机制 20.4收入等价定理 制 这个重要定理表明，在基准模型下，对于一件不可分割的商品的情形，四种经典拍 设计 卖带给卖者的收人是相等的。 口基准模型 收人等价定理有四个重要假设：（1）竞标人都是风险中性的；（2）竞标人有独立的 私人价值；（3）竞标人之间是对称的；（4）支付仅取决于竞标人自已的报价。分别介绍 如下。 （1）竞标人的风险中性。 基准模型假设所有竞标人都是风险中性的。这立即意味着每个竞标人的效用函数关 于自己持有的货币都是线性的。更多细节可参考8.6节。 （2）独立私人价值模型。 在独立私人价值模型中，每个竞标人准确知道他自己对拍卖物的评价。然而，每个 竞标人可能不知道其他竞标人的评价。每个竞标人认为任何其他竞标人的评价都抽自某 个已知的概率分布。另外，每个竞标人i知道其他竞标人和卖者将他（竞标人i）的评 价视为抽自某个已知的概率分布。正式地，与以前一样，令N={1，2，，n）为竞标 人集合。独立私人价值这个假设事先设定了概率分布，竞标人i（iEN）从Φ：中抽 取他的评价。竞标人i知道自已的评价，但所有其他竞标人和卖者仅知道概率分布

①。各个竞标人的概率分布互相独立。 这个假设的一个适当例子是一幅罕见油画的拍卖，竞标人是消费者，他们购买油画 的目的是欣赏而不是转售。 与上面模型不同的另外一种常见模型是共同价值模型（commonvaluemodel）。在这 里，如果V是拍卖物的未被观知的真实价值，那么竞标人的感知价值u（i=1，"，n）独 立抽自某个概率分布H(v|V)。所有竞标人知道概率分布H。这里的一个例子是一幅罕 见油画的拍卖，竞标人购买的目的是转售。这幅画有一个目标价值，即它的市场价格。 然而，没人知道它真实的市场价格。如果不同的竞标人对此获知的信息不同，那么他们 对油画的实际价值就有不同的猜测。 假设竞标人1设法知道了某个竞标人对油画的评价。在共同价值模型情形下，这为竞 标人1了解拍卖物的潜在真实价值提供了有用信息，因此竞标人1有可能改变自己的评 价。在独立私人价值模型下，竞标人对油画有准确评价，即使他知道了其他投标人的评 价，他也不会改变自己的评价。然而，出于策略上的考虑，他可能会改变自己的报价。 现实拍卖情形可能含有独立私人价值模型的某些方面，也含有共同价值模型的某些 方面。然而，在我们的基准模型中，我们使用独立私人价值模型。 （3）对称性。 对称性假设意味着所有投标人的评价集都是相同的，而且他们的评价抽自相同的概 率分布函数Φ。也就是说，=2==①=Φ。 （4）支付仅取决于报价。 基准模型假设获胜者支付的钱数仅取决于报价。 第 定理20.2（收入等价定理）某个卖者想通过拍卖卖掉一件不可分割的商品，有n个 章 竞标人（买者）。在基准模型（竞标人都是风险中性的；竞标人有独立私人价值；竞标人 拍 之间是对称的；获胜者支付的钱数仅取决于报价）下，所有四种基本拍卖类型（英国式拍 卖、荷兰式拍卖、第一价格密封拍卖、第二价格密封拍卖）带给卖者的期望收入相等。 卖 注释这个结果似乎有些不符合直觉。例如，在第一价格密封拍卖下，卖者得到的 钱数等于最高报价，而在第二价格密封拍卖下，卖者得到的钱数等于第二高的报价，这 难道不意味着第一价格密封拍卖带来的收人比第二价格密封拍卖更大吗？然而，注意， 在不同拍卖情形下，竞标人的行动也不同。特别地，与第一价格密封拍卖相比，在第二 价格密封拍卖下，竞标人的报价更加激进。 证明：证明分为三个部分。在第一部分，我们证明第一价格密封拍卖均衡和第二价 格密封拍卖均衡带给卖者的收人相等。在第二部分，我们证明荷兰式拍卖和第一价格密 封拍卖带给卖者的收入相等。在第三部分，我们证明英国式拍卖和第二价格密封拍卖带 给卖者的收人相等。我们提醒读者注意，我们的证明基于直觉但不是正式的；这个结果 的严格证明，读者可以参考文献[1]。 口第一部分：第一价格密封拍卖与第二价格密封拍卖的收入等价性 我们已经证明第一价格密封拍卖和第二价格密封拍卖满足定理20.1的条件。显然， 这两种拍卖带给卖者的收入相等。事实上，可以证明，在任何对称拍卖环境下（各个竞 标人的评价独立地抽自相同分布），第一价格密封拍卖的任何贝叶斯纳什均衡以及第二

价格密封拍卖的弱优势策略均衡都满足定理20.1的条件。 口第二部分：荷兰式拍卖与第一价格密封拍卖的收入等价性 为了看清这一点，假设一个竞标人面对着这两种拍卖。在每种情形下，他必须在不 知道其他竞标人的评价条件下选择自己的报价。如果他获胜，他支付的钱数等于他自己 的报价。不管我们使用基准模型中的哪个假设，这个结果都为真。我们指出，在这两种 拍卖情形下，潜在的贝叶斯博弈均衡是一个贝叶斯纳什均衡。 口第三部分：英国式拍卖与第二价格密封拍卖的收入等价性 英国式拍卖和第二价密封格拍卖的结果都满足弱优势策略均衡。也就是说，每个竞 标人有明确定义的最优反应（最优报价），无论他认为其他竞标人报价有多高。在第二 价格密封拍卖下，弱优势策略是报告自已的真实评价。在英国式拍卖下，弱优势策略是 持续竞价直到价格等于竞标人自已的评价。 首先分析英国式拍卖。注意，如果当前价格大于竞标人i的评价，那么竞标人不会 继续竞价而是选择退出。随着价格不断抬高，竞标人不断退出，直到市场中只剩下两个 竞标人（不妨称为1和2）。当价格大于竞标人2的评价时，他退出。这样，市场中只剩 下竞标人1，竞标人1获胜。注意，获胜者的评价在所有竞标人中是最高的，而且尽管 卖者有垄断势力，获胜者仍然得到了一些收益。只有获胜者自己知道他得到了多少收 益，这是因为只有他知道自已的评价。假设n个竞标人的评价分别为v(1)，U2)，， 博弈论与机制 U(n)。由于竞标人是对称的，这些评价独立抽自相同的概率分布；不失一般性，假设这 些评价按降序排列，即v(1)>U(2)>">U(n)。这样，获胜者（竞标人1）得到的收益为 U（1）—U(2） 设计 接下来，我们分析第二价格密封拍卖。在第二价格拍密封卖下，竞标人对报价的选 择决定了他是否能获胜；如果他获胜，他支付的钱数不受他自已的控制。我们已经证 明，每个竞标人的均衡策略是如实报告自己的评价。获胜者支付的钱数等于第二高的报 价（也是第二高的评价，因为每个人都如实报价）。因此，英国式拍卖与第二价格密封 拍卖带给卖者的收入相等。 综合以上三个部分，可知四种基本拍卖类型（英国式拍卖、荷兰式拍卖、第一价格 密封拍卖、第二价格密封拍卖）带给卖者的期望收入相等。 一些观察 我们现在对收入等价定理做出一些重要观察。 口期望收入相等 这个定理不意味着四种拍卖的结果总是相同的。它们仅在期望意义上相等。注意， 在英国式拍卖或第二价格密封拍卖中，价格正好等于伴随第二高评价的竞标人对拍卖物 的评价。在荷兰式拍卖或第一价格密封拍卖中，价格是第二高评价的条件期望（以获胜 者自己的评价为条件）。上面两个价格仅在偶然情形下相等，然而，它们的期望相等。

口收入的方差 收人等价定理没有规定在什么环境下应该使用这四种拍卖中的哪一种。当我们放松 基准模型的假设时，特定拍卖形式将胜出。 文献已经证明，与荷兰式拍卖或第一价格密封拍卖相比，英国式拍卖或第二价格密 封拍卖的收人方差更小。因此，如果卖者是厌恶风险的，他应该选择英国式拍卖或第二 价格密封拍卖，而不是荷兰式拍卖或第一价格密封拍卖。 口报价复杂性 在英国式拍卖和第二价格密封拍卖中，报价策略非常简单。在英国式拍卖中，竞标 人持续竞价直到价格等于自已的评价。在第二价格密封拍卖中，他递交的密封报价等于 他自已的评价。另一方面，在荷兰式拍卖与第一价格密封拍卖中，报价逻辑非常复杂。 在这里，竞标人的报价稍微小于自已的真实评价。至于小多少，这取决于其他竞标人评 价的概率分布以及参与竞标的人数。找到纳什均衡报价不是一个简单的计算问题。 20.5组合拍卖 组合拍卖是指报价对应由不同种商品组成的商品束（bundles）。在前向组合拍卖 第 （forwardcombinatorialauction）中，卖者销售一组不同商品；买者想买其中若干种商 品。在后向组合拍卖（reversecombinatorialauction）中，买者采购一组不同商品；卖 章 者提供其中若干种商品。目前已有大量关于组合拍卖的文献，例如Cramton，Shoham 拍 and Steinberg[3] 我们用例子说明一个简单的组合拍卖。 卖 口广义维克瑞拍卖 广义维克瑞拍卖（generalizedVickreyauction）指将克拉克机制应用到组合拍卖的 情形。令一个卖者想卖商品A和B。假设有三个买者（智能体）{1，2，3}。我们用A、 B和AB分别表示子集{A}、（B}以及{A，B)，尽管这么做有些滥用符号。这些子集 称为商品组合或商品束。假设智能体对商品束的评价如表20一1所示。 表20-1 智能体对商品束的评价：情形1 A B AB 智能体1 智能体2 智能体3 * 在表20一1中，每个星号元素表示智能体对此商品束不感兴趣。由该表可知，智能 体1对商品束AB的评价为10，对商品束A与商品束B没有任何评价。智能体2仅对 商品束A感兴趣，他对此的评价为5。智能体3仅对商品束B感兴趣，他对该商品束的

评价为5。 如果对此情形使用克拉克机制，那么智能体的报价将与其评价相同，原因在于克拉 克机制的优势策略激励相容性。在这里，两个配置有配置效率：（1）将商品束AB配置 给智能体1；（2）将商品束A配置给智能体2，并且将商品束B配置给智能体3。对于 这两个配置，每个配置的总价值都为10。假设我们选择配置（2），即将A配置给智能 体2，将B配置给智能体3。为了计算智能体2与3支付的钱数，我们需要使用克拉克 支付规则。对此，我们考察当智能体2与3各自不出现时的后果。如果智能体2不出 现，那么配置将把商品束AB给智能体1，此时总价值为10。因此，智能体2得到的维 克瑞折扣为10一10=0（关于维克瑞折扣的定义，请参见18.4节例18.3），这意味着智 能体2支付的钱数为5十0=5。类似地，智能体3得到的维克瑞折扣也为零，智能体3 支付的钱数也为5。卖者得到的收人为5十5=10。即使我们选择上面的配置（1）（即将 商品束AB配置给智能体1），卖者得到的总收入仍然为10。在这种情形下，卖者能够 撰取所有消费者剩余。 作为对照，我们考察当智能体的评价如表20一2所示时的结果。在这种情形下，获 胜配置为：把商品束A给智能体2，而且把商品束B给智能体3。这个配置产生的总价 值为20。如果智能体2不出现，那么配置将为把商品束AB给智能体1，该配置的总价 值为10。类似地，如果智能体3不出现，那么配置将是把商品束AB给智能体1，该配 置产生的总价值为10。这意味着智能体2与3得到的维克瑞折扣分别为10，这又意味 着智能体2与3支付的钱数分别为0！这种情形代表着为了保证配置效率与优势策略激 博 励相容，卖者最终得到的收人为零。情形还可以更糟：如果智能体2与3都是同一个智 弈论 能体使用的假名字，那么这个拍卖本身被严重操纵了！ 与机 表20-2 智能体对商品束的评价：情形2 制 设计 A B AB 智能体1 智能体2 智能体3 我们现在考察第三种情形，此时智能体的评价如表20一3所示。在这里，配置为把 商品束AB给智能体1，从而产生的总价值为10。如果智能体1不出现，配置将是把商 品束A给智能体2而且把商品束B给智能体3，这导致了总价值为4。因此，智能体1 得到的维克瑞折扣为10一4=6，智能体1支付的钱数为4。卖者的收人也为4。将这个 情形与情形2相比，在情形2下，竞标人2与3的评价都更高，但他们能以零代价获得 商品束。这表明广义维克瑞机制不能防御竞标人合谋（在这种情形下，竞标人2与3可 以合谋，从而阻止将商品束给智能体1，也将卖者的收入锐减为零）。 表20-3 智能体对商品束的评价：情形3 A B AB 智能体1 智能体2 智能体3

可以证明广义维克瑞拍卖有下列合意性质：优势策略激励相容、配置效率、弱预算 平衡以及个体理性。然而，一般来说，将克拉克机制运用到组合拍卖，这涉及求解 （n十1）个获胜者确定问题，其中n是智能体个数。这些问题通常是NP-hard类。 口组合拍卖：进一步考察 组合拍卖已被广泛应用到很多网络经济情形。关于组合拍卖比较全面的信息，读者 可以参考Cramton，Shoham，andSteinberyL3]。组合拍卖领域也有很多综述文章，例 如 de Vries and Vohra7]，Pekec and Rothkopf8]，Narahari and Dayama[1o]，以及 Blumrosen and Nisan[11] 。 20.6小结与参考文献 在本章，我们考察了拍卖和拍卖设计的各个层面。具体地说，我们讨论了以下 主题。 ·拍卖的合意性质，包括：激励相容、配置效率或福利最大化、预算平衡、个体理 性、收入最大化（或成本最小化）等。 ·拍卖类型众多，例如拍卖物可以为：一种商品且只有一个单位（数量）；一种商 品且有多个单位；多种商品且每种商品只有一个单位；多种商品且每种商品有多个单 位；多个属性，等等。 第 ·对于拍卖一件不可分割的商品，有四种经典拍卖可供考虑：英国式拍卖、荷兰式 章 拍卖、第一价格密封拍卖、第二价格密封拍卖（维克瑞拍卖）。收入等价定理表明在基 拍 准模型中，这四种拍卖带给卖者的期望收人相等。对于收入等价定理的更多细节，读者 可以参考Myerson[12]、McAfeeandMcMillan[4]、Klemperer[13]等论文，以及Mil- 卖 grom[2]、Krishna[1]等书籍。 ·在组合拍卖中，拍卖物为不同种商品组成的商品束。广义维克瑞拍卖在本质上就 是将克拉克机制运用于组合拍卖。 在这里，我们必须指出本章仅讨论了关于拍卖的少数几个重要结果。事实上，我们 仅介绍了有限几种拍卖。对于拍卖的更多细节，已有很优秀的综述文章[4，5，6］和 书籍[1，2，3]。近期综述文章主要关注组合拍卖。[7,8,9,10]采购拍卖在企业环境下非 常流行，这方面的综述文章和案例研究可参考文献[14]。 在下一章（第21章），我们讨论最优拍卖，它在激励相容与个体理性约束条件下， 使得收入最大化或成本最小化。在第22章，我们将给出网络赞助搜索拍卖的案例研究， 并且考察机制设计在其中扮演的角色。 口参考文献 [1]Vijay Krishna.Auction Theory.Academic Press,San Diego,California, USA，2002. [2]Paul Milgrom.PuttingAuction Theoryto Work.CambridgeUniversity

Press,Cambridge,UK,2004. [3]P.Cramton,Y.Shoham,and R.Steinberg (Editors).Combinatorial Auc- tions.TheMIT Press,Cambridge,Massachusetts,2005 [4]R.P.McAfee and J.McMillan.“Auctions and bidding”.In:Journal ofEco nomicLiterature25（2)（1987)，pp.699-738. [5]P.Milgrom.“Auctions andbidding:Aprimer”.In:JournalofEconomic Perspectives3(3)(1989),pp.3-22. [6]E.Wolfstetter.“Auctions:An introduction”.In:Economic Surveys 10 (1996)，pp.367-421, [7] S. de Vries and R. V. Vohra.“Combinatorial auctions:A survey".In:IN- FORMSJournalofComputing15（1)（2003)，pp.284-309. [8]A.Pekec and M.H.Rothkopf.“Combinatorial auction design”.In:Manage ment Science49(2003)，pp.1485-1503. [9]J.R.Kalagnanam and D. C.Parkes.“Auctions,bidding, and exchange de- sign".In:HandbookofQuantitativeSupplyChainAnalysis:Modelingin theE— BusinessEra.Ed.byD.Simchi Levi,S.D.Wu,and Z.J.Shen.Kluwer Academic Publishers,NewYork,2005. [10]Y.Narahari and P.Dayama.“Combinatorial auctions for electronicbusiness”. In:Sadhana-IndianAcademyProceedingsinEngineering Sciences30（3)(2003), 博奔论与机制设计 pp.179-212. [11]L.Blumrosen and N.Nisan.“Combinatorial auctions”.In:Algorithmic Game Theory.Ed.byNoam Nisan,TimRoughgarden,EvaTardos,andVijayVaz irani.CambridgeUniversityPress,2007,pp.267-300. [12]Roger B.Myerson.“Optimal auction design".In:Mathematics of Opera tionsResearch 6(1)(1981)，pp.58-73. [13]P.Klemperer.“Why every economist should learn some auction theory”.In: AduancesinEconomicsandEconometrics:InvitedLecturesto8thWorldCongressof theEconometricSociety.Ed.byM.Dewatripont,L.Hansen,and S.Turnovsky.Cam- bridge UniversityPress,Cambridge,UK，2003. [14]CharlesH.RosaDevadattaKulkarniPankaj Dayama T.S.ChandrashekarY.Nara hari and Jeffrey D. Tew.“Auction based mechanisms for electronic procurement”.In:IEEE Transactions on Automation Science andEngineering 4(3）(2006)，pp.297-321. 20.7习题 （1）（伴随预算的第二价格密封拍卖）假设卖者打算使用第二价格密封拍卖卖掉一 件不可分割的商品。假设每个竞标人i对拍卖物的评价为：>0，预算为c>0。如果某 个竞标人获胜而且他支付的钱数大于他的预算，那么他可以选择退出，但要为此支付罚

金∈>0。计算每个竞标人i的报价使其成为他的弱优势策略。 （2）对于多个单位（数量）的一种商品，有两个卖者智能体和两个买者智能体。卖 者制定了边际递减的分段常数型要价，买者制定了边际递增的分段常数型报价。我们的 目标是使得总剩余（总收人减去总支出）最大。两个卖者的要价分别为 卖者1的要价：（（1-50，10），（51-150，8），（151-200，6））。 （它们的意思是，对于50单位以内的商品，每单位10元；对于51～150单位的商品， 每单位8元；对于151～200单位的商品，每单位6元。以下数字的意思类推。） 卖者2的要价：（（1-50，12），（51-100，10），（101-200，6））。 两个买者的报价分别为 买者1的报价：（（1-50，12），（51-100，11），（101-150，10））； 买者2的报价：（（1-75，12），（76-150，10））。 假设这个交易使用克拉克机制。对于这个交易问题： ·对于给定的报价，求一个剩余最大化的配置，并计算剩余。 ·两个买者的支付分别为多少？ ·两个卖者的收入分别为多少？ （3）某个买者使用广义维克瑞机制采购商品束（A，B，C，D，E>。下列是5个卖 者的报价： ·卖者1：（A，20)，（B，30)，（AB，45）； 第 ·卖者2：（B，25)，（C，35），（BC，50)； 章 ·卖者3：（C，30)，（D，40)，（CD，60)； 拍 ·卖者4:（D，35），（E，45)，（DE，70)； ·卖者5：（E，40)，（A，15)，（EA，50)。 卖 假设这里使用XOR报价（也就是说，任何卖者都至少有一个报价被选中）。计算配 置以及获胜竞标人的收入。这个计算是个体理性的吗？为什么？ （4）将广义维克瑞机制运用到下列组合拍卖情形。这里有三个竞标人和两种商品。 评价矩阵如下： (1} {2} {1，2} 竞标人1 竞标人2 竞标人3 （5）（编程题）建立基于网络的拍卖所来实施各种拍卖。这样的平台能够进行各种 拍卖机制的实验。