价格的发现

第4章

延迟接受拍卖和近似互替品

维克里拍卖是唯一能够计算和选出有效率配置的反谋略直言机制。尽管有这个不容忽视的优点，但第3章末尾也列出了维克瑞拍卖的不少缺陷，其中有的还很严重，使这种拍卖设计对于某些应用来讲是不切实际或无法接受的。

错综复杂的约束有可能对维克里拍卖造成难以克服的挑战。在本章中，鉴于美国联邦通信委员会的频谱激励性拍卖具有的规模和经济影响，我要在该拍卖的背景中介绍这种挑战。在这项应用中，最大的约束与确保任何两个电视播放站的播放都不会引发某种不可接受的干扰相关。类似的成对约束可在许多应用中见到，尤其是在交通系统中。例如，在空中交通控制中，需要为航班排时间表，以免任何两架飞机过于接近，而相似的限制也适用于铁路运输。

就联邦通信委员会的频谱激励性拍卖而言，计算最优配置的问题极为棘手，曾经使采用维克里拍卖的建议陷于灭顶之灾。对该问题的模拟表明，即使采用适于细致问题架构的最优商用算法（Gurobi和CPlex[1]），在高速计算机上运算数周，仍无法找到最优解。在给定问题难度的情况下，分析师们身手不凡，求出的解至少有97%是最优解，却远未好到可以算出维克里价格的一个像样的近似值。

其原因在于，对每个成为获胜投标者的播放站n来讲，准确的维克里价格是n-+vn。其中，是n被认可为获胜时仍留在无线广播中的播放站具有的最大总价值，而是播放站n被迫成为出局者时的最大总价值。要想认清该估算问题有多严重，假设在这两种计算中，有一种，能精确做到，比如n，而对另一种只能达到实际最优解的0.99，即0.99 。这样一来，支付给一个获胜者的维克里估价会因0.01 的差幅而过高。由于在美国约有2 000个电视播放站，平均的播放站价值必然约为0.0005 ，因此该维克里定价误差大约是播放站平均价值的20倍。如果将这种估计误差倒过来，则该误差的量级依然相同，但估计的维克里价格通常会是负的，从而违背了维克里拍卖的逻辑。这项分析表明，即使只想得到维克里价格的一个适度估计值，最大化也必须非常近似于完美。这是该项应用的一个问题，因为检验维克里价格计算的正确性是一个NP完全问题。该激励性拍卖因伴有数以千计的选择变量和270万个约束条件而过于庞大，无法在计算上确保这个问题要求的精度。

那该怎么办呢？至少这些计算上的问题意味着，拍卖设计需要放弃在现实中实现最优化的目标，但即便如此，仍有种种挑战。首先，我们都希望我们用的任何算法能给出一个高度近似最优化的可能值，从而不会因达不到最优性而损失太多。其次，一旦我们放弃了最优化，也许就能够使拍卖具备维克里拍卖缺乏的其他良好特性。我们可以期望更好的激励特性（如某种群组反谋略性，group strategy-proofness）、更简单（对投标者而言更明显的计算），或者在获胜投标者愿意支付的价格上给他们提供更大的隐私保护。基于本章所介绍理论的最终拍卖设计囊括了所有这些优点。

4.1 维克里拍卖的替代项目

本章描述的理论中很大一部分属于首创，目的是要应对联邦通信委员会频谱拍卖中的特有挑战。

4.1.1 频谱激励性拍卖项目

如第1章介绍的，从20世纪中期起，电视产业已有过几次自我革命。最初，每个看电视的人都是在三个VHF（甚高频）频道（第2、4、7频道）之一上收看无线播放节目。渐渐地，可看的频道变多了，还纳入了属于UHF（超高频）范围内的频道，而这类频道被认为相比于早期的模拟电视信号是很差的。接下来就是有线电视和卫星电视。再接着是从模拟信号向数字信号的转型，这大幅提高了可用频率的运用效率，使高清晰度的节目得以播放。

到2012年，约90%的美国住户在利用电缆或卫星而非无线播放接收电视信号。从2007年（第一部苹果手机问世）至2012年的5年之内，对使用移动互联网接入的频率需求有过爆炸式的增长，而人们预测这种增长还将继续。政策制定者很想知道他们是否能使一种更替成为可能，即可以让移动电话公司和其他机构购买那些被用于UHF电视播放的频率，因这些公司和机构发现，这些频道是用于第四代移动宽带技术（4G）的理想频道。而激励性拍卖的意图就在于使这样一种更替成为可能，同时为美国财政部筹资。

