（概率论与数理统计专业论文）组合拍卖机制设计理论研究.pdf

摘要 近几年来，随着计算机技术和电子商务的发展，拍卖多单元物品 的实际需要，许多传统的拍卖理论和假设已经不再适合新的拍卖经济 环境。人们开始设计并使用一些适合复杂性质物品的拍卖方式，其中 多物品拍卖中的组合拍卖成为关注的焦点。 本文重点研究了组合拍卖的机制设计理论。在研究过程中采用理 论证明、算例阐释、比较分析等方法。首先系统地总结了传统拍卖理 论的主要内容，接着针对组合拍卖的现状，引出组合拍卖机制设计理 论研究问题。其次，对单阶段组合拍卖机制( v c g 机制、一级价格 组合拍卖、向上叫价代理拍卖) 的理论模型、拍卖过程、机制设计问 题、机制的优缺点等进行了详细的探讨。并对理论价值意义大且常成 为很多拍卖机制参照标准的v c g 机制的重要理论性质给予了严谨的 数学证明。 再次，对于多阶段组合拍卖机制，详细讨论了两阶段和三阶段的 设计问题。首先讨论了两阶段组合拍卖( 时钟代理拍卖) 机制设计 的基本程序，研究分析了时钟代理拍卖的三大设计问题：需求量变 化的限制、价格增量的设定和拍卖阶段的结束问题。然后研究分析了 三阶段组合拍卖机制的设计思想和设计过程。研究结果表明：( 1 ) 时 钟一代理拍卖是一种性能良好的混合式拍卖，它充分结合了时钟拍卖 的简单性、透明性和秘密保存性以及密封一竞标代理拍卖的有效性； ( 2 ) 新型三阶段混合拍卖机制设计兼备了适应性用户选择 ( p r o g r e s s i v ea d a p t i v eu s e rs e l e c t i o ne n v i r o n m e n t ，p a u s e ) 和时钟一 代理拍卖的优点，而且能有效地克服它们的一些缺陷，提供价格信息 在任意捆上( 体现协同作用的信息，在线性价格下它被失去或者曲 解) ，同时减少竞价人自由乘骑的能力。该新型三阶段混合拍卖机制 具有一些十分吸引人的性质，有着很好的理论前景。文章还指出了各 种组合拍卖机制的应用场合，为组合拍卖方案的实施提供建议。 关键词：拍卖理论；机制设计；组合竞标；协同作用 a b s t r a c t r e c e n t l y ，w i t ht h er a p i dd e v e l o p m e n to fc o m p u t e rt e c h n o l o g ya n d e l e c t r o n i cc o m m e r c e ，t h ep r a c t i c a ln e e do fm u l t i u n i ta u c t i o n ，l o t so f t r a d i t i o n a la u c t i o nt h e o r ya n da s s u m p t i o na l r e a d yd i d n ta d a p tt ot h en e w a u c t i o ne c o n o m i cs i t u a t i o n i n v e s t i g a t o r st r yt od e s i g na n du s es o m e f o r m a ta u c t i o n sw h i c ha r es u i tf o r c o m p l e xp r o d u c t s m u l t i u n i t c o m b i n a t o r i a la u c t i o nb e c o m eah o tr e s e a r c h t h i sp a p e rf o c u s e so nt h ec o m b i n a t o r i a la u c t i o nm e c h a n i s md e s i g n t h e o r y i nt h ec o u r s eo fr e s e a r c h i n g ，w eu s et h em e t h o do ft h e o r e t i cp r o v e ， c a l c u l a b l ee x a m p l ee l u c i d a t o r y , c o m p a r a t i v ea n a l y s i sa n ds oo n f i r s t l y , t h ep a p e rs u m m a r i z e st r a d i t i o n a la u c t i o nt h e o r yb yt h en u m b e r s t h e n a i m i n ga tt h ec o m b i n a t o r i a la u c t i o na c t u a l i t y , w ef e t c ho u tt h et h e o r e t i c a l r e s e a r c ho fc o m b i n a t o r i a la u c t i o nm e c h a n i s md e s i g n s e c o n d l y , t h ep a p e r d e t a i l e dd i s c u s st h e s i n g l e s t a g e c o m b i n a t o r i a la u c t i o nm e c h a n i s m ( v i c k r e y c l a r k g r o v e s ，f i r s t - p r i c ep a c k a g ea u c t i o n ，a s c e n d i n gp r o x y a u c t i o n ) i tc o m p r i s e s a u c t i o nt h e o r e t i c a l m o d e ，a u c t i o np r o c e s s ， m e c h a n i s md e s i g np r o b l e m s ，m e c h a n i s m sm e r i ta n dd e m e r i t e s p e c i a l l y , t h ep a p e rp r o v e si m p o r t a n tt h e o r e t i cp r o p e r t i e so fv c g m e c h a n i s m ，i ti s w o r t hn o t i c et h a tm a n ya u c t i o nm e c h a n i s m su s ev c g a sar e f e r e n c ep o i n t f o rj u d g i n gt h e o r e t i cs i g n i f i c a n c e t h i r d l y , t h ep a p e rd e t a i l e dd i s c u s so nm u l t i - s t a g e sc o m b i n a t o r i a l a u c t i o nm e c h a n i s m s ，c o n s i s t i n go f t w o s t a g e sa n dt h r e e s t a g e s a b o v ea l l ， w ed i s c u s st h eb a s i c p r o c e d u r eo ft w o s t a g e sc o m b i n a t o r i a l a u c t i o n ( c l o c k p r o x ya u c t i o n ) m e c h a n i s m sd e s i g na n da n a l y z et h r e ed e s i g n q u e s t i o n so fc l o c k - p r o x ya u c t i o n ，i n c l u d i n gl i m i to fd e m a n dv a r i e t y , e n a c t m e n to f p r i c ei n c r e m e n t s ，e n d o fa u c t i o np h a s e a n dt h e nw ea n a l y z e t h r e e s t a g e sc o m b i n a t o r i a lm e c h a n i s m s ，i n c l u d i n gt h ed e s i g ni d e aa n d p r o c e s s i tt u r n so u tt h a to nt h eo n eh a n dt h ec l o c k p r o x ya u c t i o ni s a h a v i n gg o o dp e r f o r m a n c eh y b r i da u c t i o n ，w h i c hc o m b i n e st h ec l o c k a u c t i o n ss i m p l i c i t y , t r a n s p a r e n c y , k e e p i n gp r i v a c ya n dt h es e a l e d - t e n d e r p r o x ya u c t i o no fe f f i c i e n c y ；o nt h eo t h e rh a n dt h en e wt y p et h r e e s t a g e s h y b r i d a u c t i o nm e c h a n i s md e s i g nn o to n l yh a v eb o t hp r o g r e s s i v e a d a p t i v eu s e rs e l e c t i o ne n v i r o n m e n t ( p a u s e ) a n dc l o c k - p r o x y a u c t i o no fb e n e f i t s ，b u ta l s oc a nc o n q u e ral o to fi t sv i c e s ，p r o v i d ep r i c e i n f o r m a t i o no na n yb u n d l e ( e x p r e s s i n gb u n d l es y n e r g yi n f o r m a t i o n ，i t w i l lb el o s to rd i s t o r t i o nu n d e rt h el i n e a rp r i c e s ) ，a tt h es a m et i m er e d u c e f r e e r i d e r s t h i st h r e e - s t a g e sa u c t i o nm e c h a n i s mh a ss e v e r a la t t r a c t i v e p r o p e r t i e s i t st h e o r e t i c a ll a n d s c a p ei sv e r yg o o d t h ep a p e ra l s op o i n to u t m u l t i t u d i n o u sc o m b i n a t o r i a lm e c h a n i s m sa p p l i e ds i t u a t i o nt h a tw i l lb e a b l et o p r o b a b l y o f f e r s u g g e s t f o r a c t u a l i z i n g t h es c e n a r i oo f c o m b i n a t o r i a la u c t i o n k e yw o r d s ：a u c t i o nt h e o r y ；m e c h a n i s md e s i g n ；c o m b i n a t o r i a lb i d d i n g ； s y n e r g y i v 湖南师范大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下， 独立进行研究工作所取得的成果。除文中已经注明引用的内容外，本 论文不含任何其他个人或集体已经发表或撰写过的作品成果。对本文 的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本 人完全意识到本声明的法律结果由本人承担。 学位论文作者签名： 詹宝娣沙7 年 6 月s 日 湖南师范大学学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定， 研究生在校攻读学位期间论文工作的知识产权单位属湖南师范大学。 同意学校保留并向国家有关部门或机构送交论文的复印件和电子版， 允许论文被查阅和借阅。本人授权湖南师范大学可以将本学位论文的 全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫 描等复制手段保存和汇编本学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密团。 作者签名： 导师签名： ( 请在以上相应方框内打“ ) 詹宝娣日期：卅年6 月f 诈 日期：加7 年6 月， 日 日 组合拍卖机制设计理论研究 1绪论 1 1 研究背景与意义 拍卖是建立在竞争基础上将稀缺资源分配给对其评价最高者的 一种高效率市场机制，现已成为一种日益重要的经济资源配置方式。 从垃圾家具、精品艺术品的拍卖到债券、专利权的拍卖等等，拍卖的 身影在我们的经济生活中随处可见。此外，政府与私人部门也越来越 多地通过拍卖机制采购或销售商品。但是传统拍卖只是拍卖单一不可 分割又互不相干的物品。随着电子商务的发展，拍卖多单元物品的实 际需要，使经济学家们发现许多传统的拍卖理论和假设已经不再适合 新的拍卖经济环境。因此，需要一些更加符合实际市场特性的拍卖方 式。 人们开始设计并使用一些适合复杂性质物品的拍卖机制。实验表 明在多物品拍卖中，当物品具有很强的协同作用( 互补性或替代性， 尤指互补性) 时，同时叫价拍卖优于序贯拍卖，而组合拍卖优于前两 者。因此多物品拍卖中的组合拍卖在2 0 世纪9 0 年代后成为拍卖领域 的研究热点。 纵观现代拍卖理论的文献，可以发现对拍卖理论的研究基本上是 围绕拍卖机制的选择与设计问题来展开的。因此对组合拍卖理论的研 究，也应从组合拍卖机制设计理论着手。组合拍卖有着与其他拍卖不 同的特性，即赢者决定问题的复杂性与竞争者之间的合作特性。组合 拍卖机制设计必须处理好组合拍卖的这些特性，且不失去拍卖的分配 硕+ 学位论文 有效性、收益最大化、低交易成本、公平、缺少自由和可测性等优良 性质。 目前国外有关组合拍卖机制设计理论的研究文献少之又少，而国 内在这方面还处于刚刚起步阶段，关于组合拍卖机制理论的研究大多 停留在对v c g 机制的推广和延伸，几乎没有其他更进一步的机制理 论研究。随着拍卖在我国市场经济中地位的进一步提高，研究适合实 际市场的拍卖理论的需求变得越来越迫切。因此，深入研究组合拍卖 机制设计理论，无论是对政府部门，还是私营企业或者拍卖行，都具 有非常重要的理论意义和实用价值。 1 2 本文的技术路线及内容框架 本文对组合拍卖的机制设计理论的研究主要采用理论证明、算例 阐释和比较分析等方法。 全文共分五章，基本内容为： 第一章论述全文的研究背景及意义。 第二章首先对传统拍卖理论进行综述，主要介绍几种标准拍卖形 式、拍卖模型、最优拍卖的基本分析与多物品拍卖的分类，并指出传 统拍卖理论已不再适合现有的很多拍卖经济环境。然后介绍了组合拍 卖的基本理论，包括组合拍卖的概况和组合拍卖的机制理论。 第三章着重研究单阶段组合拍卖机制理论，重点讨论v c g 机制、 一级价格组合拍卖、向上叫价代理拍卖的理论模型、拍卖过程、机制 设计问题、机制的优点和缺陷。并对理论价值大且常常成为很多拍卖 机制参照标准的v c g 机制的重要理论性质进行严谨的数学证明。 组合拍卖机制设计理论研究 第四章重点研究多阶段组合拍卖机制，详细讨论两阶段和三阶段 的设计。首先讨论两阶段组合拍卖( 时钟一代理拍卖) 机制设计的基 本程序，研究分析时钟代理拍卖的三大设计问题：需求量变化的限 制、价格增量的设定和拍卖阶段的结束问题。然后研究分析三阶段组 合拍卖机制的设计思想和设计过程，文中的新型三阶段组合拍卖不仅 克服了组合拍卖赢者决定的复杂性问题、信息暴露问题和门限问题而 且又保存了组合拍卖能使竞价人更充分地表达自己的偏好，得到有效 结果的优点。新型三阶段组合拍卖特别适合大量不同物品的拍卖。 第五章研究结论与展望，主要讨论组合拍卖和多阶段组合拍卖的 优势，并指出研究的未来发展方向，为组合拍卖方案的实施提供指导。 本文的创新主要体现在以下几个方面： ( 1 ) 对新兴的组合拍卖机制理论进行了较系统、全面的分析讨论。 ( 2 ) 突破国内外拍卖理论研究文献中只简要举例说明的传统研究 方法，本文对威克瑞拍卖机制的全部重要性质都进行了完整的理论分 析与严谨的数学证明。 ( 3 ) 首次从单阶段和多阶段这一新的视角对组合拍卖机制进行对 比分析，并且文中讨论的新型三阶段混合拍卖机制具有一些十分吸引 人的性质，有着很好的理论前景。 硕+ 学位论文 2 传统拍卖与组合拍卖理论综述 2 1 传统拍卖相关理论综述 2 1 1 标准拍卖形式 拍卖是具有明确规则的市场制度，在参与者竞标的基础上，通过 拍卖规则来决定资源的配置和价格( m c a f e e m c m i l l a n ，1 9 8 7 ) 。拍卖 作为一种交易方式，是价格发现方式之一，它具有很多吸引人的性质。 比如：分配有效性，收益最大化，低交易成本，公平，等等。 1 9 6 1 年威克瑞在他的论文反投机，拍卖和竞争性密封投标 中对传统拍卖进行了分类。威克瑞认为，应该按照管理拍卖的不同制 度规则来划分拍卖业，因为拍卖规则能影响交易报盘的动机，从而影 响交易的条件与效率。根据威克瑞的观点，标准的拍卖分为四类：英 式拍卖( 或称升价拍卖) ，荷式拍卖( 或称降价拍卖) ，第一价格密封 拍卖，第二价格密封拍卖( 或称威克瑞拍卖) 。 在升价拍卖中，价格逐步提高，直到只剩一个买方为止，该买方 以最后的价格赢得标的物。这一拍卖既可以由卖方报价，又可以由买 方各自报价，还可以借助显示当前最高价格的电子报价器来进行。古 董和艺术品拍卖通常都是升价拍卖。 降价拍卖与升价拍卖的形式完全相反。卖方设一个极高的开始价 格。拍卖开始后，价格逐步降低，直到有人愿意购买为止。最终价格 为该时刻所显示的价格。易腐、有保质期的商品，比如：鲜花、鱼、 组合拍卖机制设计理论研究 烟草等的拍卖通常采用降价拍卖。 在一级价格密封拍卖中，各买方不知道其他买方的出价，每一买 方单独提交其报价，出价最高的买方赢得标的物。最终价格为该赢家 的报价( 即价格是最高的或“第一价格”) 。政府拥有土地的采矿权拍 卖、房地产拍卖等通常都是一级价格密封拍卖。 在二级价格密封拍卖中，每一买方在看不见彼此出价的情形下独 立出价，出价最高的人赢得该标的物。与一级价格密封拍卖不同的是， 赢家出的价钱不是他自己的出价，而是第二高的出价，或者“第二价 格”。邮票拍卖和某些网络拍卖通常用第二价格密封拍卖。 2 1 2 拍卖的基本模型 一般对拍卖的经济分析分为二大理论模型。一是v i c k e r y 在1 9 6 1 年提出的私有价值( p r i v a t e v a l u e ) 拍卖模型。买方都有一个独立的 私人价值。买方对拍卖商品的最大愿意支付为其私人的价值；买者不 知道其他买者的私人价值，但他知道所有买者私有价值服从相同的均 匀概率分布，即对其他人的私有价值，买者中问存在着对称的不完全 信息，并形成了共同知识。可将拍卖品的真实价值视为随机变量v ； 在n 个买者中，概率分布为f i ，根据f i 得出v i 。后来发展为对称、 独立的私人价值( s y m m e t r i ci n d e p e n d e n tp r i v a t ev a l u e ) 拍卖模型。这 个模型的特征是：( 1 ) 把单个不可分割的物品卖给几个投标者中的一 个( 单个物品拍卖) ；( 2 ) 每个投标者都知道他自己的估价但其 他人不了解他的估价( 私人估价) ；( 3 ) 所有投标者都相同( 对称性) ； ( 4 ) 私人估价足服从独立同分布( i i d ) 的连续的随机变量( 独立、 硕+ 学位论文 对称和连续) ；( 5 ) 投标者和拍卖人都是风险中性的。此模型是我们 最为熟知的基准理论模型。 二是共同价值( c o m m o nv a l u e ) 拍卖模型。如果v 是不可观察 的实际价值，而投标者的评估价值( p e r c e i v e dv a l u e ) v 独立地来自于某 种概率分布函数h ( v , i ，v ) ，i = l ，2 n ，所有的参与者都知道该分布函数， 这称为共同价值模型。在共同价值模型中，拍卖商品的价值对所有投 标者而言是相同的，但是在出价时投标者并不知道拍卖商品的真正价 值，而只得到有关其价值的价值信号。在共同价值拍卖中的判断失误 被称为“赢者诅咒 。尽管所有投标者对拍卖商品的价值都拥有一个公 正的估计，但毕竟是不完全的估计。假设其出价函数相似，那么只有 拥有最高估价的投标者才能赢得拍卖品。然而这一最高估价很可能偏 高，因而出价最高的投标者由于赢得拍卖品并支付远高于其价值的代 价而受到诅咒。比方说在一个共同价值拍卖中，拍卖品的价值对所有 投标者是相同的，而每一个投标者由于对提供估价的信息有偏差，于 是对共同价值会有截然不同的估计。由于较高的估计意味着较高的价 值，因而拥有较高估计的投标者就会提出较高的出价。结果，出价最 高的投标者经常也就是拥有对拍卖品价值估计最高的投标者。就这方 面而言，赢得拍卖品的投标者的估价很可能偏高。除非其在拍卖事先 已经考虑了这一问题，否则其结果必定是要支付高于拍卖商品价值的 代价。 在真实世界中，大多数拍卖往往同时包括了私人价值因素和共同 价值因素两个方面。比如，一幅油画拍卖的投标者可能因其作为私人 组合拍卖机制设计理论研究 价值因素的个人喜好而购买之，也可能作为反映共同价值因素的投资 和最终再售而出价竞标。米格罗姆( m i l g r o m ) 和韦伯( w e b e r ) ( 1 9 8 2 a ) 发展了关于关联信息拍卖的一般理论，建立了“关联价值模 型”( a f f i l i a t e dv a l u e ) 成功地将私人价值模型和共同价值模型都纳入其 中。他们文章的主要结论是，升价拍卖b k - - - 级价格密封拍卖能拍出更 高的价钱，而二级价格密封拍卖又会比一级价格拍卖拍出更高的价 钱。 2 1 3 最优拍卖的基本分析 2 1 3 1等价收入定理 1 9 8 1 年m y e r s o n r i l e y 和s a m n e h o n 几乎同时证明了威克瑞关于 各种标准拍卖机制的期望收入等价这一结论的一般性。假定数量既定 的众多风险中性的潜在买主中的每个人都独立地获得对拍卖品的私 人估价，且这些估价服从一个共同的、严格递增的非原子分布，那么 任何具有以下特征的拍卖机制都将产生同样的期望收入( 并导致每个 投标者按自己估价的某个函数支付相同的期望金额) ：( 1 ) 拥有最高 信号的投标者总是赢家；( 2 ) 任何拥有最低可行估价的投标者的期望 剩余为零。这个结论意味着卖主选择四种标准拍卖方式中的哪一种都 无关紧要。 等价收入定理极其重要，很多拍卖理论的结论都可以用这一定理 来解释。 2 1 3 2 最优拍卖机制 所谓机制是指为控制参与者之间的相互作用而设置的一套规则。 硕士学位论文 迈耶森( m y e r s o n1 9 8 1 ) 引导了发展机制设计理论，此理论能让研究 者刻画描述所有拍卖机制的均衡结果和认出什么样的机制可能是最 优的收入最大化或是社会有效配置。他借助于“显示原理 将最优 机制的搜寻范围缩小到激励相容性直接机制上，并将最优拍卖机制问 题转化为一个双重约束的线性规划问题：即在参与约束和激励相容约 束下求卖主的最大期望剩余。沿着这一思路，将最优拍卖机制概括为 两套规则：( 1 ) 配置规则：要求每个投标者报告自己的估价，卖主计算 相应的边际收益，然后将拍卖品授予边际收益最高者，除非最大边际 收益低于卖主自己的估价( 边际成本) 。若所有边际收益都低于卖主的 估价，卖主将保留拍卖品。( 2 ) 支付规则：赢家支付的金额既非他的 边际收益亦非他的报告估价，而是使其边际收益等于或高于所有竞争 对手的边际收益以及卖主边际成本的最低估价。 2 1 4 多物品拍卖的分类 近年来，多物品拍卖的研究成为目前拍卖理论中最为活跃的领域 之一。但是关于多物品拍卖的分类目前还没有统一的方法。这里按照 拍卖规则的不同方面而对多物品拍卖进行了大致的分类。在多物品拍 卖时，按照拍卖品的顺序，拍卖可以分为序贯拍卖( s e q u e n t i a la u c t i o n ) 和同时拍卖( s i m u l t a n e o u sa u c t i o n ) 。序贯拍卖中，拍卖品一个接着 一个的进行拍卖；同时拍卖中，几个甚至全部拍卖品同时进行拍卖。 按照投标者是否要考虑拍卖品之间的关系，拍卖可以分为组合拍卖 ( c o m b i n a t o r i a la u c t i o n ) 和非组合拍卖( n o n c o m b i n a t o r i a la u c t i o n ) 。 组合拍卖中一般拍卖品之间具有协同关系，投标者必须综合考虑对各 组合拍卖机制设计理论研究 个拍卖品的投标。按照拍卖双方人数的对应关系，拍卖可以分为单向 拍卖( s i n g l ea u c t i o n ) 和双向拍卖( d o u b l ea u c t i o n ) 。在双向拍卖中 多个卖家对应多个买家。按照买卖的次序方向，拍卖可以分为正向拍 卖( p o s i t i v e a u c t i o n ) 和反向拍卖( r e v e r s ea u c t i o n ) 。常说的采购拍 卖即是反向拍卖。按照拍卖的阶段数，拍卖可以分为单阶段拍卖 ( s i n g l e s t a g ea u c t i o n ) 和多阶段拍卖( m u l t i s t a g e sa u c t i o n ) 。按照 拍卖保留价的有无，拍卖可以分为有保留价拍卖( r e s e r v ep r i c e ) 和 无保留价拍卖，等等。 2 2 组合拍卖的相关理论综述 2 2 1 组合拍卖的概况 组合拍卖是多物品拍卖的方式之一，当卖方要拍卖多个物品，这 些物品之间又存在着互补性和替代性时，组合物品的效用比单个物品 的总的有效性大( 例如，一双鞋的价值远远超过单独一只左鞋的价值 加上单独一只右鞋的价值) 。组合拍卖是指那些竞标者能把标的放在 一个组合的物品，叫做“包裹”的组合物品，而不是单个物品的一种拍 卖。组合拍卖有利于竞价人能更充分地表达他的偏好。允许竞价人更 充分地表达他的偏好常常导致经济有效率的改善( 分配物品给那些估 价最高者) 和更多的拍卖收益。组合拍卖方式最早在1 9 8 2 年被建议 用于美国航空部门和市政府拍卖飞机场的停机位，英国伦敦的运输部 门也用组合竞投方式来分配巴士营运的路线，以及货车运输公司对于 运输合同的获得。对组合拍卖的学术研究始于上世纪8 0 年代， r a s s e n t ie ta 1 19 8 2 和b a n k se ta 1 19 8 9 发表的论文常被认为是这领域 硕十学何论文 的早期工作。从9 0 年初期至中期，关于f c c 通讯频道组合拍卖机理 设计问题引发了一场空前的争论，最后由于其在实施中的计算复杂性 而被认定为不合实际。最近几年随着计算技术的发展和互联网中电子 商务的崛起，使得这一拍卖形式很快重新成为学术界和b 2 b 专家高 度关注的焦点。 目前在国内有关组合拍卖理论的研究简略回顾如下： 陈培友，汪定伟( 2 0 0 6 ) 提出了电子商务b 2 b 采购合同的反向 组合拍卖机制，建立了反向组合拍卖的多物品最优组合供应模式确定 问题的数学模型，并设计了求解该模型的两级优化算法，最后以应用 实例说明了模型的普适性和算法的有效性。 金津石纯一( 2 0 0 6 ) 通过对i b u n d l e 拍卖方法的扩展，提出了一 种多活性级的递增叫价组合拍卖方法，并给出了理性买方策略。买方 可对物品组合在不同的活性级上加价，使得拍卖兼顾了时间复杂度和 效用。 吕赐兴，朱云龙，尹朝万，于海斌( 2 0 0 6 ) 为了解决基于多智能 体的敏捷生产调度中资源分配的协商策略问题，提出了实现组合拍卖 的协商策略的解决方法。 黄河，陈剑( 2 0 0 7 ) 从多物品采购活动出发，在考虑具有质量竞 争的采购拍卖环境下，通过对原有v c g 机制的修改和扩展，设计了 q a v c g 机制和改进q a v c g 机制，在保证分配效率的基础上，从 采购商的利益出发，兼顾收益最大化的目标。 当前的关于组合拍卖的大多数学术论文都是关于组合拍卖某一 组合拍卖机制设计理论研究 方面技术问题的研究。如计算科学家注重于发展最快启发式算法和对 各种可能的组合拍卖模型的赢者决定复杂性的进一步分析，运筹专家 注重整数规划( i p ) 公式，经济学家注重实验研究，同时博弈论专家 注重理论特性研究。关于组合拍卖机理设计及其具体实施的细节资料 很少。国内关于组合拍卖的研究也才刚刚起步，而关于组合拍卖机制 理论的研究大多停留在对v c g 机制的推广和延伸，几乎没有其他更 进一步的机制理论研究。 2 2 2 组合拍卖机制理论 术语“组合拍卖 常用于描述机制：( 1 ) 同时销售多个物品，( 2 ) 允许“所有或一全无”竞标在这些物品的组合。例如，如果物品a ，b 和 c 被拍卖，在组合 a ，b i _ k 的一个“所有或全无”竞标是指要么赢得a 和b 两个，要么没有一个，不允许部分的分配。组合拍卖区别于其他 拍卖模型的两个特征是：赢者决定问题的复杂性和竞争者之间的合作 因素。决定拍卖赢者通常在一个非组合拍卖很容易，只要找出放置了 最高竞标的竞价人。然而，在组合拍卖，在物品组合上的最高竞标不 保证会赢。例如，假设有3 个待售物品：a ，b 和c 。在组合 a ， b ， c ，) a ，b ) ， a ，c ， b ，c ) ， a b c 上的最高竞标分别为1 ，3 ，2 ，5 ， 5 ，4 ，6 美元。如果 a ，c 被卖5 美元和物品b 被卖3 美元，则拍卖收 益最大。因此，在 a ， c ， a ，b ) ， b ，c ) 和 a , b ，c ) 上的高竞标没有赢标。 因此，决定组合拍卖赢者不那么简单。已经证明组合拍卖的赢者决定 问题是n p 完全问题( 见r o t h k o p f e ta 1 1 9 9 8 ) 。另外，组合拍卖里的 竞标是带有合作意味的竞标。因为不同方式的分割待售物品集形成一 硕十学位论文 个可行分配，对任意物品组合的竞标人( 除了所有物品的组合) 受限 于在互补物品上的竞标。在前例里，在组合 a ，b ) 上5 美元的竞标不能 变成一个赢标，因为没有在 c 上的足够高的竞标。这种合作特征妨 碍拍卖赢者决定的方式和完全不同于非组合拍卖。 已经知道，在多物品拍卖机制中，当物品之间具有很强的互补性 时，很多拍卖设计都不尽如人意。这表现在不同方面，如拍卖结果效 率的降低、买方的收益非竞争性的降低、易于合谋、竞价人难以确定 其报价策略、拍卖持续时间变长等等。在讨论美国联邦通信委员会 ( f e d e r a lc o m m u n i c a t i o n sc o m m i s s i o n ，f c c ) 宽带私人通信服务许可 证的拍卖方案过程中，查理普劳特( c h a r l e sp l o t t ) 关于序贯拍卖、 同时叫价拍卖以及组合拍卖这三种拍卖方式相关性能的实验结论的 报告为：当物品之间具有很强的协同作用时，同时叫价拍卖优于序贯 拍卖，而组合拍卖优于前两者。 因此组合拍卖设计需要在赢者决定的计算上的复杂性、竞争者之 间合作的竞标的影响力与吸引人的拍卖性质( 分配有效性，收益最大 化，低交易成本，公平，缺少自由和可测性等等) 之问进行平衡。组 合拍卖设计必须处理暴露问题( e x p o s u r ep r o b l e m s ) 和门限问题 ( t h r e s h o l dp r o b l e m ) ，保持竞标移动在一个合理的步调，避免和解决 平局，控制复杂性。 目前组合拍卖机制在理论上主要有以下的类型：威克瑞组合拍 卖、一级价格组合拍卖、向上叫价代理拍卖、时钟代理拍卖和重复组 合拍卖。对于组合拍卖机制的设计，理论上单阶段研究的较多，而多 组合拍卖机制设计理论研究 阶段的研究少见。多阶段组合拍卖更有利于市场信息的揭示，吸引进 入，防止合谋，更易于拍卖者控制以达到拍卖的各种目标。 硕十学位论文 3 单阶段组合拍卖机制理论 3 1 威克瑞组合拍卖机制设计 3 1 1v c g 机制理论模型 威克瑞( v i c k r e y , 1 9 6 1 ) 在他的著名论文反投机，拍卖和竞争性密 封投标中，以简明的对策论语言引入了一种给参与者以足够的激励 去显示出他们在均衡时对物品偏好的机制，分析了不同种类的拍卖市 场体制，创造性地提出了第二价格拍卖法，即“威克瑞拍卖法”。他例 证了一个特别的价格规则对竞价人报告他们的真实估价是一个占优 策略，甚至当他们知道他们报告的估价将被用于有效的分配物品时。 威克瑞的最初问题处理是对单一物品拍卖和多种相同物品拍卖 提供一种机制。机制对竞价人真实报告他们的估价是一种占优策略， 并且结果有效。对单一物品而言，机制常用于作为第二价格密封拍卖 或简单的威克瑞拍卖。竞价人同时对物品递交密封的竞标，最高的竞 价人赢得物品，但赢者支付总数的第二高竞标价。例如，如果赢者竞 标1 0 ，最高失标者竞标8 ，则赢者支付8 。 对多种同类物品而言，威克瑞的最初处理是假设在连续或不连续 的数量里，竞价人对物品有单调非增的边际估价。竞价人同时递交密 封竞标组成需求曲线。卖者组合单个需求曲线的一般方式决定总的需 求曲线和对s 物品的出清价格。每个竞价人在出清价格上赢得他需求 的数量。然而，不管是竞标的支付价格或对他的单元的出清价格，赢 组合拍卖机制设计理论研究 者对他赢得的物品支付机会成本。 在不连续的情况下，描述多物品的威克瑞拍卖的等价方式是每个 竞价人递交分离的竞标数量，每个代表一种提供去买一个物品，这些 单元竞标描述了竞价人的需求曲线。拍卖者接受s 最高竞标。如果竞 价人刀赢得k 物品，那么他支付被拒绝的其他竞价人的k 个最高价。例 如，如果一竞价人赢得二物品，最高被拒绝的其他竞价者是1 2 和11 ， 那么竞价人对他的二物品支付2 3 。 因为威克瑞的最初贡献，他的拍卖设计已经结合了c l a r k e g r o v e s 对公共物品问题的设计。对异种物品的拍卖设计工作的结论也和同种 物品一样，不需要威克瑞最初设计的竞价人有非增的边际估价，这个 机制仍有效地分配物品，仍是竞价人支付他们赢得物品的机会成本。 主要的不同是支付的数量不能一般地作为对单个物品的竞标总和来 表示。延拓的威克瑞机制有各种名字。在这里叫它 v i c k r e y c l a r k e g r o v e 或v c g 机制。 v c g 模型描述如下： 假设，= 1 ，2 ，i ，) 是竞价人集，g = 1 ，2 ，g ) 是所有物品的 集合，圪( 彳) 为任意物品集a 的估价。，6 = 彳：gjd 是物品g 分配给竞 价人，的集合，其中若有某些物品没有被分配出去，那么系统就引入 哑拍卖者。 竞标：每个竞价人i 报告一个估价函数吃给拍卖者。 计算：拍卖者计算一个估价最大的分配a ，g ，使得 m a x z i i ；( 爿) 。这样的分配是v c g 拍卖的结果，所有拍卖的物品将按 硕士学位论文 照这个分配方式卖出去。 支付：拍卖者对竞价人i 所支付的价格p i 进行计算，计算公式如下： b = 吃( 一，) - z v “j ( a )( 3 - 1 ) j 商j 譬i 其中a 一，g 表示除了竞价人i 外的其他竞价人的一个最优分配， 也就是，竞价人i 根据分配来支付自己的物品价格p i 。例如，假设 有两物品出售( 彳和b ) 和两个竞价人刀= 1 ，2 递交竞标：i ；：l ( 彳) 对物品彳， 吃( 召) 对物品b ；i ；：l ( 彳b ) 对两物品的组合。不失一般性，假设 i ；：( 彳b ) 吃( 彳b ) ，l ；：( 彳) + 吃( b ) i ；：( 曰) + 吃( 彳) 。如果i ；：( 彳b ) _ i ；：( 彳) + 吃( 召) ， 那么竞价人1 赢得两物品，由公式知，他的支付为吃( 么b ) 。然而，如 果i ；：( 彳b ) - 0 ，使得( i ) 在价格向量( 瓦，卫。) 上，买方( 对所有物品) 的需求量唯一，并且矗1 ( 死，p 一。) = 1 ；( i i ) 在价格向量( 瓦+ ，n 。) 上， 买方( 对所有物品) 的需求量唯一，并且吒1 ( 瓦+ s ，p 一肌) = 0 ；因为效用 是拟线性的，所以我们可推知1 = 吒1 ( 瓦，卫。) 1 ( 死+ s ，n 。) = 0 。由连 续性知，存在( 碗，瓦+ 占) 使得在价格向量p = ( ，p 一。) 处买方的需求 集合中存在一个包括物品刀和m 的组合，同时也存在另一个不包括这 两件物品的组合。( 注：对任一竞价人，和物品m ，有7 o ，1 ) 。) 因而，替代条件不成立意味着存在两件物品刀和m 和一个价格向 量p ，其中p p i9 p 。 - 0 ，并且p 满足以下两个性质：( 1 ) 对所有的 丸 o ，p 。) ，1 ，1 ( 石) 一( p 。，口。) x 有唯一的最大值点石，且= = 1 ；( 2 ) 对 所有的p 。( ，曰】，v 1 ( x ) 一( 丸，p 一。) x 有唯一的最大值点x 。，且= = 0 。 ( 这里b 表示一个很大的数，它超过任一物品对任一联盟的增加值。) 设p 。 - p 。，假设竞价人2 ，竞价人3 和竞价人4 对物品的估价分 别为：v 2 c x ) = z k ，：t l j np 。x k ，y 3 ( x ) = p 。x m + 以x n ，v 4 ( x ) = 多。x m 。因为在价格 向量p 上x 对于买方1 是最优的，又因为= 吒= 1 ，所以存在联盟 o ，1 ，2 ，3 ) 的一个最优分配，其中买方3 没有分得物品。因而，这个最 优分配对联盟 o ，1 ，2 ) 也是可行的。故有w ( 0 1 2 3 ) = w ( 0 1 2 ) 。因为在价格向 硕士学位论文 量( n 。，p 。) 上x 。对于买方l 是唯一的最优分配，所以联盟 o ，1 ，2 ，3 ，4 ) 的 最优分配中，物品玎分配给了竞价人3 ，从而它不同于联盟 o ，1 ，2 ，4 ) 的 最优分配，所以w ( 0 1 2 3 4 ) _ w ( 0 1 2 4 ) 。因此竞价人4 的联盟收益： 万4 ( 0 1 2 3 4 ) = w ( 0 1 2 3 4 ) 一w ( 0 1 2 3 ) - w ( 0 1 2 4 ) 一w ( 0 1 2 ) = 万4 ( 0 1 2 4 ) ( 木) 所以卖者的联盟收益 万。( 0 1 2 4 ) = w ( 0 1 2 4 ) - ，。 1 2 4 l 万7 ( 0 1 2 ) = 似0 1 2 4 ) + w ( 0 1 2 3 4 ) 一w ( 0 1 2 4 ) 一万3 ( 0 1 2 3 4 ) 一，e 1 2 4 万7 ( 0 1 2 ) = w ( 0 1 2 3 4 ) 一万3 ( 0 1 2 3 4 ) 一1 a 1 2 4 万7 ( 0 1 2 ) w ( 0 1 2 3 4 ) 一蚓1 2 3 4 万7 ( 0 1 2 3 4 ) = 万。( 0 1 2 3 4 ) 由此知，增加竞价人3 ，卖者的均衡收益反而减少了。 威克瑞拍卖的缺陷之三是在物品不可替代时，威克瑞拍卖有合谋 的现象，因为在失标者之间存在有利可图的联合偏离。# 例证如下： 记为物品i l ，2 ) 的价值，矿为这两个物品的联合价值。对于竞价人 彳，如果这两个物品是不可替代的，则他的估价有口= 矿一( h + 吃) _ 0 。 引入竞价人e 和垦。竞价人e 对物品i 的估价为v i + o - v i ，其中 q + 乞 _ ，其中毛+ 占：_ 0 。所以，如果物品是不可替代的，那么 对于竞价人b 来说，采用托投标是有利可图的偏离。 威克瑞拍卖的缺陷之四是当竞价人有限制预算时，威克瑞拍卖占 优策略的性质打破了。例如，考虑一个拍卖每个竞价人有一个1 2 亿 的预算。估价分别从预算决定：他们反映了竞价人利润的净现值增量。 如果它获得特别的频谱许可证。竞价人a 对单个许可证估价1 亿或 对两个估价2 亿。竞价人b 和c 每人只需一个许可证。对竞价人b ， 一个许可证的估价为o 8 亿。竞价人c 的估价对其他竞价人而言未知， 因为他依赖于c 是否能在拍卖外获得一个特别的可替代品。根据情 况，竞价人c 也许愿意支付1 1 亿或0 对一个许可证。在威克瑞拍卖 里，竞价人a 应该赢得两个许可证或者一个许可证，这依赖于最后 的竞价人的决定。可选择情形下，他的总支付将为o 8 亿，因此它的 预算总能够满足它的威克瑞支付。然而，如果a 的预算限制约束它