（产业经济学专业论文）组合拍卖的非合作博弈分析.pdf

摘要 拍卖已经成为微观经济学、博弈论以及产业经济学的重要研究对象。电子商 务和计算机技术迅速的发展，将拍卖机制的应用范围扩大到性质复杂的标的物， 这对传统的单一物品拍卖方式提出了挑战。近年来，人们开始设计并试用一些适 合复杂性质物品拍卖的方式。 组合拍卖主要适用于市场中被拍卖物品间的互补替代关系比较重要的时 候。本文的目的就是以具体拍卖市场为基础建立组合拍卖模型，从一般模型的角 度研究组合拍卖问题。在研究方法上，鉴于拍卖行为是一种竞争性的非合作行为， 而博弈论是研究非合作行为的一种好工具。因此以非合作博弈作为本文的一个主 要分析方法。 在回顾国内外学者对拍卖理论、多物品拍卖方式以及组合拍卖的研究之后， 从组合拍卖的实践背景中归纳组合拍卖的特点，利用相关理论背景明确组合拍卖 所包含的一般问题，然后建立组合拍卖一般模型。主要采用博弈论中非合作博弈 的思想，结合最优机制设计的研究方法，从理论上分析组合拍卖模型，通过对组 合拍卖中投标人策略、拍卖人箢略、最优机制等方面的具体分析，从理论上说明 组合拍卖是一种最优机制。最后利用模拟组合拍卖市场中的投标行为验证模型， 即模拟两组允许投标人对感兴趣的物品提交组合投标的投标结果，将使用整数规 划的方法得出的物品分配结果与物品分开拍卖得出的分配结果进行比较，综合激 励、拍卖人收益、投标人的最终所得和是否存在赢者诅咒现象这四个方面的比较 结果，最后得出，当物品问互补关系重要时，组合拍卖在大多数方面是优于将这 些物品分开拍卖的结果。 通过对于组合拍卖的理论与实践分析之后，希望组合拍卖的优越性能够在实 际应用中得到充分利用，像国内的电力市场中电能分配、电子商务中互补物品的 拍卖以及卡车配货等近似组合拍卖的市场中，“卖主”能够通过组合拍卖获得更 大收益。 关键词：组合拍卖；机制分析：最优机制 a b s t r a c t t h ea u c t i o nh a sb e c o m ea n i m p o r t a n tp a r to fm i c r o e c o n o m i c s ，g a m et h e o r ya n d i n d u s t r i a le c o n o m i c s t h ed e v e l o p m e n to f e l e c t r o n i cc o m m e r c ea n dc o m p u t e r t e c h n o l o g yo f f e r sap r o m i s i n gf i e l df o ra p p l y i n ga u c t i o nm e c h a n i s m ，m o r ec o m p l e x p r o d u c t st r yt ou s ea u c t i o nw a y t oa l l o c a t e ，s oi t b r i n g st h ec h a l l e n g et ot r a d i t i o n a l s i n g l e o b j e c t a u c t i o nm o d e i n v e s t i g a t o r st r yt ou s et h ec o m p l e xa u c t i o nc r e a t e d s e v e r a la u c t i o n sm o d eo nt h ep a r t i c u l a ra u c t i o nw h i c hs u i tf o rc o m p l e x p r o d u c t s c o m b i n a t o r i a la u c t i o n sa r e u s u a l l ya p p l y i n gw h e nt h ec o m p l e m e n t a r i t y a n d s u b s t i t u t a b i l i t yr e l a t i o n sv a r ya m o n g t h e s ea u c t i o n s n ep u r p o s eo ft h i sp a p e ri st o s u m - u pc o m b i n a t o r i a la u c t i o n sm o d e lw h i c hb a s e do np a r t i c u l a ra u c t i o nm a r k e t ，t o s t u d y t h ec o m b i n a t o r i a lp r o b l e m sf r o mt h ea l l 露eo f c o m m o n l y m o d e l o nt h ew a yo f s t u d y , w h e r e a sa u c t i o nm a n n e ri s ac o m p e t i t i v en o n c o o p c r a t ep e c u l i a r i t y , b u tt h e g a m e t h e o r yi s t h e r e f o r e n o n c o o p e r a t eg a m e i st h em o s t i m p o r t a n ta n a l y s i si nt h i s p a p e r a f t e r1 0 0 kb a c kt h ea u c t i o nt h e o r y , m u l t i o b j e c tm o d ea n dt h es t u d yo fa u c t i o n b y t h es c h o l a ro fh o m ea n da b r o a d ，t h r o u g l lt h ep r a c t i c eb a c k g r o u n do fc o m b i n a t o r i a l a u c t i o ns u m - u pt h ep o i n to f i t ，m a k eu s eo f t h eb a c k g r o u n do fr e l e v a n tt h e o r yt os h o w t h e c u r r e n t l yp r o b l e m si n c l u d e ，i n t e g r a t e t h e s p e c i a l t ya n dc u r r e n t l yp r o b l e m so f c o m b i n a t o r i a lt ob u i l dc o m b i n a t o r i a la u c t i o nc o m m o n l ym o d e l t h ea n a l y s i so f m o d e l sm a i n l ya d o p tt o n o n c o o p e r a t eg a m et h o u 【g h t s i ng a m et h e o r ya d du pt o o p t i m a lm e c h a n i s m t od e s i g nt h es t u d ym e t h o d t h r o b g ht h ea n a l y s i so ft h es t r a t e g y o fb i d d e r si nc o m b i n a t o r i a la u c t i o n s ，t h es t r a t e g yo fa l l c t i u n e e ra n dd e d u c eo p t i m a l m e c h a n i s mf r o mt h ea n a l y s i so fc o m b i n a t o r i a la u c t i o nm o d e li nt h e o r y 1 1 h e nw e r k o a tc o m b i n a t e r i a la u c t i o ns u i t sf o rd e s i g n e db yo p t i m a lm e c h a n i s m t h e nm a k eu s eo f t h eb i di ns i m u l a t ec o m b i n a t o r i a la u c t i o nm a r k e tt ov a l i d a t ei t w ec a nc h o o s et w o g r o u p s o ft h e o b j e c t sw h i c h t h eb i d d e r si n t c r e s t e dt os u b m i tt h er e s u l t ，t oc o m p a r et h e t w oa s s i g nr e s u l t s ，a d du pt os y n t h e s i z ei n s p i r i t ，b e n e f i to fa u c t i o n e e r , b i d d e r si n c o m e a n dw h e t h e re x i s tw i n n e r sc u r s ef o u r a s p e c t s a tl a s t w o r k so u tt h a tw h e nt h e c o m p l e m e n t a r i t yi sm o r ei m p o r t a n t c o m b i n a t o r i a la u c t i o ni so v e r m a t c h e dt oo t h e r s f o rt h em o s tt i m e t h r o u g ht h et h e o r ya n dt h ea n a l y s i s o fp r a c t i c e ，w eh o p et h ea d v a n t a g eo f c o m b i n a t o r i a la u c t i o nc a nm a k et h eb e s ti nt h ep r a c t i c a la p p l i c a t i o n ，l i k ee l e c t r i c i t y a l l o ti nt h ee l e c t r i c i t yp o w e rm a r k e t ，c o m p l e m e n t a r i t yo b e c t sa n c t i o ni ne 1 e c t r o n i c c o m m e r c ea n d c o m p o u n d t h el o r r yg o o d s ，v e n d e r sc a na c h i e v em o r eb e n e f i t st h r o u g h c o m b i n a t o r i a la u c t i o n k e y w o r d s ：c o m b i n a t o r i a la u c t i o n ；a n a l y s i so fm e c h a n i s m ；o p t i m a lm e c h a n i s m 独创性说明 作者郑重声明：本硕士学位论文是我个人在导师指导下进行的研究 工作及取得研究成果。尽我所知，除了文中特别加以标注和致谢的地方 外，论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得 大连理工大学或其他单位的学位或证书所使用过的材料。与我一同工作 的同志对本研究所做的贡献均已在论文中做了明确的说明并表示了谢 意。 作者签名：盎薹 日期： ，媳。6 ji y 组合拍卖的非合作博弈分析 1 引言 拍卖是世界上最古老的价格发现机制之一，应用非常广泛，最早可以追溯到 公元前5 0 0 年的巴比伦。拍卖可以是为一单件物品或一个单元物品进行的，比如 我国商业银行处理抵押品时对楼房或汽车等物品的单件拍卖；也可以是为整批或 整包不同物品的组合而进行的，比如国有企业改制中对于全部闲置的国有资产、 破产企业或小型企业资产的拍卖；或者，拍卖还可以是为待售的多单位同类标准 化物品而进行的，比如2 0 世纪7 0 年代国际货币基金组织和美国财政部进行的金 块拍卖，美国财政部每周一次对期限为9 1 天和1 8 2 天的证券进行的拍卖【”，以 及中国政府与事业单位的采购等。拍卖问题的研究目前已经成为微观经济学重要 的组成部分，并且对该理论的研究也扩展到应用经济学以及产业组织理论等领 域。 1 1 问题及研究意义 组合拍卖，也叫组合竟价拍卖，是多单位可能不同物品拍卖的一种方式。当 被拍卖物品之间的关系是非独立的，尤其是可能有互补关系时，投标人在进行评 估时，与把这些物品分开独立评估的价值相比，投标人对其中的某个或某几个物 品组合起来的评价可能更高。拍卖物品具有互补关系的特点决定了不可以简单地 通过扩展基本拍卖理论的方法来研究。在研究组合拍卖时，除了分析框架用的是 基本拍卖理论外，其理论分析主要借鉴的是多单位产品拍卖机制理论。包括最 佳多单位拍卖理论、可分多产品拍卖理论、多产品捆绑包拍卖理论等。目前组 合拍卖理论研究主要集中在竟胜标的分配算法上，而很少有研究者在组合拍卖一 般模型的层次上分析包括竟标策略、最优拍卖机制分析以及福利等一般问题。 本文试图在一般化的组合拍卖模型水平上研究拍卖理论，包括建立组合拍卖 模型，投标人最优策略分析、拍卖人分配算法及方式分析、组合拍卖最优机制分 析、以及福利等问题。并且对于组合拍卖的最优性进行验证。 从一般化模型水平上来研究组合拍卖问题，除了对拍卖理论有所补充外，主 要是为了能够利用模型得出普遍适用的解概念和最优解，对组合拍卖或类似组合 拍卖的市场中的拍卖人和投标人的决策提出一个可供参考的基本可行策略。 组合拍卖的非台作博弈分析 1 2 拍卖理论综述 1 2 1 拍卖基本理论 所谓拍卖就是一组确定谁是获胜者以及获胜者支付价格的规则，必要时拍卖 规则还会对拍卖的参与、可行的投标等作一定限制并规定一定的行为准则i 羽。拍 卖的最大特点是，价格由竞争的方式决定，不是由卖方说了算，也不是由买卖双 方讨价还价来确定。竞争决定价格的优越性源于非对称信息，卖方不完全知道潜 在买方愿意出的真实价格，这种信息通常只有买方自己知道。每一潜在买方也不 知道其他买方可能的意愿出价。拍卖的竞价过程可以帮助卖方收集这些信息，从 而把物品卖给愿意支付最高价格的买方。这不仅达到资源有效配置，也使得卖方 能够获得最离收益【3 1 。使用拍卖机制的主要原因主要有三点：加快销售速度；显 示有关买者估价的信息；防止卖方代理人与买者之间的不诚实交易1 2 】。 拍卖理论进入经济学文献的时间相当晚，直到2 0 世纪7 0 年代末，越来越多 的博弈论研究者意识到拍卖是一种简单而又具有完备定义的信息不对称经济环 境，它是分析经济主体之间的不完全信息博弈的一个颇有价值的实例，其经验研 究前景也非常诱人。与此同时，实验经济学者对于可控拍卖实验的兴趣也不断高 涨。在这一背景下，拍卖理论逐渐被主流经济学家所接纳，并大量运用博弈论、 实验以及经验检验作为拍卖理论的研究工具1 4 l 。 在现实生活中存在许多不同的拍卖规则，这些规则非常重要，因为它们能影 响报盘的动机，从而影响交易的条件和效率。拍卖理论分析普遍使用的4 个基本 拍卖机制是：增价拍卖( a s c e n d i n g - b i da u c t i o n ，也口q 做公开、口头、或者英国拍 卖) ，减价拍卖( d e s c e n d i n g - b i da u c t i o n ，也叫做荷兰拍卖) ，第一价格密封投标 拍卖( f i r s t p r i c e s e a l e d b i da u c t i o n ) ，和第二价格密封投标拍卖( s e c o n d p r i c e s e a l e d - b i da u c t i o n ，也叫做v i c k r e y 第二价格拍卖) 。拍卖中买卖各方面临的环境 不同将导致不同的经济模型：独立私有价值模型、公共价值模型以及介于两者之 间的关联价值模型【l 】1 2 嘲郇。在独立私有价值模型中4 种基本拍卖机制会产生同等 的平均收益( 或价格) ，并且都能获得最有效的配置资源结果【5 1 。 对于标准拍卖类型，各国学者已进行了相当深入的研究，这已经成为微观经 济学领域的一个重要组成部分，参考文献f 2 】【5 】中对于拍卖基本理论进行了较为 详细的分析与说明。随着拍卖理论和实践、以及计算机技术和电子商务的发展， 拍卖的应用领域更加广泛，如网上拍卖【7 】等。由于像拍卖金融有价证券、能源产 组合拍卖的非合作博弈分析 品、频谱以及计算机网络中的宽带等多物品拍卖的应用越来越重要，上述标准拍 卖类型已经不能适应拍卖环境的变化，于是经济学家们开始着手研究多物品拍卖 问题。 1 2 2 多物品拍卖理论 对于拍卖理论，具体拍卖方式研究往往早于理论研究。多物品拍卖理论也是 由拍卖方式的研究开始的。经济学家们首先考虑的是标准拍卖机制是否可以被应 用到拍卖多物品的情况，而这主要取决于各种物品之间的关系。一般来说，各种 物品之间的关系大致可以分为两类情况：第一类，所有拍卖品完全相同，而买方 可能最多需要一件这样的商品，或者需要购买多件。在买方购买多件物品时，他 的边际支付意愿可能会随物品数量的上升而下降；第二类，这些拍卖品不完全 样，但拍卖品之间有一定的联系。买方对这些物品的支付意愿因物品的组合而不 同。在设计拍卖机制时，被拍卖物品间的互补性或替代性常常是应该值得考虑的 重要因素i j j 。 对于像金融有价证券、能源产品和环境许可证这种相同物品的拍卖，在拍卖 中，投标一般需要指定可分商品的数量：股票的分配、电的瓦特数、或热能的盹 数。通常这些有关商品是或者将是在同一时间上的拍卖。当每一个买主 只需购买一件物品时，上述基本拍卖机制可以被推广到多物品拍卖，常见的两种 同时拍卖( s i m u l t a n e o u sa u c t i o n s ) 方式是歧视性( d i s c r i m i n a t o r y ) 拍卖和单一价 格( u n i f o r mp r i c e ) 拍卖【3 1 。歧视性拍卖方式是第一价格拍卖的推广，在拍卖中， 投标人同时并独立提交价格和需求数量。每个投标人在各自的价格上赢得他想要 的数量，并且支付他们赢得的每个物品价格的总和1 8 】。换句话说，如果两个投标 人赢得同样物品组合，但对物品所支付的价格可能不同。而单一价格拍卖是 v i c k r e y 第二价格拍卖的推广，即每个投标人同时并独立的提交价格和需求数量， 出价高的投标人获胜，而他们对每一个物品支付相同的价格，该价格是没有获胜 的那些投标中最高的投标价( 未中标者的最高报价) 。另外，当物品不是处于问 一时间被拍卖时，常用的是序贯拍卖的方法。序贯拍卖s e q u e n t i a la u c t i o n ) 是 指把k 件物品通过第一价格或第二价格机制一件一件地依次拍卖，并且每次拍卖 中，只公开最高的出价p 1 。 在拍卖多件不尽相同的物品，尤其是在这些物品问有互补关系的时候，一令 实用的设计是同时增价拍卖( s i m u l t a n e o u sa s c e n d i n ga u c t i o n ) 简称s a a j 。这种 拍卖方式也是英国拍卖的自然概括，尤其应用在出售多个有关物品的时候。s a a 组合拍卖的非台作博奔分析 拍卖中，物品在一系列循环中被同时拍卖。在每个循环中，每个投标人可以在任 何物品上提交投标，规定用最小投标增量来提高投标。直到没有投标人愿意在任 何项目上投更高的标时拍卖结束【1 0 】。s a a 方式最初是专门为通讯执照而设计的 i i i 该机制最大的优势在于通过竞争将许可证分配给最有能力运用稀缺的频谱资 源的电信运营商，并且能够带来较高的财政收入以减少扭曲性的税收。 如果物品间有比较强豹互补性，买方倾向于对一个或多个项目的组合提交投 标，即“组合投标”的形式，相应的拍卖形式就是组合拍卖( c o m b i n a t o r i a la u c t i o n ) 。 组合拍卖是指投标人可以对所有物品的任何组合投标，并提出相应的价格，也可 以同时对几个组合投标提出相应的价格。给定所有投标组合及价格，拍卖人使用 计算机计算出收益最大化的结果，并将该结果公布于众1 5 】。组合拍卖最早曾被美 国航空部门和市政府用来拍卖飞机场的停机位i i2 。，而英国伦敦的运输部门也用组 合拍卖方式来分配巴士营运的路线【1 3 1 【1 4 】1 1 5 1 。 适应性用户选择机制( a d a p t i v e u s e rs e l e c t i o nm e c h a n i s m ) ，简称a u s m ，是 在s a a 机制基础上建立起来的一种新机制。投标入可以在一段连续的时间之内出 价，随机确定拍卖持续的时间，以促使投标人保持活跃。投标人可以对多个商品 的组合提交投标。如果投标人提出了对一个物品组合的出价，它就可以替代前面 任何与其内容重叠的出价。任何时候的当前最高价是由一种最大化算法算出的一 个一致出价集中所提出的出价。试验证明这种拍卖机制在一些互补性很强的多物 品拍卖中表现很好1 1 l l 。该方式是f c c 正在研究的，对现行的s a 趟行改进的新的 打包竟价方式p l 。 文献 6 】中还介绍了一些新型的多物品拍卖机制，包括：随机n 价拍卖：a k l 3 a 和i b u n d l e 等拍卖方式。随机n 价拍卖指每个竞标者提交自己的投标，所有投标按 从高到低的顺序排列，拍卖者随机选择一个介于2 到k 之问的数字n ( k 为投标人的 数量) ，出价最高的前n 一1 个投标人以第n 高的价格得到物品。a k b a ( a s c e n d i n g kb u n d l e a u c t i o n ) 也是一种组合拍卖规则，允许买方对多个物品的组合投标。它 是一族拍卖规则的统称，最常见和研究最多的是a i b a 。这种拍卖是价格持续累 进的，投标人的投标必须高于他以前的出价和拍卖者宣布的高价。拍卖者宣布每 一个商品组合的竟价，并告知投标人他们所能得到的商品组合和得到其他组合所 需要提出的投标。拍卖者计算各种商品组合的均衡价格，通过这种方式决定买方 得到的商品组合和价格。该拍卖主要应用在现实的电子商务中，竞买者对市场上 的多个物品有互补的偏好，即异质产品( 不同的部件) 和互补偏好( 整个计算机 的配置) 分配问题。i b u n d l e 也是一种有效的增价组合拍卖方式。它和a k b a 都属 组台拍卖的非合作博弈分析 于在最后支付价格确定机制方面有所创新的拍卖机制。二者在概念上相似，但 i b u n d l e 具有价格歧视规则，而且在价格更新机制方面与a k b a 不同。事实上， i b u n d l e 是一种拍卖机制族，其中包括i b u n d l e ( 2 ) 使用的是匿名非线性价格； i b u n d l e ( 3 ) 使用非线性歧视性价格：r f i i b u n d l e ( d ) 在投标人对才i 连续的物品组合投 标时转为歧视性价格。i b u n d l e 中的投标人可以对物品组合提出“异或”出价( 只 要a 组合或只要b 组合) ，投标人的出价必须大于或等于拍卖者提出的要价加上最 低增价幅度。拍卖人在每一轮都计算商品组合的利润最大化分配方案，但必须尊 重投标人的“异或”出价。 最早研究多物品最优拍卖机制问题的是t h o m a sp a l f r e y ，在假定投标人对物 品的总价值是他对每件物品的私人价值的总和。当只有两个投标人时，拍卖人的 期望收益在捆绑方式下要比在分开拍卖下高。但当投标人数较多时，拍卖人更喜 欢分开拍卖| 5 l 。在多物品最佳拍卖中，如果投标人对于每一个产品的评价有二元 分布，则最佳拍卖的形式可能依赖于投标人的数量1 1 6 1 。 总体来说，对于最佳多单位拍卖的研究，一般论文明确认为多物品通常具有 下述三个之一：( i ) 标的是理想的替代品时导出收入最大化拍卖，( i i ) 分析执行 多少物品的有效分配，或( i i i ) 在预期收入和经济福利条件中比较特殊的拍卖形 式。然而，很少围绕有不同种类标的的收入最大化来推导拍卖设计。对有效多标 的拍卖，在某些机制中拍卖人的行为与收入最大化无关。从理论观点来看它是在 独立私有价值关系中简单地达到( 强) 有效，即一个g r o v e s 机制，个投标人的 支付外在地反映他通过他的偏好宣布而对其他投标人施加影响。这在公共( 或关 联) 价值情况中更复杂1 1 6 1 。 对于收入最大化多目标拍卖，早期的文章认为拊卖人在( i ) 在独立的上升 投标拍卖中提供单个标的( i i ) 在单独上升投标拍卖中做出单独出售项目和绑定 标的两者之间的决定。就捆绑模型，投标人在标的捆绑上的值是他们个别值得总 和。在投标人的数量为两个的时候，拍卖人总是更喜欢将标的捆绑起来出售它们， 但在投标人数量变得很多时这些拍卖人则倾向于分开拍卖。这暗示采取什么样的 多产品拍卖形式应该首先估计投标人的数量。同时也说明“纯捆绑”拍卖绝不是 最佳的( 除了恰好两个投标人外) 峭j 。 另外，多产品最佳拍卖有时还涉及到投标人风险偏好、需求缩减和预算约束 的问题。一般的，风险厌恶的投标人比风险中立的投标人投标更少，在比较竞争 的投标中，真实投标甚至在风险厌恶时也是最优的【1 7 】。有实力的投标人为了更少 的支付，而有降低需求的动机。即该投标人通过减少需求量，有时会用更低的价 组合拍卖的非合作博弈分析 格打败实力较弱的投标人l ”】。尽管投标缩减在每个价格上是最优的，但得到的是 完全无效率的交易1 1 。”。在需求曲线是水平和向下倾斜时，独立私人价值和关联价 值、同一价格与支付投标价格的拍卖方式都是无效率的【1 8 】。当物品面对的是一组 有预算约束的投标人时，在简单的完全信息框架里，首先出售更有价值的物品总 是最优的。如果物品的价值方面差异很大，与s a a 相比，序贯拍卖会产生更多 的收入；如果物品间有较强的互补性，而价值方面的差异很小，则同时拍卖是优 良的，并且这时预算约束是内生的【1 9 j 。 1 2 3 组合拍卖理论 组合拍卖是多物品拍卖的一种方式，主要用于不同物品间有互补影响、并且 投标人被允许在捆绑或不同物品的组合上提交投标的拍卖中。组合拍卖增强了拍 卖的经济效率f 2 0 】。组合拍卖方式最早在1 9 8 2 年就被建议用于美国航空部门和市 政府拍卖飞机场的停机位，英国伦敦的运输部门也用组合竞投方式来分配巴士营 运的路线，以及货车运输公司对于运输合同的获得1 2 ”。 组合拍卖机制在理论上应该包括单一循环、第一价格密封竞标、 v i c k r e y c l a r k e g r o v e s ( v c g ) 机制、有均街和出清价格的拍卖，和重复的组合 拍卖。组合拍卖的设计问题也应该同时考虑预期问题、极限问题、以合理的速度 保持投标变动、避免和打破平局，以及控制复杂性1 2 2 1 。研究组合拍卖与研究基本 拍卖机制一样，必须要涉及到四个主要方面：竞标( 每个投标人必须在物品的组 合上完全表达他的投标) 、分配( 按照某一目标函数的最优化使拍卖的物品分配 给不同投标人) 、支付额( 每个获胜者为一组物品支付多少) 以及策略( 投标人 在确定的分配和支付瘦则上自由选择的投标策略) 【矧。与分配问题相关的一个问 题常被称为竞胜标( w i n n e rd e t e r m i n a t i o n ) 阅题，最佳分配是所有分配中最优的， 而竞胜标问题则是如何找到最佳分配。 组合拍卖总体来说是个计算上很复杂的一种拍卖形式。在多数情况下，组 合拍卖因为其复杂性雨不常被使用。对于组合拍卖的研究，研究者通常作如下努 力：忽略某些问题，让投标人去推测他们将来是否将赢得项目；对于物品增加一 个转售t 守场，希望可以帮助产生经济上可取的组合；在多轮并行拍卖中出售多个 项目，希望前一轮的反馈信息可以提供投标人在下一轮的竞标策略；通过规定一 个两个或多个拍卖人可以组队的机制，使他们的投标结合起来，希望他们能找到 摄佳投标途径1 2 3 1 。 目前研究组合拍卖的研究者普遍认为计算竟胜标问题是最重要，其算法也是 组合拍卖的非合作博弈分析 最复杂的。解决组合拍卖的竞胜标问题就是在支持最佳项目捆绑分配的组合拍卖 中找到单独项目的价格【2 4 】。对于该问题的基本算法有枚举法、动态规划、近似算 法和对可投标的组合加以限制等。许多研究者经过进一步探索。发展出了许多可 行且易操作的算法，比如各种搜索算法。一种搜索算法是研究竟胜标的近似概率， 该算法允许组合拍卖按比例增加项目的数量，投标由现实资本来最佳化竞胜标， 通过可能的搜索树中充分选择后代的产生、利用对快速子代产生的二次搜索、利 用速度上可承认且最佳化的探索、和搜索空间的预处理4 个途径来进行。而一 个随时竞胜标的搜索算法，则可以通过利用投标空间必然鲜于实际的事实，扩大 计算出的可行的组合拍卖的输入范围f 2 6 1 。更复杂的搜索算法，则包括结构上的降 低搜索树的长度的改进，更快的数据组织，和基于逐个节点搜寻的最优化，来确 定且解决计算的易处理旧。另一种具有实现方便、寻优效果好的嵌入优先适台启 发式规则的混沌搜索算法，该算法在实例计算结果中有效地解决竞胜标决定问题 【2 8 1 。如果通过构造搜索空间来改进深度优先( d e p t h f i r s t ) 搜索，通常避免考虑 包含冲突投标的分配，来缩减处理时间的方法能够保证最优，且在构造的数据检 验中能够很快的找到最佳分配并且在任何时候都能够很好的执行。整数规划也是 一个常用的方法【2 0 1 ，但当竞胜标问题是整数规划时，一般不可能找到线性定价结 构，这时可以构造使用灵敏度分析和线性规划中二元性来获得定价信息的种类 。但组合拍卖的整数规划模型经常得不到整数解，一种解决方法是放宽限制条 件( 线性规划松弛或拉哥朗日松弛) ，或者引入一个混合整数规划逼近问题，则 通过标准整数规划算法能有效处理非常一般的拍卖1 2 9 1 。最后一种方法是启发式 的、基于市场的逼近。利用虚拟代理扮演每个初始投标捆绑和按照固定战略对捆 绑中的每个商品提交投标来建立虚拟多轮拍卖。虽然在构造的数据检验中缺乏关 于最佳或循环时间的保证，但在多数情况下能很快地接近均衡解p 。 如果从电子商务中的组合拍卖机理出发，以第价格密封拍卖方式为背景， 则组合拍卖竟胜标确定问题为离散组合优化问题。通过引入智能算法的思想，在 遗传算法中采用单亲遗传算予和嵌入优先适合启发式规则，求解该模型的优先适 合启发式单亲遗传算法。计算实例表明，利用该算法求解竞胜标确定问题的最优 解，算法实现简单，计算效果良好，且不需要复杂的交叉和变异等操作f 3 。同样 在电子商务环境下，许多服务可以被动态搜索和使用，因而，可以通过利用前一 轮投标的评价来进行下一轮评价的方法来缩减计算的负担1 “。 如果考虑每个商品可能又是由多个单位组成，并且每个投标从每个商品中随 意指定想要单位数量的更一般问题。可以合并专用动态规划程序，使用分枝限界 组含拍卖的非合作博弈分析 算法【3 3 】【3 4 】。 在投标人提交投标时，投标人对于所有满足需要的商品有时可以选择不完全 指定投标，这也可以缩减买者列举所有可能可接受捆绑的负担【3 引。 在研究组合拍卖的激励相容性质时，v i c k r e y 组合拍卖在简单的实验室环境 中可以成功的被实施。虽然投标人在c k r e y 拍卖中多数时间并不遵循需求显示 的占优策略，但给定v i c h e v 组合拍卖的“复杂性”，则它的需求显示性能只比 一个可能的单一单位第二价格拍卖的预期略微差一些。v i c k r e y 组合拍卖明显比 当前公共物品拍卖机制的实验室检验执行得更好p 6 】。在通过研究某些近似解来替 换严格解机制的影响时，通过对组合拍卖建立一致性，说明在限制参与人的种类 时真实的策略是占优的i ”1 。但事实上组合拍卖可能很难找到最优和可能没有激励 相容机制或市场出清的单独项目价格困i 。 因特网虽然为组合拍卖提供极好的基础设施，但必须考虑一种新型欺诈的可 能，即，一个代理人试图从虚假名字( 虚名投标) 下提交几次投标获益。如果不 存在虚名投标，一般v i c k r e y 拍卖( g v a ) 满足个人理性，帕雷托有效和激励兼 容。另一方面，当虚名投标是可能的时候，对于组合拍卖协议来说，理论上不可 能同时满足这3 个性质，标准划分机制( l d s ) 协议，是g v a 的修正，利用保 留价格拍卖判断取决于物品打包还是分开出售。l d s 协议满足个人理性和激励 相容，但不保证达到帕雷托有效的社会剩余，但l d s 协议通常可以比捆绑销售 商品协议达到更多的社会剩余i s 9 l 。 当存在个人理性时，效用最大化的代理人会在团队行为上遇到合作的机会， 他们必须决定是否参与团队行为，这涉及到诸如初始承诺决定问题( i n i t i a l c o m m i t m e n t d e c i s i o n p r o b l e m ，i c d p ) 的问题【删。在这种勾结问题上，理论工作 一般是适当加以限制来避免勾结行为的发生。 1 ，3 研究方法及论文结构 虽然研究组合拍卖既复杂，又有一些固有难题，但在一些像电力拍卖、运输 合同这种互补性很强的物品拍卖上又有极其实用的价值。因此有必要继续研究。 本文采用的分析方法是博弈论中非合作博弈理论。“博弈论”是在8 0 年代开始逐 渐进入主流经济学。迄今为止，在微观经济学、产业组织理论和宏观经济学中， 都取得了重要成就。用博弈论来研究拍卖不是个新方法，但应用博弈论的思想研 究组合拍卖问题则是个新的思路。 组合拍卖的非合作博弈分析 博弈论，又称对策论，是研究决策主体的行为发生直接的相互作用时的决策 以及这种决策的均衡问题的理论。依据当事人是否达成一个有效协议，博弈论可 以分为合作博弈和非合作博弈。纳什、泽尔腾和海萨尼的贡献主要在于非合作博 弈方面，他们的研究表明只有合作博弈中的协议构成一种非合作博弈中的纳什均 衡时才是一种有效协议( 真正有约束力的协议) ，所以现在谈到博弈论，一般指 的都是非合作博弈。般来说博弈论有四种不同类型的博弈，与之相应有四个均 衡概念，即：完全信息静态博弈纳什均衡；完全信息动态博弈予博弈完 美纳什均衡：不完全信息静态博弈贝叶斯纳什均衡；不完全信息动态博弈论 完美贝叶斯纳什均衡【4 1 】。使用博弈论方法来分析经济学问题的优势在于，博 弈论侧重于经济活动中多个利益主体的行为所产生的相互作用和影响的分析，从 而使经济分析更能反映经济系统的本质。第二，博弈论能够突出了经济分析中理 性人的地位【4 2 1 。而拍卖问题则是研究理性的参与人在拍卖过程中的行为所产生的 相互作用和影响，因此，用博弈论的思想完全适合研究拍卖问题。 一个博弈模型需要确定和定义四个要素：( 1 ) 博弈的参与者。即在所定义的 博弈中究竟有哪几个具有独立决策、独立承担结果的个人或组织。并且，博弈的 规则确定以后，各参与方都是平等的，大家都必须严格按照规则办事。( 2 ) 各参 与方各自可选择的全部战略或行动的集合。即规定每个参与方在进行决策时( 同 时或先后，一次或多次) 可以选择的方法、做法或经济活动的水平、量值。( 3 ) 进行博弈的顺序。在现实的各种决策活动中，当存在多个独立决策方进行决策时， 有时候这些参与人必须同时作出选择，因为这样能保证公平合理，而很多时候各 参与方不止一次的决策选择，这就免不了有一个顺序问题。因此，规定一个博奔 就必须同时规定其中的顺序，不同的顺序必然是不同的博弈，即使其他方面相同。 ( 4 ) 参与人的支付。对应于各参与人的每一组可能的决策选择，博弈都有个 结果表示各参与人该战略组合下的所得和所失。由于所有参与人在这个结果中所 得都是最优的选择，这个战略的组合便构成了一个均衡【矧。而拍卖理论所研究的 也是四个问题：参与人、参与人策略、拍卖规则以及最终支付。 如上所述，拍卖环境符合博奔论研究的特点，所以拍卖一般可以使用不完全 信息静态博弈理论来分析。即在“个体行为理性”基础上的“非合作博弈”。所 谓“个体行为理性”是反映个体的行为始终都是以实现自身的最大利益为唯一目 标，除非为了实现自身利益的需要，否则不会考虑其他个体或社会的利益这样一一 种决策原则。而“非合作博弈”是指在各参与人之问不能存在任何有约束力的协 议，也就是说各参与人不能公然“串通”、“共谋”的博弈问题1 4 ”。 组合拍卖的非合作博弈分析 本文研究般组合拍卖模型，包括建立组合拍卖模型，投标人最优策略分析、 拍卖人分配算法及方式分析、组合拍卖最优机制分析、以及福利等。在对组合拍 卖模型进行理论上的分析之后，利用模拟数据分析模型的合理性与实用性。 文章分为四个部分，第一章引言，通过介绍和评论拍卖理论、多物品拍卖方 式以及组合拍卖理论，提出本文的研究目的。第二章通过三个组合拍卖市场作为 模型的实践背景，得出组合拍卖的特点，并且从拍卖模型的理论背景中说明一般 的拍卖模型需要研究的问题。在第三章中用不完全信息博弈理论来建立和分析组 合拍卖模型，分析组合拍卖模型包括投标人策略分析，分配算法及程序分析，和 最优组合拍卖机制分析。在第四章中首先分析研究组合拍卖在我国的现实意义， 然后具体分析组合拍卖在数据应用上的优势，即结合组合拍卖的特点，利用合理 的数据模拟，通过将组合拍卖与把物品分开拍卖的传统形式的比较，说明组合拍 卖在物品间有互补关系拍卖中的优越性。主要技术路线就是建立组合拍卖模型之 后，利用博弈论的思想来分析组合拍卖模趔，最后通过数据验证模型的可行性。 组合拍卖的非合作博弈分析 2 组合拍卖的实践来源及基本要素 研究拍卖理论离不开具体拍卖实践，而常常是理论研究滞后于对于具体拍卖 方法的实践研究，有时会滞后很长时间。组合拍卖这种拍卖方式已经应用了很多 年，学术上公认的组合拍卖实践的几个典型是1 9 8 2 年美国航空部门和市政府拍 卖飞机场的停机位，英国伦敦的运输部门分配巴士营运的路线，以及货车运输公 司对于运输合同的获得。 2 1 组合拍卖模型实践背景 2 1 1 分配机场空位问题 1 9 6 8 年f a a ( f e d e r a la v i a t i o na d m i n i s t r a t i o n ) 采用了高密度规则分配4 个 主要飞机场( l ag u a r d i a ，w a s h i n g t o nn a t i o n a l ，k e n n e d yi n t e r n a t i o n a l ，o h a r e i n t e r n a t i o n a l ) 中稀缺的降落和起飞空位。该规则是对于这些飞机场中拥挤航线的 控制设立定额。通过这些定额调整，飞机场跑道空位有一个明确的特征，即，任 何建议的分配程序包含：航程起点机场上对于一条航线起飞空位的需求不独立于 它对于航程终点机场上降落空位的需求。当然，一个给定航程也可能在几个相互 依赖的相关需求中顺次起飞和降落。 空位由国民航空权威委员会( c a b ) 按照时间安排进行分配。每个机场的时 间安排委员会由每一个机场的代表组成，这些代表来自于被c a b 认定的可以飞入 这个机场的航线。委员会每半年开一次会，由空中运输协会的组织和协调。委员 会的人数是相对稳定的，而且在所有的委员会里的人总是相同的。 委员会分配机场容量方法蕴含着当前的政策关注。至u 1 9 8 5 年为止，有三十五 个机场将要面对严重的进入或容量问题。除了跑道、空间、环境的制约之外，装 载工具，运送行李工具，柜台空间等等，都会成为制约的瓶颈。行业发起者提倡 个全国性的解决合作分配问题的委员会程序。 相对于政策制定者的委员会程序的分析必须克服两个困难。首先，飞行和路 线的收益率的关键数据，不会因为被运送者而下降。其次，由于新的变化，过去 的方法的成绩不能够简单的被用来推断将来的数据。违反规定的先进入者被有效 地阻挡。因此委员会需要做的仅仅是协调一些大量的运输工具，在相对稳定的份 组合拍卖的非合作博弈分析 额下。无论如何，委员会都需要处理违反规定的，想要改变份额的新进入者。 在进行了大量的数据研究之后，委员会研究决定用和行程安排委员会同样的 程序来做决定。真实的财政方面的动机被用来诱导需求函数，需求函数和被认为 用来刻画空位的需求函数有着同样性质“。 之前，g r e t h e r ，i s a a c 和p l o t t 在1 9 7 9 和1 9 8 1 年对于发展机场空位分配提供 了一个市场程序。该程序的基础是增加竞争的( 相同价格) 密封拍卖和口头双边 拍卖。在他们的建议下，对于每个机场空位上，一个独立的初级市场将在合适区 间上被组织成像密封投标竞争性拍卖一样。在初级市场分配以后，不准备提供相 互依赖的空位需求，口头双边拍卖的计算操作形式如同建议一个“后市场”来允 许自由购买航线和相互出售初级市场的空位，该连续“后市场”交易将通过单独 航线愿意获得的那些空位捆绑支持他们的时刻表。因而，在不做航程配合空位的 w a s h i n 西o nn a t i o n a l 上获得空位的航线可以通过在o h a r e 可以购买额外的 o h a r e 空位或在后市场中出售他超额的w a s h i n g t o n 空位两者之一来处理。虽然 该建议中的后市场允许航线自由交易空位，并且由此得到专有空位捆绑，但它有 两个缺陷。 ( 1 ) 单独航线在后市场的机场空位交易过程中可能受到资本的损失与增加。 因而，有a 个超额空位和b 个稀缺空位的航线可能在给b 个空位定价是非常徒 劳的，而额外的a 个空位只能在损失中被出售。 ( 2 ) 成本策略