这样的激励性拍卖因若干理由而具有了历史意义。首先，它涉及的货币金额极高，有可能高达数百亿美元。其次，在以前的拍卖中从未有过这种交换（swap）。早期的频谱拍卖都是出售当前未占用频道的使用权，因此拍卖者无须担心能否筹到足够的钱支付给卖家。而现在这种拍卖设计中，最独特和最困难的部分与如下问题有关，即从UHF播放机构购买并清出一定数量的频谱，并使它们可被用于他途。

4.1.2 联邦通信委员会频谱激励性拍卖中的配置约束

要想用正规术语描述这种拍卖，第一个任务是开发出一套标识符号叙述播放站对频道的分配。我们将要定义的变量都是逻辑变量，即都是关于这种分配的陈述。我们用（X,c）表示“指定播放站X在频道c上播放”。这正好是一个陈述，因而它可能是真的，也可能是假的。电视播放站对频道的分配构成一个真陈述集，即一个配对集P⊆S×C，其中，S是播放站集合，C是可能频道的集合。

种种陈述的一定组合不可能同时为真，这要么出于逻辑上的原因，要么是因为拟议中的播放站分配会在播放机构之间造成不可接受的干扰。例如，从邻近发射塔播放的两个播放站不能使用同一频道。有关这个问题的所有约束要么与单一播放站有关，要么与一对播放站有关。

要描述这些逻辑约束，我用¬表示逻辑上的“否定”，用∨表示逻辑上的“或者”，用∧表示逻辑上的“和”。而约束都用各种集合的一个分类（CX,X∈S）和一个集合^I描述，并伴有如下解释：CX⊆C是频道中被允许分配给播放站X的子集，而^I⊆（X×C）2则为成对播放站列出了所有非兼容的频道分配。根据这些解释，若这些约束同时用文字和数学符号表述，则呈现如下：

1.“S中的每一个播放站都分到了（至少）一个适于它的频道。”

2.“S中没有任何播放站分到两个不同的频道。”

3.“没有任何两个播放站分得不兼容的频道。”

在联邦通信委员会的频谱激励性拍卖中，约有270万项这样的约束。其中最简单约束要求两个位置紧邻的播放站不能分配到相同频道上。

要想深入了解这个问题，让我们聚焦于一种适用两个条件的特殊情形。第一个条件是，所有播放站都有资格占用同一批频道C，这使我们可以在逻辑约束中用C取代CX。第二个条件是，唯一要紧的干扰存在于两个紧邻的播放站之间。当这些条件都得到满足时，我们就能以下列方式用一张图更简单地写出各种约束。

令A⊆S×S描述相互邻近因而不能分得相同频道的成对播放站集合。我们的假设意味着I={（X,c,X′,c）|c∈C,（X,X′）∈A}。我将各播放站S当作一张图中的各个节点，而将A当作对应的弧集。两个播放站（X,X′）∈A被认为是紧邻的。仅使用C个频道检验以不引发干扰的方式向各播放站分配频道是否可行，有着与图着色问题相同的逻辑结构。因为图着色问题就是要决定，在给定图（S,A）的情况下，是否有可能用C种颜色为每个节点着色，从而没有任何两个紧邻的节点是同色的。

这个图着色问题被公认为是NP完全级别的（Karp,1975）。对适用于任何NP完全问题级别的每一种已知算法，都存在一系列规模s方面的问题。因为正是在这个规模级别中，求解时间因s而呈指数式增长。在实践中，即使在中等规模的问题中，仍会有一些问题就算是在最快的计算机上也需耗费极长的时间求解。

这种计算复杂性对于激励性拍卖这样的应用有很大的影响，因为在这种拍卖中，不出售其权利的电视播放站必须要分得某个频道。要决定是否有可能接受电视播放站的报价集并拒绝别人的报价，联邦通信委员会必须决定是否有什么可行的办法向不出售权利的播放站分配频道。如我们已看到的那样，这与图着色问题相当类似，且它的难度有可能极高。

4.1.3 单一意图投标者

本章从头至尾，都将注意力限定于“单一意图的卖家投标者”，这是指投标者只有一个播放站要出售且面对单一的决策——卖或者不卖。在实际的激励性拍卖中，有些投标者拥有多个播放站，且有的投标者对那些播放站还拥有卖或不卖之外的选项，所以此处提出的这个理论并不完全适于这项应用。但如果说成为某个大群体组成部分的电视播放站往往都是具有较高价值的播放站，那么这种拍卖中的真实卖家大多数是单一意图投标者。这都是些较小的投标者，对他们中的多数来讲，卖或不卖是其主要的选项，且在这样的情形中，缓解投标者面对的报价问题将是核心的设计挑战。[2]

