1. 引言
作者以问题为导向,通过解决联邦通信委员会的无线电频谱拍卖中的实际问题,发展出了一套实用性极高的拍卖理论。本章将介绍问题的来源。
移动网络和智能终端的兴起(如智能手机等)需要将大量用于传输无线电视信号的频率清理出来,为移动网络腾出无线电频率。这就出现了大量无线电频率的拍卖。而无线电频率的拍卖,同拍卖和博弈相关的特点如下:(1) 移动网络同时具有传输和接受数据的功能,所以有着上行和下行两个通道,所以买家需要购买成对的频率,这对应着后文联盟博弈的“核”概念,买家策略是“核”收益最大。(2) 若按照传统拍卖的组织形式,拍卖的工作量过大:一场拍卖将拍卖多种不同价值的频道,频道卖家面临着不同的选择,卖家也有自己的偏好,买卖双方的最优策略并不一定完全重合。如:一场拍卖中,买家A需要拍下频道1到10,买家B需要拍下频道4到13,而1~14频道属于9个不同的卖家,卖家最多的有3个频道,少的有1个频道,按照传统拍卖,将组织(买家数) 2 × 9 (卖家数) = 18 (场)拍卖,随着买家和卖家数量的增多,拍卖的场数呈几何级数增长。作者在本章并未具体对此问题做出详细解答,而将此问题抽象成第二章的背包问题和近似背包问题。
综合看来,联邦通信委员会组织的频谱拍卖本质上是一种交换(swap),用旧的无线电视频率换成无线通讯网络或现金补偿,同时,拍卖还有另一个目的:为美国财政部筹资 [1]。
2. 背包问题与贪婪算法
背包问题(knapsack problem),始于丹齐格(George Dantzig, 1957),假设有一个“背包”,体积为S,和一些编号为n = 1, 2, …, n的商品,每个物品i都有着对应的体积si和价值vi。背包问题:挑出一组物品,在满足装入包中的物品总体积不超过背包体积S的前提条件下,同时使得装入物的价值最大。
本书作者在解决背包问题前,先引入了“放松的背包问题”,放松的背包问题是:物品可以无限细分,即可以装半个物品或者四分之一个物品进入背包。放松的背包问题,作者采用了“贪婪算法”(Greedy Algorithm):
算出每个物品的价值体积比,得到物品的单位价值
;将物品单位价值从高到低排序,得到序列
;
将物品按照单位价值从高到低依次装入包中,直到装不下为止。
贪婪算法能解决全部的“宽松的背包问题”和大部分背包问题,但是存在如下的情况无法解决:当背包体积为2,物品A的体积为1,价值为1.1;物品B的体积为2,价值为2。根据“贪婪算法”,物品A的单位价值为1.1大于物品B的单位价值1,那么“贪婪算法”的结果是:选择物品A,总价值为1.1;显然,本题的最优解是选择物品B,总价值为2。
本文作者将最后装入背包中的价格称为“拟均衡价格”,拟均衡价格如同均衡价格一样,有着反应供求关系的特点:当价格低于拟均衡价格时,存在过量供给;当价格高于拟均衡价格时,存在过量需求。
贪婪算法同样具有反谋略性,其原因是:只要投标人出价高于均衡价格即可,跟其他无关。为了得出发现拟均衡价格的机制,作者将“贪婪算法”进行改变,得到了变种的“截尾贪婪算法”即,在贪婪算法中加入提前终结的条件,在过程中终结前的每一回合都同贪婪算法一致。
激励机制和投资博弈:为了引入激励机制,作者在背包问题中引入了投资,即应标人可以通过投资的方式来改变物品的价值和体积。如:一个体积为2的背包,面临着体积为3,价值为9的物品A,该问题的解为空背包,背包价值为0,拟均衡价格为3。但是如果可以通过投资1单位,将A变成体积为2,价值为5的商品
,那么,我们可以选择投资1单位,将商品
装入背包,获得背包价值为5,拟均衡价格为2.5。在这一例子中,我们可以得出三个结论:(1) 可以通过投资的方式使得背包价值变大;(2) 投资可以使拟均衡价格降低,尽可能还原由“截尾贪婪算法”导致的拟均衡价格同均衡价格的偏差;(3) 当投资成本过高时,有可能存在成本高于投资收益的情况,而此时确定的拟均衡价格则是投标人的隐忍(若不投资,就什么都没有;若投资,还能有点收益,但不及心理预期),不能反映投标人的真实需要。
根据以上三个特性,作者将背包投资问题拓展为多个参与人,一起选择物品。作者此时引入博弈论的框架,所有局中人面临:(投资,不投资)这两个策略。而投资博弈的纳什均衡也可能存在多个纯策略纳什均衡或占优策略。同第三章的维克里拍卖的投资博弈问题类似,作者也通过设计投资激励机制来排除多个纯策略纳什均衡的其他无效率均衡,使得占优策略纳什均衡成为最有效率的结果 [2]。
作者针对贪婪算法出现的问题,提出了“贪婪拒绝算法” [3],即同原贪婪算法不同,贪婪拒绝算法区分了“被接受”和“被拒绝”的物品,并将其分为了两个集合A和R,每个物品都被打上标签 和 ,贪婪拒绝算法的具体步骤如下:
首先设定价值
,共有N个物品。
1) 初始化集合:
,且
。
2)
每次增加1,即每回合
。
3) 如果
,停止,并给出
和
。
4) 如果
,设
和
;如果
,设
和
。
转到步骤2。
贪婪拒绝算法的关键在第4步,判断是否拒绝,接受或者拒绝条件为企业的约束;且作者认为,贪婪拒绝算法同凯尔索克劳福德劳动力拍卖市场算法互为对偶问题,即:前者的思路是拒绝最昂贵的物品,直到不能继续拒绝;后者的思路是雇佣最合适的人,直到不能继续雇佣。在频道拍卖情形中,该对偶问题为:将被收购的频道(集合A)成本最小化;未被收购的频道(集合R)成本最大化。
3. 独特的拍卖理论
3.1. (近似)互替品、价格和稳定性
主要讨论了当市场中的商品都是互为替代品的时候,其市场均衡价格的决定机制以及均衡价格的稳定性。本章的思路较紧密,从简单到复杂,从新古典福利经济学市场均衡理论出发,分别放开以下三个限制条件:(1) 价格连续变动;(2) 商品完全互为替代;(3) 完全竞争。放宽条件(1),即价格离散变动,本书讨论了凯尔索和克劳福德的劳动力拍卖(Kelso and Crawford Auction);放宽条件(2),即商品为近似互替品,本书的第四章有关于其的详细讨论;放宽条件(3),即有外部性存在的情况下,本书在第四章的延迟接受拍卖中讨论了拍卖的激励机制,即卖家合谋而非独立个体之间的完全竞争。
本书首先讨论了新古典理论中完全互为替代品的市场、市场均衡价格及其稳定性,以阿罗和赫维兹(Kenneth Arrow and Leo Hurwicz)的市场均衡理论为框架,三大理论前提为:价格变化是连续的、商品完全互为替代、市场完全竞争。结论为:(1) 市场存在不止一组均衡价格;(2) 市场均衡具有一定的稳定性,即供求关系使得最终价格收敛于均衡价格;(3) 价格连续变化,从上到下或者从下到上连续变化。
凯尔索和克劳福德劳动力市场拍卖模型虽然是离散度,但是其结果同阿罗和赫维兹的连续模型一致,有如下结论:(1) 最终结果收敛于均衡工资水平;(2) 拍卖结束于有限的回合;(3) 均衡工资水平也是具有竞争性的,符合福利经济学定律。作者引用该劳动力拍卖模型的意图在于证明:市场的均衡价格可以通过有限回合的拍卖来实现。这就搭建了经济学理论和拍卖实践的桥梁。
我们回顾第一章无线电频道拍卖的情形,拍卖的商品并不符合同质性和完全替代性的约束,同时,买卖双方最有利的结果可能并不相同,即同一个频率可能对无线网络买家A和B或无线电视广播站C的效用不同,那么其价值也不同,在这一情形下,如何找到均衡价格,便是本章另一个讨论的重点。作者找到了类似的问题,即“背包问题”,并通过类似于“贪婪算法”的算法实现“背包问题”的求解。
3.2. 维克里拍卖与互替性
维克里拍卖,又名第二价格密封拍卖。其定义为:在维克里拍卖中,每个投标者提交密封的交易价格,出价最高者赢得商品,但交易却以所有出价中的第二高价进行。该拍卖具有反谋略和保护投标者隐私这两大特点。
本书又引用了联盟博弈中的“核”概念,用来讨论维克里拍卖中的互替性问题,即当无线网络运营商买家同时购买上行和下行频道才可以实现自身利益最大化,而单纯的上行或者下行通道对其毫无意义,而提供下行和上行通道的卖家不是同一个时,这两个上下行通道的卖家就形成了一个“核”。博弈策略的维克里收益是否还是符合经济学中竞争性和有效率的,同时维克里拍卖是否还能实现其反策略性。
维克里拍卖也存在诸多重要缺陷,如:(1) 拍卖师的维克里收益有可能非常低;(2) 在离散的价格变动和物品数量多且非完全替代品的拍卖情形下,在封标机制中,投标者可能不得不就数目很大的组合确定估价,这将使得计算变得十分复杂;(3) 有的情形中,维克里拍卖受制于财务约束,使得他们给出的报价水平受到限制,这些情形下维克里拍卖不具有任何占有策略;(4) 在维克里拍卖中,出局投标者有时能够进行有利可图的合谋以变成获胜投标者。而且,合谋有可能对所有相关当事方都完全有利,从而无须合谋者进行可能被察觉的现金转移。
3.3. 延迟接受拍卖和近似互替品
由于实际拍卖中要涉及错综复杂的约束,这些约束给维克里拍卖造成了难以克服的挑战。本章内容大部分由作者首创,目的是针对性解决联邦无线电频谱拍卖遇到的问题。其中,最大的约束与确保任何两个电视播放站的播放都不会引发某种不可接受的干扰相关,美国有2000个电视播放站,共形成数千个选择变量和270万个约束条件,过于庞大。而维克里拍卖对于价值的估算在大量拍卖品参与的情况下,误差显得尤为巨大。同时,由于维克里拍卖的“怪异”机制,许多参与拍卖的应标人无法完全理解其直言机制,尽管其机制是反谋略的,但是往往投标人容易出错。这也造成了投标人对拍卖机制的不信任。同时,拍卖中也存在串标,拍卖师偷看价格舞弊等行为,这些行为导致了投标人对拍卖的不信任,从而威胁拍卖的成果。于是,本文作者在希望设计一套拍卖机制,这套拍卖机制具有:(1) “明显的反策略性”,即不用通过书中第二章和第三章的证明来理解其“反谋略性”,并赢得投标人的信任;(2) 拥有一套能够计算出高度近似最优化的可能值的算法;(3) 具有更好的激励特性(如群体反策略)和保护投标人隐私的特性。
于是,作者引入了维克里拍卖的替代方案:有动态机制的激励性拍卖。动态机制,作者这里指的是动态时钟拍卖机制。动态体现在拍卖存在多个回合,每个回合价格都改变;时钟指的是在应标者面前有一个价格显示器,显示价格的变化,该显示器在拍卖回合开始时处于最高位,并随着回合的进行而渐次下行。每当投标者的价格变化时,就询问投标者是否继续留在场上。当剩余最后一个投标者未离场时,该投标者获胜,并支付他接受的最后价格。通过上文的分析,我们可知:(1) 价格的单调变化并最终到“拟均衡价格”停止这一机制符合贪婪拒绝算法;(2) 可以实现拍卖胜出者的成本最小化;(3) 由于每回合的价格变化微小,所以,最后的成交价格仅仅略低于投标者的心理价位,符合维克里拍卖的次优价格机制;(4) 该机制存在明显的反策略性,即如果他在错误的时机选择离场,那么他将一无所有,如果他在低于估价的时候仍然选择在场,他将获得负收益;(5) 由于每个应标人的类型不同,面对的时钟和价格下降机制不同,所以,该拍卖机制也具有保护隐私的特性。
该机制同时还简化了计算,当时钟拍卖回合结束后,收集到了所有应标人i的最终价格
和期望配置
组合
,将最终价格和期望配置组合的集合
,剩下需要的计算就变得简单了。由于动态时钟拍卖机制同盖尔–沙普利(Gale-Shapley)的延迟接受算法(deferred-acceptance algorithm)有着相似的特性,于是这个动态时钟拍卖机制又被成为延迟接受拍卖机制。
动态时钟拍卖的机制设计中还有两个较为重要的问题:首先是如何确定每次价格降低的量?其次是如何满足第一章导论部分提到的约束?针对每次价格降低量
的问题,作者认为,每个应标者面对的时钟应该有自己独特的降价函数,而且,每个应标者都不知道下一回合的降价量
。而确定价格降低量 的思路同贪婪拒绝算法密不可分。贪婪拒绝算法在每个回合都会对一个物品进行标注为“接受”或者“拒绝”,而价格降低量
的目的在于恰好将拍卖者从“接受”变为“拒绝”,这样能够确保拍卖能在有限回合内结束。确定价格降低量
的算法被称为“一次一个投标者的价格削减算法”。
“由于一个投标者只有当他的价格被降低时才会选择退出,且只有当退出不会导致一个不可行配置时,才降低一个投标者的价格。”
换言之,当价格无法接受或者配置不可行的时候,投标者会“拒绝”结果并退出拍卖,此时便符合贪婪算法。
4. 理论应用:联邦通信委员会激励拍卖
在第一章的附录部分,作者提供了联邦通信委员会激励拍卖机制的有关简报,我将结合上文的分析,在本部分对其进行讨论。联邦通信委员会的拍卖分为多个环节,其思想是:在收入覆盖支出的情况下,为联邦财政创造税收。所以,首先进行价格递减的电视播放站播放权让渡拍卖,这样可以将成本减少并锁定在一个可以接受的水平。其次,进行价格递增的移动网络使用权授权拍卖,这是价格递增的正向拍卖,目的是在覆盖成本的同时,尽可能多的为联邦财政创造收入。紧接着通过终端回合核算“收入和支出”,如果有需要,再进行“延展回合”目的是有序地扩大收入。最后,进入频道分配回合,确定频道的归属。
拍卖首先进入清理目标环节,即拍卖的首要任务是要整理哪些UHF1频道继续用于电视播放,哪些转入移动网络。这一阶段要设立可能被清理的最大频道数。
拍卖第二环节为“反向拍卖投标”,反向拍卖投标用来购买电视播放权。类似于荷兰的鲜花市场拍卖,反向拍卖投标是价格递减拍卖,即电视播放站的价值未来是不断减少的,当不收购一个播放站就不可能实现清理目标时,该播放站的价格就停止下降,原则上,每个播放站的价格都不同。该步骤的目标是降低整场拍卖的总成本。
拍卖的第三环节为“正向拍卖投标”。在该环节中,移动宽带供应商为购进频谱中特定频率的占用许可权而竞争。正向拍卖是上文所述的“时钟拍卖”,在一系列回合中进行,需求大于供给时,价格上升,直到再也上不去为止,有着贪婪算法的特征。出于反垄断的考虑,为防止大买家垄断了高质量的频道,联邦无线电委员会制定了“有条件预留”机制,即在收入达到某个“阈值”的之前,各个买家都平等地竞标;达到阈值之后,某些“合格的投标人”可以排他性的参与某些地区的竞标。这条规则的目的就在于通过竞争筹集足够的收入,不允许无线播放市场中的在位者躲避竞争。
拍卖的第四环节为“终段规则及追加阶段”,如果来自正向拍卖的收益满足了某个最低绝对标准,且如果这些收益高到足以支付由反向拍卖决定的清理播放机构的成本,则整个过程结束。这一决定原则被称为“终段规则”(final stage rule)。如果收益不足,就缩减清理目标并启动另一个拍卖阶段。首先通过降价来回购较少的频道;与此同时,在正向拍卖中,供给会减少,但价格会继续上升。
拍卖第四环节后有可能有“延展回合”,这一回合的目的是当正向拍卖中的投标活动终结于某个清理目标时,价格低得无法满足收益目标,但差得不多,比如不到20%。可以想见,与其进入价格更高、许可权更少的另一阶段,该阶段的获胜投标者宁可看到拍卖价格上升以实现当下阶段的清理,也不愿意坐等价格上升而可售频谱量减少的另一回合。实质是一轮被追加的时钟拍卖。在延展回合中,价格可以有最高20%的升幅以实现市场出清。如果投标者选择继续随价格上升对当前的许可权数量投标,则当前阶段就能变成最后阶段,而当前的清理目标也就得以实现。
拍卖的最后阶段是“频率分配”回合,以上的回合中,只确定了胜出者,最终的配置并未进行分配。正向拍卖的移动网络运营商某些对频率有偏好,有些对地区有偏好;反向拍卖的电视播放站也要进行分配,即用UHF换取LVHF、HVHF 、现金亦或是以上三者的组合。而这一回合将配置所有这些偏好。
5. 结论
经济学理论中最重要的便是供求理论,供求关系影响着价格,而价格又可以引导供求关系。供求关系以一种什么样的机制决定着价格,作者在本文中探讨的就是这样的一个机制。如本书的书名,整本书的要解答的问题就是如何发现复杂约束市场中稀缺商品的价格。不同于那些交易频繁,买卖参与方众多的市场,如股票市场、期货市场等。总有些稀缺资源是特殊的,其价格面临着复杂的约束机制,如作者在文中详细讨论的无线电频道,以及简略介绍的飞机航路、电力系统等。而作者巧妙地通过“延迟接受拍卖”机制,以动态多回合价格递减的方式,模拟出市场上多变的供求变化,找到每个拍卖者的内心估价以及理想配置,并最终将结果整合,确定物品的价格,完成市场交易。
NOTES
1UHF,Ultra High Frequency,超高频,价值较高的移动信号;LVHF,Low Very High Frequency,低甚高频,价值低于超高频的移动信号;HVHF,高甚高频,价值介于超高频和低甚高频的移动信号。