分别销售物品
回顾下在一个组合拍卖中有个投标人和个不一样的物品，其中投标人对每一个物品组合都有一个私人价值。除非很小，否则让每一个投标人都上报个标价是荒唐的。因此，第一次在这门课程中，我们没有办法只能设计和分析非直接的机制，特别是基于“需要知道”的向投标人询问相关价值信息的迭代机制。这意味着既放弃DSIC保证，又放弃完全的福利最大化――我们会怀念这些性质，但是我们别无选择。
有哪些其他机制我们可以尝试？考虑到我们需要销售多个物品，并且不想获取每一种物品组合的价值，最简单的机制是尝试分别销售这些商品，并对每一个物品都使用某种单物品拍卖。如果需要的话我们一定可以实施这样的拍卖――我们需要的是每一个投标人对每一个物品的出价，而这毫无疑问是最少的。
我们很快就会深入具体的拍卖形式，但是首先让我们提一个更基本的问题：分别销售物品是否能行，甚至是在理论上？对这个问题有很多优雅和清楚的理论，其中的一些结论我们以后会讨论。到目前为止，我们总结下这种理论中的主要结论。
对组合拍卖有一种重要的二分原则：一类拍卖中物品相互是替代品(substitutes)，而另一类拍卖中物品相互是互补品(complements)――前者无论从理论上还是实践上都比后者容易得多。粗略来说，物品是替代品指的是你会得到逐渐缩小的回报――有了一个物品只会使其他物品变得更没有价值。举例而言，对两个物品和，替代条件意味着。在一个频谱拍卖中，同一个区域中相同频率范围大小的两个许可证通常是替代品。理论表明当物品（大部分）是替代品时分别销售物品有可能工作得很好。首先，当物品是替代品并且真实价值已知时，福利最大化是一个计算量上可处理的问题。其次，当物品是互补品时，上一讲和练习中指出的VCG机制不好的性质都会消失，从而拓展了单物品情况。但是即使互补商品是“简单”的情况，我们会看到当试图分别销售它们时很容易搞砸。
当物品之间有协同效应时，它们是互补品，因而拥有了一个物品会使其他物品更加有价值。对于两个物品和，这意味着。在无线频谱拍卖中互补品很常见，因为一些投标人想要一些无论在地理区域还是频率范围上邻近的许可证。由于互补品的存在，福利最大化（没有激励约束）就已经是一个非常难的问题；见习题5。我们不能指望像分别的单物品拍卖这样简单的拍卖形式能够在这样的环境中工作得很好。
频谱拍卖中的物品，以及大部分现实场景中的组合拍卖，都是替代品和互补品的混合。如果问题是“大部分替代品”，那么如果合理实施的话，分别的单物品拍卖已经能做得很好。如果不行，那么需要加入新的想法，具体见部分3。
同时的上升拍卖
有很多方法来组织分别的单物品拍卖。接下来我们会讨论两种在实践中很重要的设计结果，更多的细节参考Cramton[1]和Milgrom[2]的第1章。
新手错误#1: 顺序地进行单物品拍卖，每次出售一个物品。
为了看出为什么顺序地进行拍卖很可能是一个坏的想法，考虑最简单的相同物品的情况，其中每一个投标人最多只想要一个物品。这个问题能够简单地通过一个一次性分配所有物品的拍卖解决（例如，将Vickrey拍卖扩展到这个场景）。假设反过来我们采用一连串单物品拍卖。具体来说，考虑两个相同的物品，通过连续的Vickrey拍卖出售，并且你是一个有着非常高价值的投标人——你希望赢得所有你参与的拍卖。你应该怎么做？首先，假设其他人直截了当地出价，指的是，如果他们尚未赢得一个物品，那么他们会参与下一轮拍卖并且按真实价值报价。如果你参与了第一次拍卖，你会赢并且付第二高的价值。如果你跳过第一次的拍卖，有第二高价值的投标人会在第一次拍卖中获胜并且消失，从而使得你在第二次拍卖时获胜的价格变为原来第三高的价值。当然，我们现在意识到了在一连串Vickrey拍卖中让投标人直截了当地报价并不是一个占优策略，我们必须搞清楚他们可能会怎样策略化。总而言之，在一连串Vickrey拍卖中很难科学地报价，因为你必须得猜未来的拍卖的期望售价，而这反过来使得拍卖的结果很难预测，并有可能导致低的福利和收入。
在2000年的3月份，瑞士通过一连串的Vickrey拍卖卖掉了3段频谱。前两个拍卖售出的是相同的物品，20Mhz频段，并且分别卖出了一亿两千一百万瑞士法郎和一亿三千四百万瑞士法郎。这其中已经有了对于相同物品而言人们所不希望看到的价格差异。但是更奇怪的事情发生在第三次拍卖中，一个更宽的56MHz频段，售价居然只有五千五百万！报价肯定远远没有到达均衡，并且这场拍卖获得的福利和收入都令人怀疑。
上面的讨论和历史教训都建议对多个物品同时采用单物品拍卖，而不是连续地。但是每一个单物品拍卖的拍卖形式还有待探究。
新手错误#2: 用密封报价的单物品拍卖。
在1990年，新西兰政府利用同时的（密封报价的）Vickrey拍卖出售在电视广播中使用的基本相同的许可证。再一次地，投标人很难搞清楚在这样的拍卖中应该如何出价。举例而言，想象一下这里有10个许可证，并且你想要其中的一个（但是不想多要），你应该如何出价？一种合理的策略是选许可证中的一个（比如说随机挑选），然后冲着它去竞拍。另一种策略是在多个许可证上不那么激进地竞争，希望能在一个特价上获得一个许可证，同时也不会赢得太多你不想要的多余的许可证。困难在于赢得过多许可证的风险和赢得过少的风险的权衡上。
在一个同时的密封投标的拍卖中报价和协同的困难使得拍卖非常容易滑入低福利和低收入的结果。举例来说，假设有三个投标人和两个相同的物品，并且每个投标人都只想要一个物品。Vickrey拍卖的明显扩展是将两个许可证卖给拥有最高价值的投标人，每一个许可证都收取等于最低价值的费用。在一个同时的密封投标拍卖中，如果每一个投标人的目标都只是一个许可证，那么有一个许可证很可能只有一个投标人，因此很可能被免费送出去（或者更一般地，以保留价格出售）。
1990年新西兰拍卖的收入只有三千六百万美元，相比预计的两亿五千万美元简直微不足道。相对而言，过去20年的大部分频谱拍卖都达到或超过了预期收入。在某一个许可证上，最高的报价是100000美元而第二高的报价（或出售价格）只有6美元！在另一个上，最高出价是七百万美元而第二高的只有5000美元。雪上加霜的是，公众能够看到最高出价，也就能够看出有多少钱被剩在了桌上！之后的另一次新西兰的拍卖保留了同时的密封报价形式，但转而采用首价拍卖——这种改变很可能无法阻止上一次拍卖中的不协调和随之而来的福利及收入损失，但是它使得这些损失对于公众而言不那么明显。
同时的上升拍卖(SAAs)构成了过去20年大部分频谱拍卖的基础。我们首先讨论基本形式，然后是这些年里加入的额外的卖点。从概念上讲，SAAs类似在一个房间里同时进行的一系列单物品英式拍卖，每一个物品都有一个拍卖人。更准确地，在每一轮中，每一个投标人都可以在他想要的物品的子集上提一个新的报价，只需要遵循一个活动规则(activity rule)。这个活动规则强制所有投标人从一开始就参与拍卖，并且对下面要讨论的价格发现有所贡献。一个活动规则的细节可以很复杂，但是要旨是要求一个投标人进行投标的物品数随着价格的上升只会下降。一般而言，高的报价和投标人是大家都知道的——尽管这可能会导致发信号或报复性报价（回顾上一讲中USWest和McLeod竞争的例子）。当第一次没有新的报价时，整个拍卖结束。
SAAs比连续的或密封报价的拍卖要好的主要原因是价格发现(price discovery)。随着投标人获得关于许可证可能的出售价格更好的信息，他可以实施中途的纠正——放弃竞争比预期要激烈的许可证，抢购没有预料到的特价，并且思考重新组合怎样的许可证集合。这种形式很好地解决了困扰同时的密封报价拍卖的不协调问题。举例而言，假设有两个相同的物品和三个投标人。每一轮，都会有一个投标人在两场拍卖中都输掉。当他再重新参与拍卖时，对现在更便宜的物品进行竞拍是合理的，而这会使得两个物品的价格大致相同。
SAA形式的另一个好处是投标人只需要在一个需要知道的基础上决定价值。我们假设了在拍卖开始时投标人是知道价值的，但是在实践中决定一系列物品的价值代价非常高，涉及到了研究、专家建议等等。与直接显示拍卖形成鲜明对比的是，一个投标人常常可以在一个SAA中对大部分价值仅仅拥有一个粗略的估计，而对重要的集合才有准确的估计。
一般而言，SAAs被认为表现很好，这意味着他们能取得好的福利和收入。这个断言在一场拍卖之后很难验证，因为一些价值仍然未知并且报价是不完整的，还有可能是不真实的。然而，有一系列“理性检查”支持了好的拍卖表现。首先，拍卖后应该没有，或很少有物品的重新出售，而且任何重新出售都应该在一个与拍卖的出售价可比的价格上进行。这意味着投机者并没有能够在这场拍卖中起到巨大作用。其次，类似的物品应该售出了类似的价格（作为对比，回想瑞士和新西兰的拍卖）。第三，收入应该达到或超过预期。第四，应该有价格发现的证据——举例而言，在拍卖中途的价格和临时的获胜者应该跟最终的售价和获胜者高度相关。最后，投标人组织的集合应该是合理的，例如相邻地区或频段的一系列许可证。
SAAs有两个大的漏洞。第一个问题是需求减少(demand reduction)。即使当物品是替代品时，这个问题也很明显。当一个投标人索要比他真正想要的更少的物品时需求减少就会发生。投标人会降低竞争，从而降低他得到物品时付出的价格。
为了说明，假设有两个相同的物品和两个投标人。第一个投标人对两个物品中的一个的价值为10，并对这两个物品的价值为20。第二个投标人对两个物品中的一个的价值为8，并且不想要两个物品（即，他对两个物品的价值仍是8）。将两个物品都给第一个投标人会最大化福利为20。VCG机制在这个例子中收入为8。因此，投标人2只有当两个物品的价格都至少为8时才会退出。如果投标人固执地坚持要赢得两个物品，他的效用是20-16=4。如果，换种情况，投标人的目标仅仅是一个物品，那么每个投标人会以接近零的价格获得两个物品中的一个。投标人1的效用会接近10。在这个例子中，相对VCG机制的结果，需求减少导致了福利和收入的损失。在很多频谱拍卖中有需求减少的大量证据。
SAAs的第二个大问题，当物品是互补品时很明显（出现在许多频谱拍卖中），是曝光问题(exposure problem)。作为一个例子，考虑两个投标人和两个不一样的物品。投标人1只想同时要这两个物品——它们对投标人而言是互补的物品——并且他对它们的价值是100（否则是0）。投标人2愿意为任一个物品付出75。VCG机制会将两个物品都给投标人以获得100的福利，并产生75的收入。然而，在SAA中，在两个物品的价格都到达75之前投标人2不会退出。投标人1处在一个不会获胜的状况中：为了获得两个物品他必须付出150，而这超过了他的价值。而以一个非平凡的价格赢得一个物品可能会更糟。另一方面，如果投标人2对每个物品的价值只有40，那么投标人应该付诸全力去赢得两个物品。但是投标人1要如何知道哪种场景更接近现实呢？曝光问题使得对一个物品是互补品的投标人而言在SAA中竞拍变得特别困难，而且它常常导致这样的投标人采用风险规避和试探性的报价。
额外的卖点
一个困难和富有争议的问题是要不要利用包裹拍卖(package bidding)来增强基本的SAA形式——除了单个的物品，可以对物品的集合报价——并且，如果要的话，如何做。允许包裹拍卖的主要原因是缓和当物品是互补品时的曝光问题，使得想要物品集合的投标人可以激进地竞标它们。也有一些场景中，包裹拍卖可以消除需求减少的动机。
传统的视角，一直统治实践到相对比较近的现在，认为包裹拍卖增加了一个相当起作用的拍卖形式的复杂度，并且有可能带来更多的坏处而不是好处。仅仅在过去5至10年间，包裹拍卖的有限形式被包含在频谱拍卖设计中。
一种设计途径是在SAA中投标人可以对他们想要的任何物品子集提交包裹报价后增加一个额外的“代理”轮，遵循一个活动规则的前提下；细节见Ausubel和Milgrom[3]。这些包裹报价相互之间竞争，也会与来自拍卖的SAA阶段的对单个物品的获胜报价竞争。最终的分配是由一个福利最大化的计算决定，计算时将报价视为真实的价值。这种途径的最大问题是计算最后的价格是富有技巧性的。这里不使用VCG费用规则是因为它不好的收入和激励性质（见第7讲和练习）。一种更加激进的费用规则，虽然不满足DSIC但有其他好的激励性质，在这里被使用。在这种相对复杂的价格规则下的投标人的典型行为并没有被完全理解。
另一种途径是提前制定一个有限的可允许的包裹报价的集合，而不是允许投标人提出他们自己的。理想情况下，提前制定的包裹报价应该跟投标人真正想要的高度一致，又足够的结构化使得合理的简单分配和支付规则存在。分层包裹——举例而言，允许对单个许可证，或者地区范围的许可证打包，或者全国范围的许可证打包报价——是这种设计途径的一个好的切入点[4]。提前制定的包裹报价的最大问题是当它们和投标人的目标匹配很差时会带来更多的坏处而不是好处。举例而言，想象一下你是一个想要物品ABCD的投标人，但是可得的包裹是ABEF和CDHI——你的报价策略是什么？
研究前沿
我们已经讨论了无线频谱拍卖的现有结果，让我们以一个未来的案例作总结：一个即将到来的FCC双重拍卖，有可能发生在2014年。拍卖形式仍在讨论中，这一部分只是作者对于被采用的形式的最好猜测。
无线频谱并不是伸手可得的。在目前这个阶段，给某人一个新的频谱分配往往要求讲频谱从另一个人那里拿过来。很快地，FCC正计划这样做，利用一个反向拍卖从电视广播公司那里将频谱释放出来，然后利用一个正向拍卖将频谱重新卖给能够将频谱用于更有价值的目的的公司。正向拍卖很可能通过一个改进后的SAA实施，这同往常一样；反向拍卖完全是新的。
进一步地，FCC会重组剩下的广播公司使得释放出的频率是连续的。举例来说，它可能会在全国范围内使用38到51之间的UHF信道的广播公司中买下一些，然后对剩下的广播公司进行重新分配使得它们的信道在38到45之间，从而将46至51之间的频段留给新用户（见图1）。
图1：在一些电视广播公司的频段被买下后，剩下的公司会通过信道重分配使得一段连续的频谱被释放出来。
经过一个非常酷的发展后，现在反向拍卖形式的领跑者是一种贪心的近似福利最大化分配规则，跟我们在课件4中讨论过的背包拍卖并不是那么不一样。在所提的模型中，每个投标人（广播电视公司）对于它的广播许可证有一个私人价值。也就是说，是买下的“最低可接受出价”。这种单变量模型假设了每一个电视广播站都是由不同的策略性代理人拥有。这种假设在实践中并不总是正确的，但它使得模型更加容易分析。令表示投标人的集合，集合代表获胜的投标人——这里“获胜”指的是被买下——是可行的，如果剩下的投标人能够在目标频段上（例如，38-45的频段）上重新组合。一个有趣的问题是如何设置这个目标。目标频段越大，反向拍卖中单位量的频谱的费用越大，同时前向拍卖中单位量的频谱的收入越小，因为增加供给会降低价格。一个理想的目标应该使得前向和反向拍卖中的频谱单价相等——或者可能让前向拍卖中的价格更高一点，从而拍卖的费用能够通过拍卖的净营收抵消。一种被严肃讨论的途径是利用所提出的反向拍卖来估计整个供应曲线——对每一个可能目标频段的获取费用——并据此在前向拍卖中匹配供给和需求。举例来说，如果，那么所有的投标人都被买下了并且整个频段都被释放了，因此肯定是可行的。当时，没有频段被释放，是一个不可行的结果。检查一个给定的集合是否可行是一个中等规模的NP难问题——根本上是一个图染色问题，因为在重叠地理区域上的两个电视广播站并不能被分配相同的或邻近的信道——因此解决它需要现有的算法技术。在这个课件写作时，SAT程序和整数规划程序正在相互竞争，想要尽可能快地解决这些“可行性检查”问题。
我们对于所提出的分配规则给出一个直接显示的描述，尽管它们可以（也很可能会）通过一个有递减的、投标人指明价格的迭代的拍卖实施。递减的实施比密封报价更好是因为从经验上讲，投标人觉得它更容易。分配规则从一个平凡的可行集开始（对于所有投标人），然后从现在的可行集里反复删除投标人直到剩下一个最小可行集。一种贪心的打分规则用来选择每一轮中去掉哪一个投标人。你可以称之为“反向贪心算法”，因为它是从整个集合开始删除投标人，而不像前向贪心算法中从空集逐步添加投标人（对比讲义4中的背包拍卖）。Milgrom和Segal[5]称其为延迟分配规则(deferred allocation rules)。
- 令。【开始是可行的。】
- 当存在一个使得仍保持可行：\ \indent (*)从中删掉某一个这样的。【即，不会被买下。】
- 返回。
(*)那一步很明显没有定义好，很容易想到各种值得尝试的启发式方法，例如删掉报价最高的投标人（即，最不愿意被买下的），有最高报价的投标人等等。贪心规则的准确选取很可能通过合成数据上不同规则得到的福利得到指导。
如果我们通过一个得分函数来实施(*)，（满足可行的前提下）删除得分最大的投标人，并且如果这个得分函数随着投标人的报价递增，且与其他活跃用户的报价独立，那么这个延迟分配规则是单调的（报价更低只会让你获胜）。见练习题#4。根据Myerson引理，支付关键报价——一个赢了的投标人所能给出的保持被买下结果的最大报价——产生一个DSIC拍卖。
值得注意的是，延迟分配规则除了DSIC以外还有一系列好的激励性质，而这些性质在与它们类似的前向贪心规则中没有[5]；另外也可以参考问题集#3。
参考文献
[1] Peter Cramton. Simultaneous ascending auctions. Wiley Encyclopedia of Operations Research and Management Science, 2004.
[2] Paul Robert Milgrom. Putting auction theory to work. Cambridge University Press, 2004.
[3] Lawrence M Ausubel and Paul Milgrom. Ascending proxy auctions. Combinatorial auctions, pages 79-98, 2006.
[4] Jacob K Goeree and Charles A Holt. Hierarchical package bidding: A paper & pencil combinatorial auction. Games and Economic Behavior, 70(1):146-169, 2010.
[5] Paul Milgrom and Ilya Segal. Deferred-acceptance heuristic auctions. Technical report, Working paper, August, 2013.