小投标者的一个特殊需要是要确保他们能理解拍卖规则以及规则包含的种种激励。其计算必须比维克里拍卖中的计算简单得多。维克里拍卖中的计算复杂难懂，因而就算技术专家真有办法执行它们，投标者也未必相信其正确性。投标者不信任的后果可以是不参与，从而威胁拍卖的成功。

4.1.4 “明显反谋略”机制：非公式化讨论

因报价容易且省去了某些成本，反谋略机制能拥有超越其他机制的重要优点。在我们的理论模型中，一个探明竞争对手报价的投标者不可能利用信息精明地报价，因为简单、诚实的报价永远是最优的。任何投标者都不可能靠研究、刺探其竞争对手以掌握他的类别，或者通过给自己的信息加密隐瞒类别以改善自己的机遇。在标准的密封投标中，投标者希望能够出其不意地以低价从竞争对手手中赢得拍品。与此不同的是，反谋略拍卖中不存在任何这样的潜在好处。

不过，反谋略性可能仍不足以使报价对投标者来讲是真正简单的。我们已经看到，反谋略的维克里拍卖会遇到严峻的计算问题，但即使它们不面临这类问题，反谋略机制的优点也可能因若干原因而得不到完全的认识。首先，实验证据（Kagel and Levin,1993）表明，在普通的次优价拍卖中，尽管该机制实际上是反谋略的，但投标者还是常常出错。其次，在计算很具挑战性的情境中，可能很难使投标者信服反谋略性。其三，如果投标者不能验证计算，他们就可能怀疑拍卖师正确实施计算的能力。最后，投标者可能担心不老实的拍卖师会偷看报价并另外提交使他们失败的报价以操纵拍卖价格。

所有这些问题都是可以克服的，办法是放弃所有直言机制，倾向更具动态的拍卖机制，以创造出一种反谋略机制，即就算投标者不理解该结果函数要求的计算，不信任拍卖师会正确地计算，没有能力按命题2.7的证明思路导出反谋略性，也不相信拍卖师会不偷窥众卖家提供的报价，这个机制仍能得到投标者的信任。用李绳武（Shengwu Li,2015）的话讲就是，这样一种机制是“明显反谋略的”。有一个迹象表明这是有可能做到的，它来自凯格尔和莱文（Kagel and Levin,1993）的另一个发现，即在同样的实验室情境中，投标者对次优价拍卖困惑不解，但在易趣网上用的简单的价格递增拍卖中，他们采用的却是占优的诚实策略。

与直言机制不同，在动态机制（dynamic mechanism）中，某投标者并不仅仅报告估价，而且还可以有多次报价机会。例如，在价格递增拍卖中，投标者通常有多次机会改善（即提高）其报价。如果投标者是卖家，则价格递减拍卖的运作与此类似，投标者可以通过降低其报价而动态地改善要约。

在动态机制中，投标者n的一项策略σn∗（“诚实的”策略）与该投标者的任意其他策略σn相比，如果在这两种策略首次出现分叉的任何n的选择节点上，继续遵循σn的最高可能收益少于或等于继续遵循σn∗的最低可能收益，就说策略σn∗是明显占优的（按照李绳武的定义）。如果一个机制的特性是每个投标者都永远拥有一种明显占优策略，该机制就是明显反谋略的。在本节中，我们对这个概念只给出文字解说，在下一节中要为一种特殊的拍卖类型使用公式化的标识符号。[3]

当拍卖师要出售（或购买）某单一对象时，很容易看出，维克里的次优价拍卖不是明显反谋略的。假设，有个投标者愿意出售某拍卖品，他对物品的估价为10，但考虑是否要开价为8。如果该投标者开价为10，即采用占优策略，则能够出现的最坏情况是他可能输掉，所得收益为零。如果相反，该投标者开价为8，他有可能在X>10的某价位上获胜，并在X-10>0时获得一笔正收益，所以他的最优可能收益严格为正。既然诚实开价的最低收益少于背离诚实的最优收益，该拍卖就明显不是反谋略的。

与此相反，请考虑一种动态时钟拍卖机制，这里的“时钟”是非正式名称，它表示展现可变价格的显示器。该价格时钟在高价位上启动并在整个拍卖过程中令价格渐次下行。每当一个投标者的价格变化时[4]，就问该投标者，他是否要继续在场。只要投标者答复“不在场”，他就退出拍卖。当只有一个剩余投标者从未说“不在场”时，该投标者就获胜且他需要支付的是他已接受的最后价格。由于价格降低量极小（小于各投标者之间的任何供给成本差），如果展现给投标者的价格都几乎相等，且一次只调节一个投标者的价格，这个机制就模仿了维克里拍卖。其理由是，第一，这个机制是反谋略的；第二，最后仍然在场的投标者具有最低的供给成本；第三，此时的时钟价格几乎等于次低供给成本。

但与维克里拍卖不同，在时钟拍卖中，每个投标者都有明显的占优策略：只要价格高于他的估价，他就应当说“在场”，否则他就应当说“不在场”。要证实这种“诚实的”策略是明显占优的，请注意，投标者在任何选择节点上起步都不能赔钱出售，所以采用诚实报价的可能连续收益最低为零。如果该投标者采用任何其他策略，那么在起步的任何选择节点上，都背离了诚实策略，可能连续收益最高为零。其原因在于，这样的投标者要么错误地说“不在场”，从而永远得到零收益；要么在价格已低于估价时错误地说“在场”，此时的最优结果是他输掉并挣得零收益。

在关于明显反谋略性的定义中有很多精妙之处。首先，与验证占优策略相比，在该机制的运行过程中投标者可能更易于验证某种被荐策略是否明显占优。因为，这种验证只需要比较代表最优收益和最差收益的两个数，虽然这种比较在每次选择时都要做。与之不同的是，在次优价格拍卖中，要验证诚实报价比任意特定的替代策略更好，投标者就需要计算和比较潜在收益的两个向量，相当于将他所能挣得的收益与其他投标者的所有可能策略组合的收益相比较。要证实某种策略是占优的，就必须把每一种替代策略做类似的比较。而这在日常术语中有时被说成，在维克里拍卖中占优性需要做“相机推断”（contingent reasoning）：投标者需要考虑一些个别情形，并就每一种情形比较两个策略可能发生的情况。显然，反谋略机制能使参与者免于运用相机推断。

其次，在时钟拍卖中，投标者理解和信任机制运行者的必要性下降了。要断定一种策略是明显占优的，投标者只需要知道两件事：如果他说“不在场”，他就要带着零收益退出；而如果他说“在场”，则要么是他赢得按价位供应的权利，要么那套机制将通过另定一个更低价格而继续下去。投标者没有必要知道的事情包括，有多少其他投标者参与，有多少拍卖品要被购买，这个时钟将来会选什么价格，以及即使没有其他投标者在场时，该时钟是否仍能令价格渐次下行。对投标者来讲，要得出自己的结论，除了刚才指出的两件事之外，无须知道、理解或相信任何其他事情。另外，投标者也无须害怕拍卖师会偷窥报价。按规程，拍卖师要看着那些报价运行该机制，但与封标拍卖不同，在封标拍卖中，拍卖师能够探明如何安全地操纵价格，而在时钟拍卖中，拍卖师没有任何安全的操纵办法，因为他不知道投标者对下一个价位将如何反应。

动态机制有助于简化激励计算，但将动态机制的结果与其他机制的结果相比较，则结合运用直言机制还是有帮助的。一旦我们明确了投标者人数、他们的诚实策略，以及关于时钟何时下行和下行多少的规则后，若我们得到了投标者的类别θ，就能推断动态机制中源于诚实报价的配置和价格。我们称这种成对的配置和价格为（α（θ）,pα（θ））。收取有关投标者类别的报告并产生结果（α（θ）,pα（θ））的机制是直言机制。显而易见，如果动态拍卖是明显反谋略的，那么（α,pα）就是反谋略的直言机制。

直觉上看，直言机制描述的情形是，投标者将他们的类别报给拍卖师，而拍卖师则恰如投标者想要的，承诺在该动态机制中采用诚实策略。一个投标者要想发现向拍卖师谎报其类别是有利可图的，他就必须要发现背离明显反谋略的做法是有利可图的，而这是一个矛盾。

4.2 延迟接受时钟拍卖

现在让我们转向拍卖师是买家、投标者都是卖家，且他们各有一件物品要标价出售的情形。前文已非正式地描述过时钟拍卖，它们都包含某种重复的过程，在该过程中，拒绝某一价位的投标者都被不可逆转地移出拍卖，不到拍卖的最后不会认定任何投标者为胜者。认定胜者的决策被推至最后，而著名的盖尔-沙普利延迟接受算法（Gale-Shapley deferred-acceptance algorithm）也有此特点。这两个事实导致我们称这样的机制为延迟接受时钟拍卖（deferred acceptance clock auction）。[5]

要想将足够的细节置入前文的非正式描述以允许作正式处理，需要有两个另外的规定。第一点涉及在拍卖过程中应就已发生之事向每个投标者通报什么，第二点是要明确价格要约是如何确定的。在任何反谋略机制中，无论参与者得知其竞争对手的动向是什么，他们的最优选择总是最优的，所以我们可以简化描述，即将注意力集中在投标者在决策时能得知全部既往博弈历史的机制。在接下来的各段中，我们在不同的延迟接受时钟拍卖中做出的唯一正式区分是一个独特的函数p，它被用来决定如何设定价格。我们对p施加的唯一约束是，从一个回合到下一个回合，任何投标者都不得提高价格。

需要我们引入标识符号的关键概念是有关投标回合、在场投标者，以及历史时段的概念。拍卖在一系列离散回合（t=1,2,…）中发生，且在每一回合t中，都有某个投标者集At⊆依然“在场”。拍卖中到回合t为止的在场历史时段被标识为。令为所有可能的在场历史时段集。

其中，vn是投标者n提供其拍卖品的（机会）成本。拍卖结束时已不在场的投标者都是“出局投标者”：他们既不供给物品，也不接受支付，且挣得零收益。结束时仍然在场的投标者成为胜出者，他供给一件拍卖品并接受一笔相当于所获价格和供给成本之差的收益。

4.2.1 激励的属性

我们的第一个任务是描述延迟接受时钟拍卖的良好激励属性。这里要分析两种属性。一种与明显的反谋略有关，另一种与投标者群体在拍卖中合谋的激励有关。

定义

直觉上看，如果在博弈的任意可能历史时段At之后，一个博弈者径直背离σn希望获得的最优收益并不优于绝不背离且永远按σn博弈能获得的最差收益，策略σn就是明显占优的。有关明显反谋略的证明本身就应该是显而易见的——投标者还能如何别做他解？而且幸运的是，这一个证明就是。

命题4.1

在每一种延迟接受时钟拍卖中，诚实策略都明显占优。

证明

明显反谋略的一个有趣含义与投标者群体合谋的激励有关。任何拍卖都免不了合谋，因为获胜者能通过合谋贿赂失败者让他们不参与投标，或者规避残酷竞争。但是，如我们已经看到的，维克里拍卖尤其难以避免合谋。它们无须以支付贿赂来鼓励合谋。有时，在这种拍卖中，失败者可以通过合谋使他们变成获利的胜出者。这种影响可能很大。因为与无须付钱，只需眨个眼、点个头或者认可投标者共同利益便实现合谋的方式相比，以支付为形式的合谋会造成高得多的被察觉风险。所以值得指出的是，当一种拍卖能抵制较容易的合谋形式时，即当任何投标者群体都无法在拍卖中改变其策略时，拍卖本身就一定能引导所有投标者获得更高的收益。

定义

命题4.2

每一种延迟接受时钟拍卖都是群体反谋略的。

证明

请考虑潜在合谋者的任意集合S′，并考虑他们中的某人，比如说投标者n，在第一回合中背离诚实报价。此时，他的价格丝毫不高于他的价值，所以，不管S′中其他博弈者的策略是什么，n的背离都不可能导致大于零的收益。相比之下，诚实报价从不导致小于零的收益。所以投标者n绝不因参与合谋群体而获利。■

4.2.2 合乎贪婪算法的延迟接受时钟拍卖

让我们再次假设，拍卖师/买家拥有一些约束条件，这些条件控制着他能拒绝的投标者/卖家集合，同时又满足他的购买目标。我们的目标是考虑肯定满足这些卖家约束条件的延迟接受时钟拍卖。

我们将注意力集中在延迟接受时钟拍卖中确保有一个可行结果的子集。直觉上看，这些拍卖是按下述方式运作的。在每个回合中，这种拍卖都要验证任何在场投标者的退出是否有不可行的风险。如果有这样的风险，就将该投标者标注为必要的。这意味着，将不再进一步降低该投标者的价格，而该投标者将最终成为胜者。其余的在场投标者都是非必要的。在任何回合t中，这种拍卖都按照一定的量（Δ（At）≤Pn∗（At-1））降低非必要投标者（被标识为n∗（At））的价格。我们假设这个过程是有限的，[6]反复持续至所有在场投标者要么是必要的，要么被报价为零。此时，没有进一步的价格变化，拍卖结束。

下面是用标识符号表达的相同拍卖算法。

一次一个投标者的价格削减算法

由于一个投标者只有当他的价格被降低时才会选择退出，且只有当退出不会导致一个不可行配置时，才降低一个投标者的价格，所以具有这种定价算法的延迟接受时钟拍卖的结果永远是可行的。

命题4.3

具有一次降低一个投标者价格的算法的每一种延迟接受时钟拍卖都终结于一个可行的配置。

这类拍卖有一种特别简单的算法：（1）价格降低量Δ（At）=Δ是一个正的常数；（2）n∗（At）在合格投标者标号1,…,N中重复循环，略过必要或不在场的投标者，或者其价格为零的投标者。我们称此为价格降低量Δ的标准时钟拍卖。在这种拍卖过程中的任何回合上，任意两个非必要投标者要么拥有相同的时钟价格，要么拥有正好相差Δ的价格。

假设在标准时钟拍卖中，每个投标者n都采用他的明显占优策略。于是，如果价格降低量Δ足够小，第一个要退出的投标者将是第一个发现价格已跌至其估价以下的非必要投标者。如果这样的投标者独此一人，他就是持有最高估价的投标者；否则，他就是持有同样最高估价的投标者之一。一旦这个投标者退出，必要投标者集合就会被重新计算并有可能被扩大。下一个要退出的投标者又是当时持有最高估价的非必要投标者。因此，标准时钟拍卖中的获胜者集合就完全像是投标者向拍卖师诚实报告其估价，而拍卖师则运用某种贪婪拒绝算法决定拒绝哪个投标者。我们说“某种”贪婪拒绝算法而非贪婪拒绝算法，是因为如果有两个或两个以上的投标者持有相同估价，对投标者的排序可以影响他们中的谁会被拒绝。

命题4.4

设。于是，价格降低量为Δ的标准时钟拍卖以类似于某种贪婪拒绝算法的方式拒绝投标者。

接下来，我们将这些结果与第2.4节中引入的拟阵相联系。将命题4.4与命题2.14合并得到如下命题。

命题4.5

如果是一个拟阵且，则价格降低量为Δ的标准时钟拍卖导致某种最优配置。

4.2.3 隐私保护特性

在实际的拍卖中，可能存在多种理由使拍卖师或者获胜投标者不想让别人知道他原来愿意接受的价格。就拍卖师而言，存在着一种风险，即公众或其客户得知反向拍卖中的胜出投标者原本愿意接受一个低得多的价格。在正向拍卖中，该问题的一个著名实例出现在20世纪80年代新西兰的电视许可权拍卖中。政府采用了次优价拍卖，获胜投标者支付的价格等于次高报价。在那场特殊的拍卖中，胜出者的报价是10万新西兰元，但获胜投标者只支付了6新西兰元，这就是次高报价（当时1新西兰元=0.55美元）。报刊大肆宣扬这一巨大落差，令政府备感难堪。

投标者或许也希望隐瞒他们愿意支付的价格，以免竞争对手、供给者和其他人得知那次特殊交易可能多么有利可图。

从保护隐私权的普遍愿望来看，价格递减时钟拍卖的另一个特别好的属性就是，它并不要求所有投标者通过其报价披露其准确估价，而只是要求获胜者透露证明他应该获胜的必需的最少信息。在计算机学科中，这个特性被称为“无条件隐私权”（unconditional privacy）。除了减轻投标者对披露其估价的顾虑之外，这个隐私权概念还有一个好处，即有的投标者觉得算出准确价值很费事，而这个概念使得投标对那些投标者来讲更为容易。米尔格罗姆和西格尔（Milgrom and Segal,2015）证明，各种时钟拍卖实质上是提供占优策略激励并保护胜者无条件隐私权的仅有机制。

4.3 近似拟阵和互替性指数

在实践中，基于贪婪算法的程序经常表现极好。在凯文·雷顿-布朗、尼尔·纽曼、伊利亚·西格尔和我对美国激励性拍卖所做的小型模拟（Leyton-Brown、Newman、Segal and Milgram,2016）中，我们发现，这种拍卖获得的价值通常达到最优化价值的95%以上。在实际拍卖中，维克里结果和价格根本不可能计算。在我们的小型模拟中，维克里结果耗费的时间和基于贪婪算法的拍卖相比要多出三个数量级，但后者获得的价值是最优化价值的95%以上。这一惊人的良好表现需要某种解释，而我在此处提供的只是对该解释的初步思考。

给定标准时钟拍卖在为一拟阵时具有简易性和表现良好的特点，人们也许希望，当可行集合中的相关部分能由一个拟阵近乎完全描述时，某种相似的拍卖也能运行良好。为了使这一论断在正规意义上讲得通，我必须给出一种正规的解说，以恰当地把握“相关”和“近乎”这两个词的含义。

首先聚焦于“相关”这个词。对我头脑中有的问题，如一个繁忙空港的航班时刻表，分析者可能了解或猜到，有些约束条件，比如跑道空间，可能是最优解的重要决定因素；而其他约束条件，比如航站楼的空间，就可能较少限制性。要在模型中体现这一点，请设想，全套约束条件体现为一个集合，但分析者猜想，最优解将位于更小的⊆。假设和都具有自由处置属性（free-disposal property）。如果分析者不具备任何有用的信息，就需要通过指定=以便在模型中反映那些信息。如果分析者知道，有些约束条件肯定有约束力，而别的约束条件肯定没有约束力，那么就可能出现⊂。

对于“近乎”这个词，我引入一个指数来描述任意特定拟阵中的集合与中的集合相近似的程度。聚焦于任意特定集合X∈，其最优的内部近似（best inner approximation）是集合M∈，它含有X的最大元素数。我用来衡量该近似的最差品质。我将注意力限定于各种近似拟阵⊆上，所以近似集合M∈本身是可行的。给定这一方法，用一个拟阵近似地反映各相关约束条件的能力就由“替代性指数”（substitutability index）来描述，其定义如下。

定义

给定N中诸子集的一个分类，一个最优近似拟阵可标识为∗=（,），而其替代性指数可标识为ρ（,），其中

且

命题4. 6

证明

令

给出：

根据命题4.6，替代性指数不仅测度各集合的最差近似度，它还测度源于求解∗上易计算问题而非上难计算问题的最差收益率。求解拟阵∗上的问题是容易的，因为它正好靠一种贪婪算法来求解。而且，该贪婪算法提供了一种单调的胜者挑选规则，所以它能被纳入某种反谋略拍卖。

命题4.6对于像频谱的激励性拍卖那样的应用最有意义。因为，在那种拍卖中，约束条件都是已知的，并且知道哪些是在最优解上有约束力的约束条件。该命题意味着，如果ρ（,）接近于1，就有可能制定一种特殊的贪婪算法，它将因那些实际约束条件和某个相对集合中的所有取值而运行良好。该命题为一种特殊贪婪算法的表现给出了最差限界，此种特殊贪婪算法虽是标准的贪婪算法，但采用的是约束条件∗，而非实际的约束条件。

有另外一些类贪婪算法，它们的表现甚至比贪婪算法更好。首先，将该标准贪婪机制用于（N,v,∗）。然后，当这一机制停止时，从∗至R逐渐放松约束条件，并且只要可行，按贪婪方式装入新增的物品。在最坏的情况下，如果没有新增物品可装入，其解就与那种近似的贪婪算法一样。不管怎样，这一扩展经常导致严格的改善，因为它装入了新增的物品。不难看出，这种改良的贪婪算法依然是单调的，所以它能被用作反谋略拍卖的组成部分。

4.3.1 一个频道分配的例子

与世界大多数地方一样，美国的大城市也都是靠享有船运贸易之利发展起来的。因此，大体上，我们可以对城市和播放站形成一个概念，即它们线性地沿一条海岸线有序布局，我们设定这种排列的走向是由北向南。请设想在每个都市区域内，电视播放站都紧密地聚在一起，从而若有两个播放站在相同频道上播放，一个播放站就会干扰另一个播放站的至少部分客户的信号接收。再请设想，有些靠近都市区域边界的播放站可能干扰紧邻城市中的某些播放站，因此需要向那些播放站分配不同的频道。假设有C个频道可用，且每个播放站都只与其I个北面最近邻居和I个南面最近邻居有某种潜在的干扰冲突。令x（n）表示播放站n所在的城市。使某播放站集合S可行的一个明显必要条件是，对每个城市X，有{n∈S x（n）=X}≤C。也就是说，在一个城市中，我们分配的播放站在总数上不能多于可用的频道。

给定这样一个分类S，请设想，我们设法由北向南逐次向播放站分配频道，从频道1开始并持续到频道C，然后对下一个播放站从频道1重新开始，并以同样方式持续分配。如果C>I，则每个播放站分得的频道都不会与其北面I个最近邻居和南面I个最近邻居中的任何一个相同，因此这种分配绝不会引发任何干扰。由此而来，播放站中的这个可行分类就与拟阵′={S:{n∈S|x（n）=X}≤C}吻合。如果C <I，仍然有可能通过′创造的一个拟阵从内部限定。例如，增加如下限制，即在每个城市里，I个最北面播放站中能够继续播放从而必须向其分配频道的播放站不得超过C-1个。实际问题中并不存在这个外加约束，而添加这一约束导致一个拟阵′，它对实际的约束集是一个内部的范围限定。虽然如此，但在这个内部范围上运行的贪婪算法导致对最优解的充分逼近。实际上，对于′这个选项来讲，。因此，不考虑各电视播放站的实际价值，采用拟阵′的贪婪算法选出的播放站集，其总价值与采用实际约束条件的最优解相比，至少达到后者的。

4.4 激励性拍卖的约束条件和贪婪算法

如在上述例子中一样，在联邦通信委员会的频谱激励性拍卖中，对获胜投标者集合的那些约束条件并非间接地给出，而是作为对一个次级问题的解给出的：找出一种可行的方法向各播放站分配电视频道，使它们能进行无线广播。在这个次级问题中，存在两类约束条件：一类约束条件直接限制可供每个播放站使用的频道。例如，位于纽约锡拉丘兹的某个播放站也许无法使用某特定频道，因为那个频道被预留给一个邻近的加拿大播放站使用。第二类约束条件禁止某些成对的分配。这类约束中最常见的例子或许是禁止将两个邻近的播放站，比如播放站X和播放站Y，都分到第26频道上。这要么是因为这两个播放站的服务区域多有重叠；要么是因为某个区域尽管已超出了X和Y的播放区域，但仍设定Y要为该区域服务，由于Y的距离较远，从而发自X的信号虽已相对变弱，但依然足以干扰发自Y的信号。偶尔还会有一些其他约束条件控制着位于不同频道上的播放站。例如，有时候会禁止将播放站X分到第26频道并将播放站Y分到第27或第28频道。

对这种激励性拍卖，令A表示那些依然选择无线播放但不参与拍卖的播放站集合。对这样的播放站，总是需要向它们分配频道。另外，会存在另一个播放站集合R，它们的当前报价是该拍卖系统想要拒绝的，因为它们索要的价格太高。将这两个群体合在一起，若这些投标者被拒绝就依然进行无线播放的播放站集合是S=A∪R。在该拍卖系统能够决定拒绝R中各播放站的报价之前，它必须先确定能够找到适合于S中的所有播放站的频道。

请注意，是各播放站集合的集合，它的定义始于一组可行的频道分配{s,c（s）}⊆（A∪R）×C，而这种频道分配是由一组配对构成的集合，且只取自每个配对中的播放站并只包括N-A中的播放站。这是一个复杂的建构，且没有任何条件保证一定拥有任何特别好的结构。然而，在许多场合，它的确具有某种好的结构。

例如，如果在某都市区域中只有15个频道可供使用，那么被指定继续在该区域内播放的播放站总数就必须不超过15个。如果各都市区域都是分开的，且这些是仅有的禁干扰约束，则这个约束集将定义一个拟阵。

作为另一个例子，请设想，对任意的播放站集合S总能找到一种可行的频道分配c，它不具有太多的播放站间禁干扰约束，比如有总数不超过I个的约束。如果sn是涉及播放站n的禁干扰约束数量，那么确保S可行的充分条件就是，所以这描述的是一个背包问题。返回我们对背包问题的研究，通过按vn/sn给各播放站排序，并利用这个指数以贪婪方式装包，就能找到一个近似最优解。

在联邦通信委员会的实际问题中，背包约束或者近于拟阵的约束都对这种配置有约束力，而两者中哪一个有约束力，它就能够影响各播放站究竟是按vn还是按vn/sn才能得到更好的排序。在近似于一个拟阵的情况下按vn排序能运行得很好；而如果背包约束是有约束力的，则按vn/sn排序就能运行得很好。还可能有种种折中。例如，可以按照vn/√sn给播放站排序，而且有些与此类似的做法还成为联邦通信委员会激励性拍卖中使用贪婪算法的基础。

[1] Gurobi即Gurobi Optimizer，美国Gurobi公司开发的大规模数学规划优化软件。C-Plex，全称“IBM ILOG CPLEX Optimization Studio”，是美国IBM开发的商用最优化软件。——译者注

[2] 在拍卖设计中，一般来讲，没有任何事情比吸引严肃投标者的投标更重要了。在激励性拍卖的情形中，在一个或几个广播市场中拥有单一电视台的小企业很可能是一个面对极高赌注的无经验投标者，它出售的是其家族业务！且正从事一种一生一次的陌生交易。在拍卖之后，由于运营的频道更少了，不出售其权利的投标者会分得宝贵的频道。按照均衡理论，拍卖中支付的价格可以接近于拍卖后的频道价值。所以，对投标者来讲，不参与有可能是一个能保命的现实选项。抵消这种激励的最好途径是让参与拍卖变得安全和容易，尤其是对那些小投标者。

[3] 寻求公式化、一般化解说的读者请参阅李绳武（Li,2015）。

[4] 这意味着，这种拍卖中的每个投标者都有自己专属的价格时钟。——译者注

[5] 本节中的拓展都基于米尔格罗姆和西格尔（Milgrom and Segal，2015）论文。

[6] 例如，我们可以限制价格降低量，使对某个,