（计算机软件与理论专业论文）网络经济若干拍卖机制的研究.pdf

摘要 近几年，电子商务正在迅猛发展。尤其是网络拍卖，大量理论上和实践 上的研究围绕着它展开。本文分别对网络时代的三种拍卖模型分别进行了 研究。 我们首先研究了一种拍卖数字产品的模型。在该模型中，每个竞拍者 将向拍卖商提交他的最大愿意支付单价，竞拍数量以及最大预算。现在的 在线广告位置拍卖，软件许可证等拍卖都可以抽象到这个模型。我们为该 模型设计了一种对拍卖商有利的机制。这种机制的主要特性就是每个竞拍 者为了追求自身利益最大化而撒谎的话，不仅不会减少拍卖商的收入，而且 还有可能增加拍卖商的收入。然后，我们在拍卖商供货量有限和无限的情 况下，都给出了具有4 ( 1 一口) 的竞争比的对拍卖商有利的拍卖机制，其中 q 表示了在最优单个定价拍卖中，所有的赢家中间，单个竞拍者的最大需求 量与总的赢家的需求量之间的最大的比值。 然后，我们对被g o o g l e ，、r a h o o ! 等搜索引擎商所使用的在线广告拍卖模 型进行了研究。我们将整个拍卖过程看作是一个动态的不完全信息的非合 作博弈，其中每个竞拍者不仅会考虑它的策略给他当前所带来的影响，而且 还会考虑该策略对于其他竟拍者未来决策的影响。基于上述的观察，我们 提出了比纳什均衡更适用于广告位置拍卖的有远见的纳什均衡。该均衡解 有着良好的性质，它既是输出诚实的，而且它的定价与v c g 拍卖机制下的 定价是一致的。更为重要的是，我们证明了该模型将最终收敛于该均衡解 中。我们分别研究了几种合理的动态调整模式。我们证明了其中的随机的 调整模式将以概率l 收敛于有远见的纳什均衡。 最后，我们还就e b a y 拍卖中几个拍卖会在同时拍卖同一种商品的现象 中文摘要 i v 进行的分析。我们研究了在这样分化市场下买家的策略行为。我们证明了 在这个一种环境下，存在着贝叶斯一纳什均衡。此外，我们还分析比较了分 化市场下的希望的总收入与单个市场下的总收入。结果表明了分化市场下 的总收入在绝大多数情况下会低于单个市场下的总收入。 关键词：网络经济，竞争性拍卖，广告位置拍卖，e b a y 在线拍卖，博弈论， 机制设计 中图分类号：t p 3 0 9 a b s tr a c t l nr e c e n ty e a r s ，g r e a tp r o g r e s s e sh a 、r eb e e nm a d ei ne l e c t r o n i cc o m m e r c e e s p e c i a l l yi ni n t e r n e ta u c t i o n s ，t ow h i c hv a r i o u st h e o r e t i c a la n dd r a c t i c 越 s t u d i e sh a 、r eb e e nc o n d u c t e d i nt h e 矗r s tp a r t ，、ei n v e s t i g a t ean e wa u c t i o nm o d e li nw h i c hb i d d e r s h a eb o t hc o p ya n db u d g e tc o n s t r a i n t s t h en e wm o d e lh a se x t e n s i v ea n d i n t e r e s t i n ga p p l i c a t i o n si na u e t i o no fo n l i n ea d w r o r d s ，s o f t 协r el i c e n s e s e t c w bc o n s i d e rt h e f b u o w i i 培p r o b l e m ：s u p p o s e 出lt h ep a r t i c i p a t o 】瞎a r er a t i o n a l ， h o wt oa 1 1 0 c a t et h eo b j e c t sa n da tw h a tp r i c es oa st om a x i m i z ea u c t i o n e e r s r e v e n u e v i n t r o d u c ean e wk i n do fm e c h a n i s m sc a l l e d 口就c 统d n e e 7 - n ( 幻。佗n 口甜 r n e c 九a n i s 7 n sa n dp r e s e n tt h en o t i o no f 仳竹c d n d i 统d 礼n fc d m p e 挽亡z t ，eo u c 挽d n s a n o t a b l yi n t e r e s t i n gp r o p e r t yo fo u c 跣d 佗e e 7 、n d 口口佗口夕e d7 n e c n 扎t s 仇si st h a t e a c hb i d d e r ss e l f - i n t e r e s t e ds t r a t e 酊b r i n g sb e t t e ru t i l i t yn o to n i yt oh i m s e i f b u ta l s ot ot h ea u c t i o n e e r t h e nw ep r e s e n to u c 统o n e e ，- n d u 口n o 口e dm e c o 扎i s 仃措f b rm u l t i u n i ta u c t i o n sw i t hc o p ya n db u d g e tc o n s t r a i n t s w bp r c i v e t h a tt h e s ea u c t i o i l sa r eu n c d 礼班i d n o zc d 竹印e 蹴锄eu n d e rt h e s i t u a t i o no fb o t h l i m i t e da n du n l i m i t e ds u p p l y i nt h es e c o n dp a r t ，r es t u d yt h ea d w o r da u c t i o n ，u s e db yg o o g l ef b r i n t e r n e ta d v e r t i s e m e n t w ba r ei n t e r e s t e di i lt h ed y n a m i c p r o c e s sh o wb i d d e r si n t e r a c tt or e a c ha ne q u i l i b r i u m w bc o n s i d e rs u c ha na u c t i o np r o c e s sa s ad y n a m i ci n c o m p l e t ei n f o r m a t i o nn o n c o o p e r a t i v eg a m e ，w h e r e e v e r yp l 妁r e r w i l lt a k ei n t oa u c c o u n tb o t hh e rc u r r e n 乞b e h a v i o ra n d i t se 船c to nt h eo t h e r v 英文摘要 v i p l a y e r s f u t u r eb e h a v i o r 缸t h ep r o c e s so fo n 一1 i n ea d v e r t i s e m e n ti sf u l l yc o m - p u t e rc o n t r o l l e d ，t h eo u t c o m eo fe a u c hd i s p l a y m e n to p p o r t u n i t yc a nb et o t a l l y d i h e r e i l t i tc a i li n d e e d ( 龇1 do f t e ns o ) b ei m p l e m e i l t e da ss u c had y i l a i n i c n o n c o o p e r a t i v eg a m e b a s e do nt h i so b s e r v 扎i o n ，w ep r o p o s eb i d d e r s s t r a t e g y ，如r 叫n 硝一f d d 兢7 汐 6 e s 他印o n s e 九几c 仍礼，a i l dr e l e v a n te q u i l i b r i a ，a ss u i t a b l es o l u t i o nc o n c e p 乞s t h ec o n c e p tt a k e si n t oc o n s i d e r a t i o ni m p o r t a n tf a c t o r si nb u y e r s s t r a t e g i c b e h a v i o ri nt h ed y n a m i cp r o c e s so fa d w d r d sa u c 乞i o n s w bp r o v et h es o l u s i o n i sd 让印钍t r m 副0 也fa n di t sp r i c i n ga n da l l o c a t i o ns c h e m ei se q u i v a l e n tt ot h e v c ga u c t i o no u t c o m e m o s ti m p o r t a n t l y ，w a n a l y z et h ec o n v e r g e n c ep r o p e r t yo ft h i ss o l u t i o n c o n c e p t w bs t u d ys e v e r 出d y n 锄i ca d j u s t m e n ts c h e m e s w bp r o v et h a ta r a n d o m i z e da d j u s t m e n ts c h e m ew 珊c o n v e r g et o 如删口r 出幻d 觑凹 e g 让乒 跣6 疵ow i t hp r o b a b i l i t yo n e o nt h eo t h e rh a n d ，、) l ，es h o wt h a to s c i l l a t i o nm a y e m e r g ei nb o t hs i m u l t a n e o u sa d j u s t m e n ts c h e m ea n ds e q u e n c ea d j u s t m e n t s c h e m e i nt h et h i r dp a r t ，es t u d yt h ee b a yo n l i n ea u c t i o ns y s t e m ，w h i c hi st h e 、7 l r o r l d sl a r g e s to n l i n em a r k e t p l a c ef o rb u s i n e s s e sa n dc o n s u m e r st oa u c t i o n 0 8g o o d st h r o u g hi t i nt h i so n l i n ea u c t i o ns y s t e m ，t h es e l l e rp u t so nt h e i t e ma n dr e l e v a 呲i n f o r m a t i o n ，a n dt h eb u y e r sb u yt h ei t e mb ys u b m i t t i n g t h e i rb i d s w bo b s e r v et h e r ea r e 印胁m o 他e 幻i ne b a y so n l i n ea u c t i o ns y s t e m i no t h e r r o r d s 。t h e r ee x i s ts e v e r a la u c t i o n st h a ts e l lt h es a m ei t e m s i m u l t a n e o u s l yi nm o s tc a s e s w bs t u d yt h eb u y e r s s t r a t e g i cb e h a v i o ri n s u c hs p l i tm a r k e t w 宅s h o wt h a tt h es p l i tm a r k e th a sab o 秒e s i o 佗- 口娩e q u i l i b r i u m f i u r t h e r ，w ea n a l y z et h ee x p e c t e dt o t a lr e v e n u ei nt h es p l i tm a r k e t i nc o m p a u r i s o nw i t has i n 舀em a r k e t k e yw o r d s ： i n t e r n e te c o n o m i c s ， e b a yo i l l i n ea u c t i o n s ，g a m et h e o r y ， c o m p e t i t i v ea u c t i o 璐，a d - w o r da u c t i o n s ， m e c h a n i s md e s i g i l 论文独创性声明 本论文是我个人在导师指导下进行的研究工作及取得的研究成果。论文中除 了特别加以标注和致谢的地方外，不包含其他人或其它机构已经发表或撰写过的 研究成果。其他同志对本研究的启发和所做的贡献均已在论文中作了明确的声明 并表示了谢意。 、 作者签名： 1 二壅塑 日期：竺z 查：! 兰作者签名：1 筌塑 日期：竺乙查：竺 i 论文使用授权声明 本人完全了解复旦大学有关保留、使用学位论文的规定，即：学校有权保留 送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部分内 容，可以采用影印、缩印或其它复制手段保存论文。保密的论文在解密后遵守此 规定。 作者签名： 匕茎型导师签名 l 一 n 曰期：竺2 ：查：! ! 第一章 ji 古 亏l 苗 1 1网络经济背景 i n t e r n e t 是人类亲手创造的世界，通过将现实生活中的各种活动引 入到i n t e r n e t 中，人们正在从各方面丰富并完善着这个世界。而广告和e - m a r k e t 正是i n t e r n e t 世界中两个重要组成部分。i n t e r n e t 中的广告业务不仅 极大地丰富了整个广告市场，而且还正在慢慢吞噬着现实中的广告市场的 份额，逐步成为广告市场的主流，这当然与人们日益频繁的网上活动有关。 而e - m a r k e t 的规模更是日益壮大。各种b 2 b 和b 2 c 平台的建立和完善，使得 愈来愈多的商家与商家，商家与消费者的各种交易都在i n t e r n e t 中完成。 在这上述这两种i n e r n e t 的成功应用中，拍卖一一这个有着悠久的历史， 但同时也一直远离于普通百姓日常生活的经济机制直扮演着一个非 常重要的角色。正是由于i n t e r n e t 的出现以及日益普及，拍卖这个以往只有 政府，企业，富翁等参与的经济活动慢慢地渗透到了普通百姓的生活中，并 发生着一系列重大的变动。 在网络信息时代，可以销售的产品除了以往由分子构成的物理实体以 外，还包括信息时代所独有的，由0 和1 组成的数字产品，例如网上通过收费 可以下载的多媒体文件( m p 3 ，电影) 以及各种应用软件，如w i n z i p 等等。 区别于物理产品，这些数字产品可以拥有无数多份拷贝，而且生产多份拷贝 不会给经销商带来更多的花费。 1 2 本文的工作及贡献 2 此外，在网络信息时代，拍卖已经成为了许多大型新型企业的主要盈利 手段。例如，超过9 8 的g o o g l e 的收入以及超过5 0 的、r a h o o ! 的收入都 来自于广告关键词拍卖【1 0 1 。这些收入的总额将近几十亿美金。 除了有许多大型的企业以拍卖作为主要盈利手段外，更有无数的个体 将网上拍卖作为他们的主业或者是副业。由于在网上进行销售，整个销售成 本大大降低。而且整个拍卖过程都是由系统自动完成，卖家只需要在拍卖 前和拍卖后适当介入即可，因此卖家投入在上面的精力也可以降到最低。 而在传统的拍卖中，政府部门往往扮演着拍卖商的角色，主要是拍卖各 种自然资源，例如土地，能源，频率等等。因此采用的拍卖机制更主要的是 考虑到这个社会的利益，而不是拍卖商自身的利益。 正是由于上述的种种不同，对于i n t e m e t 中现有的各种拍卖活动，我们 有必要进行重新审视，分析和设计。 1 2 本文的工作及贡献 我们首先就数字产品的拍卖模型进行了设计和分析。正如前面所说的， 数字产品的主要特点是容易批量生产，数量甚至可以无限而不需要增加任 何成本。我们考虑了一个通用的模型，其中每个竟拍者要向拍卖商提交他 对单个拷贝所愿意支付的最大价格，他最大愿意购买的拷贝数量以及他所 能够支付的最大数目。这种模型有着广泛的应用。例如在现有的广告位置 拍卖中，每个广告商就需要向系统提交他在一定的时间段内，比如说1 个月 内，对每一次点击所愿意支付的最大价格以及他在这一个月之内所能够支 付的最大金额等。 从拍卖商的角度出发，在每个竟拍者都是理性且自私的合理假设下，我 们希望能够通过某种分配和定价手段以最大化拍卖商的利益。因此，我们 引入了一种对拍卖商有利的机制。这种机制的主要特性就是每个竞拍者为 了追求自身利益最大化而撒谎的话，不仅不会减少拍卖商的收入，而且还有 可能增加拍卖商的收入。 我们首先就供货量无限并且竞拍者没有预算限制的情况下，设计出了 具有4 ( 1 一q ) 的竞争比的对拍卖商有利的拍卖机制，其中n 表示了在最优 1 2 本文的工作及贡献 3 单个定价拍卖中，所有的赢家中间，单个竞拍者的最大需求量与总的赢家 的需求量之间的最大的比值。而供货量无限其实是供货量有限的一个特例。 因此，我们又将模型推广到供货量有限而且竟拍者有预算限制的情况。在 这种情况之下，我们给出了同样的竞争比。 对于现在引起各方关注的广告位置拍卖，我们则研究了这个拍卖的动 态过程一一即竞拍者最终是如何到达均衡的。在在线广告位置拍卖中，广 告商通过竞价来获得在搜索结果页中所显示的相关广告链接的排名。竞价 越高的广告商将获得较显眼的广告位置，例如显示位置靠前等，因此他更能 获得较高的点击率。而他将为每一次点击向搜索引擎商支付在他下面那个 位置的广告商的竞价。对于这样一个现有的拍卖机制，我们已经知道它并 不是诚实的，同时我们也知道在这样一种机制下，纳什均衡是肯定存在的 1 0 ，3 0 ，3 1 。但既然每个竞拍者并不一定会诚实地提交他的真实竞价，那么 这么纳什均衡是否能够最终到达就成了一个重要的问题。 我们发现纳什均衡在广告位置拍卖之下其实并不是稳定的。考虑到每 个竟拍者的竞拍不仅影响他自身的当前盈利，还会影响其他竞拍者未来的 竞拍策略，我们提出了一种新的均衡解的概念，叫做有远见的纳什均衡。 我们证明了有远见的纳什均衡在位置拍卖中将只有唯一一个解。相对于在 纳什均衡中，真实估价高的竞拍者有可能拿到点击率低的广告位，在有远 见的纳什均衡中，它保证了输出诚实的性质一一即真实估价高的竞拍者将 拿到点击率高的广告位。我们证明了有远见的分配和定价模式其实是等价 于v c g 机制的，而v c g 机制正是由于它过于复杂的定价机制才没有被采用 到现有的广告拍卖中。我们的结果则表明了现在所使用的这样一种拍卖机 制其实是合理的。 更重要的是，我们分析了这个均衡解的收敛性。我们提出了几种合理 而且公平的动态调整模式。我们证明了随机调整模式将以概率1 收敛到有远 见的纳什均衡，而另外的并发的调整模式和循环的调整模式则不一定总能 够收敛到纳什均衡。而随机的调整模式能够更好的反映现实的模型，因此 我们可以在实际的广告位置拍卖中，动态系统将会最终收敛到有远见的纳 什均衡。 1 2 本文的工作及贡献 4 此外，我们还就e b a y 在线拍卖中的分化市场现象进行了研究和分 析。e b a y 是现在世界上最大的b 2 c 交易平台，而它所采用的交易模式正是拍 卖机制。在该在线拍卖系统中，每个卖家将要拍卖的物品及相关信息放在 网上，而买家则通过向系统提交竞拍价进行购买。我们发现在在线拍卖中， 经常会发生几个拍卖会在同时拍卖同一种商品的现象。我们研究了在这样 一种环境下买家的策略行为。我们证明了在这样一个分化拍卖市场之下存 在的贝叶斯一纳什均衡。在该贝叶斯纳什均衡之下，如果每个竞拍者的真实 竟拍价低于某个阈值，则他会同时参加这两个拍卖会。反之，如果他的真实 的竟拍价高于这个闽值，则他将随机的参与其中的某个拍卖。此外，我们还 分析比较了分化市场下的希望的总收入与单个市场下的总收入。结果表明 了分化市场下的总收入在绝大多数情况下会低于单个市场下的总收入。 第二章 基本概念及其相关定义 2 1博弈论模型及其均衡解的概念 在这一部分，我们将就本文中所提及的一些基本概念进行必要的介绍。 读者如果需要进一步地了解这些概念的提出背景以及具体应用，可以参考 【1 2 ，2 3 ，1 9 ，1 6 】。 定义2 1 1 完全信息博弈( g a m ew i t hc o m p l e t ei n f o r m a t i o n ) 一个完全信息 搏弈模型g 包含了r ： i 参加该博弈的全体人的集合n ； 2 每一个参与者t n 有一组非空的行为( a m o n ) 集合a ； 3 每一个参与者i 有一个效用函数心绷t 冶知n c 统d 矽讹：j a r o 注释2 1 2 模型中的“效用”( 碱跳譬) 在许多具体的环境中常被“盈利”( p 蚴 o 嚣) 所替代。因此，在本文中，这两个词所指是同一个意思。 所谓一个博弈的均衡解，就是给定每个参与者的个人喜好，理性程度， 获得信息量的多少等情况下，在假设每个参与者都是利己主义者( 即最大化 效用值) 的前提下，该博弈所最终能够达到的稳定状态。其中最有名的一类 解就是所谓的纳什均衡。 5 2 1 博弈论模型及其均衡解的概念 6 定义2 1 3 纳什均衡( n a s he q u i l i b r i u m ) 一个完全焦息搏弈模型下的纳什 均衡是一组行为矢量a j ，该矢量满足对于任意t 和啦a ： u t ( a ) u i ( q i ，a 二t ) 其中o i 是参与者 的行为，而a = - 。是表示其它参与者的行为，即a 二；= 【n 1 ，o i l ，啦+ l ，n 竹) 。 注释2 1 4 因此，在纳什均衡解下，在其他参与者都保持不变的特况下，每 个人都对自己当前的行为最满意。因为该行为最大化了他的效用值。尽管 纳竹均衡是一个应用十分广泛的均衡，但纳什均筏仅仅强调了什么样的状 态是一个稳定的状态。却没有提及每个参与者从一个任意的初始状态是否 会最终达到一个纳什均筏甚至如果这个博弈含有多个纳什均衡。其次纳 什均衡是假设每个参s 者都完全知道其它的参s 者的行为。但很显然，在 很多实际的情况t 包括在各种拍卖模型中每个参s 者并不能够获得其他 人的行为信息。 正如上面所说，很多情况下，每个参与者并不能获得其他人的相关信 息，因此每个人只能够根据其它人的部分信息计算出来的期望的效用值来 选择自己的行为，从而产生了与之相关的非完全信息博弈模型。 定义2 1 5 非完全信息博弈( g a m ew i t hi n c o m p l e t ei n f o r m a t i o n ) 一个非完 全焦息薄弈模型r 包含7 ： 1 参加该博弈的全体入的集合n ； 2 每一个参与者t n 有一组j # 空的行为集合a ； 3 每一个参s 者t n 有一组类型( t 譬p e ) 集合砥来刻画参s 入的相关 特征； 4 基于j 的一个概率分布函数f ； 5 每一个参与者 有一个效用函数u t ：j 心疋_ 肽。 2 1 。博弈论模型及其均衡解的概念 7 注释2 1 6 f f ) 在任何一个给定的搏弈中，x j 码是按照分布，随祝采 样的；( 2 ) 在很多情况下我们都可以把这个抽象的类型集合看成是参s 者 的真实偏好一一如对物品的真实估价等等一一只有他本人知道，而其他人 都不知道的信息。在本文中我们将会多次提到这个概念。 定义2 1 7 策略( s t r a t e 盯) 对于参与者i ，他的策略是一个从他的类型集 合映射到行为集合的函数即& t ：k _ a 。 定义2 1 8 支配策略均衡( d o m i n a n ts t r a t e g y ) 如果对于任意的x j 码， 以及其他入的任意策略q 一。 u t ( q i ( z i ) ，q t ，z t ) 让t ( q ：( z i ) ，0 【一i ，z i ) 则该策略q t 是参与者t 的支配策略。 如果每个参s 者t 都有个支配策略畦则岔就组成7 一个支配策略 均筏。 注释2 1 9 换句话说，不管别人采用什么样的策略，参与者i 采用支配策略 畦肯定会最大化他的效用。因此如果一个博弈存在着支配策略均衡，我们 一般可以非常合理的假设所以得参s 者都会采甩他的支配策略。因为即使 对某个参与者t 可能还存在其他的某个策略必基于其他入的当前策略能够 最大化他的效用既然采用支配策略能够达到同样的效用而且比文更加 保险因为支配策略是无条件最优的4 这样支配策略均衡可以很好的解决 前愿斩提及的纳什均筏的弱点。但由于这个解的概念太强并不是任何博 奔都存在着这样的解的。 接下来的贝叶斯一纳什均衡是纳什均衡在非完全信息博弈模型下的推 广。 定义2 1 1 0 贝叶斯一纳什均衡( b a y e s n a s he q u i l i b r i u m ) 在非完全焦息博弈 模型下，一个贝叶颧纳什均衡是一个矢量口满足：对于任意t z i 砥以 及q ： e 【u t ( q ；( z 1 ) ，q 二i ( x i ) ) i x t = z 】e 【“t ( 乜：( z ) ，a 二t ( x 1 ) ) l x f = z f j 其中x 是满足分布 的随机变量。 2 2 机制设计 8 注释2 1 1 1 贝叶斯一纳什均衡和纳什均衡的一个主要区别是在贝竹斯纳什 均筏中每个参与者的策略是基于其他参s 者具体行为的某个分布的而不 是仅仅对于其他参s 者的某个具体的行为。换句话说对s 其他参s 者赋 予具体类型下的具体行为，参s 者t 的策略畦并不一定是最优的o 2 2机制设计 前面的部分主要是讨论给定一个博弈模型下，最终所能够达到的各种 均衡状态及其性质。而机制设计则是一个逆向的过程，它是在求设计出某 个博弈模型，使得在该博弈博弈模型下，能够得到我们所需要的均衡解。 定义2 2 1 机制设计( m e c h a n i s md e s i g n ) 一个机制m ( 0 ， p l ，r ) ) 包 括以下几个组成部分： 1 有孔个参s 者； 2 每个参与者t 的类型集合疋等于他的行为集合a ； 3 每个参与者t 有一个真正的类型t t xr 有他本人知道； 彳每个参与者t 可以执行任何一个策略a t ：咒_ a ； 5 该机制有一个公开的分配函数阻z f d c 口勘扎知n c 踟砂o = o ( o l ，o n ) 从类型集合到s 具体问题相关的结果集合的一个映射。 疗该机制同肘对于每一个参与者z 还有一个支付函数俨口3 m e 死血礼c 踟叫仇= 只( 0 1 ，a n ) ，所有的支付函数都是公开的； z 对于每一个参与者z ，他的效用函数定义为u t ( “o ) = 砒( 彘，o ) 一 只( a ，o n ) ，其中仇( 如，o ) 表示在该分配下给参与者i 所带来的价 值。因此这个效用函数可以看作是该分配结果给参s 者t 的“净价 值”。 定义2 2 2 诚实的机制( n u t h f u l i m p l e m e n t a t i o n ) 如果在这个祝制中，存 在者一个支配策略均衡，其中每个久的策略就是简单地报告他们厅9 j 内心的 类型的话，我们就说这个机制是诚实的。 2 3 拍卖9 而下面的定理则保证了如果某个机制存在支配策略均衡的话，则一定 存在着相应的诚实的机制： 性质2 2 3 揭露原理( r 电v e l a t i o np r i n c i p l e ) 如果一个祝制存在支配策略均 衡的话。则一定存在着相应的诚实的机制。 在众多的机制中，最有名，也应用最为广泛的就是下面的v c g 机制了。 定义2 2 4v c g 机制( v c gm e c h a n i s m ) p j ，邑! 彬在阳僦制中，其分配 函数以及支付函数必须满足： j o ( 亡) a r g m ( ：l 饥( 屯o ) ) ； 2 a ( t ) = j 和饥( o ( 亡) ，缸) + 玩( t t ) ，其中吃是关于t t 的任意函数。 定理2 2 5y e g 机制是诚实的。 注释2 2 6 我们一般有这样的假设：如果这个机制是诚实的话，那么每个 参s 者就会诚实地报告他们的真实类型。这是由于对于自身来说任何情 况z 下不撒谎永远可以保证是最好的策略之一。因此每个用户没有必要 再花费一定的代价另外再找一个最优策略。而且他还不一定能够知道其他 人的策略是什么。 但这并不意味着只有诚实的报告他的真实类型才是最好的策略。事实 i 即使在诚实的机制中也存在着大家都不诚实的纳什均衡。因此严格 的说，上述定义的诚实地机制其实是弱的诚实机制。在本文的第三章中，我 们也同样使用7 这样一个假设o 2 3 拍卖 拍卖其实就是一种机制设计。接下来我们先介绍一下非常简单的拍卖 模型，以及基于该模型的一种诚实机制的实现。 定义2 3 1 单回合秘密竞价拍卖( 0 n e r o u n d ，s e a l e d b i da u c t i o n ) 在卓回合 秘密投标拍卖模型中： 2 3 拍卖 1 0 1 每个竟拍者( b t a d e r ) i 有一个只有他本人才知道的值t t 表示这个竞拍 者内心对该拍卖物品所愿意支付的最大价格( 估价) 即在机制设计定 义中的类型； 2 每个竞拍者t 会将一个竞拍价( b 试) 写在信封里然后再提交给拍卖 商。因此每个入r 知道自a 的竞拍价。我们用矢量b 表示所有竞拍者 似u c “d 礼e e r j 的竟拍价，其中6 i 表示第t 个人的竞拍价； 3 在收到所有入的竟拍价之后拍卖商会用一个事先b 经公布的分配方 法o = o ( 6 ”6 竹) 和支付函数a = 只( 6 1 k ) 进行分配。对于任 意的毫。如果0 t = 1 则竞拍者i 获得该物品并且支付乳这时他 的净获利( p 叼。嚣) 是t l t p t ，我们称之为赢家；如果0 t = q ，则竞拍 者没有得到该物品这时他的净获剩是一p i 我们称之为失败者o ( 此 时。我们一般都要求仇都等于o 这样失败者的净获剩也不会是负数 否则他还不如不参加这个拍卖。这个可以鼓励每个入都来参加拍卖o ) 每个竞掐者之间都不会进行合谋( c o t 沁s t o 他) ； 5 ，每个竞拍者都是理性的，且追求自身的净获利最大化； 6 每个人的竞拍价都不相同。 在该单回合秘密竞价拍卖模型中，我们利用上一节所提到到v c g 机制 就可以设计出一个诚实的拍卖机制，使得每个竟拍者最终都会如实地递交 自己内心的真实的估价给拍卖商。 定义2 3 2 七c o p yv i c k r e y 拍卖机制( 肛c o p yv i c k r e ya u c t i o n ) p 假设在 单回合秘密投标拍卖模型中将拍卖k 个相同的物品，而且k 严格小于竟拍 人的人数礼。在该老c 印耽c 后他秒拍卖机制中，竞拍人会以第七+ 1 高厅队的 出价作为该物品的统一价格将这k 样物品卖给出价最高的前k 个人。 读者可以很容易的验证该机制是满足v c g 机制的。基于上面的定理， 我们马上就可以得到七一c o p yv i c k r e y 拍卖机制是诚实的。下面我们将给一个 更加直接的证明，给读者以比较直观的认识。 2 3 拍卖 1 1 定理2 3 3 惫c 叩耽c 概可拍卖祝制是诚实的。 证明：让p 表示所有的出价中第七+ 1 高的价格。对于某个竞拍者l ，如果 大于p ，则不管i 在p 之上如果修改他的竞拍价，他仍然以同样的价格获 得物品，因此净获利没有发生改变。如果他改变他的竟拍价以至于小于p ， 则净获利变成0 。显然对于竞拍者 来说，报他内心的估价就是他的支配策 略。 对于某个竞拍者 ，如果啦小于或者等于于p ，则不管t 怎样降低他的 出价，他仍然没有得到物品，因此净获利仍旧是0 。如果他提高他的出价以 至于得到了该物品，很显然，他所需要支付的价格必然要大于p ，而他本人 内心的估价小于或者等于于p ，则他的净获利变成了负数。因此，对于这 些竞拍者来说，报他们内心的估价仍旧是他的支配策略。 一 注释2 3 4 耽c 七r e y 拍卖之所以特别著名，就是因为它是一个诚实的拍卖祝 制。在耽c 后r e 可拍卖中，对于每个竞拍者来说，他根本不必考虑其他人的叫 价。因为不管别人怎么竟价他报他自a 真实的估价永远是最好的策略之 一。所以在单回合秘密投标v t 汰r e g 拍卖中每个竞拍者都能够直接诚实的 报告自a 内心的估价而不必考虑其他人的报价。 第三章 有需求量及预算要求的竞争性拍卖 3 1 介绍 在这一章，我们将研究一类通用而且实际的拍卖模型。在该模型中，一 个拍卖商对一种数字产品进行拍卖，且该数字产品具有多份的拷贝。在拍 卖过程中，每个竞拍者需要向拍卖商提交( 1 ) 他对该物品的估价一一即他 对单件物品所愿意支付的最大价格，( 2 ) 他对该数字产品的需求量，( 3 ) 他 最大的支付能力一一即他的经济预算。我们将从拍卖商的角度出发，在该 拍卖模型下，设计出某种机制，使得拍卖商的收入从理论上能够得到保障。 也就是说，在假设每个竞拍者都是理性且自私的前提下，尽可能地最大化拍 卖商的收入。 和以前传统等拍卖模型相比，该模型考虑了在数字经济时代所特有的 特征，更加符合现代生活的实际应用： 1 我们的模型主要是适用于对于数字产品的拍卖。数字产品主要具有容 易复制的，且边际成本( m a r g i n a lc o s t ) 基本为0 的特点。例如，软件许 可证的销售，网上m p 3 歌曲的下载，在线广告等等。 2 我们考虑了每个竞拍者对于拷贝数量的需求以及经济能力的限制。很 显然，在现实生活中，每个买家的需求以及经济能力总是有限的。冗 余的分配不仅不能够给买家和卖家带来经济利益，而且会产生严重的 1 2 3 1 介绍 1 3 资源浪费。一个只拥有1 0 0 台电脑的公司购买1 0 0 0 份软件许可证毫无 疑问是不合理的。 此外， 我们设计了一类叫作拍卖商有利的机制( a u c t i o n e e r - a d v a d l t a g e dm e c h _ a n i s m ) 。在一般的双边市场中，有名的v c g 机制在最大化买家利益的 同时，却最小化卖家的利益。这是v c g 机制本身的利他函数( u t i l i t 瓣 i a nf u n c t i o n ) 所决定的。在以往的大量有政府组织的拍卖活动中，比 如通讯频率，地皮，自然资源等，v c g 机制这样的特性能够更好的体 现服务社会的思想。然而，现在拍卖活动日益频繁以及普及，任何人 都可以在网上进行拍卖，并且以此作为主要的营利方式。如果再只考 虑买家的利益很显然是不合理，也是不合适的了。而在我们的拍卖商 有利的机制中，买家的自私行为不仅会最大化他个人的盈利，同时还 会增加卖家的收入。 拍卖中的竞争比概念最先是由【1 3 】提出的然而，【1 3 】的概念仅适用 于带有支配策略均衡的机制，而我们进一步推广了这个概念，使之能 够适用于更广泛的情境之中。 在拍卖商供给量有限和无限的情况下，我们都给出了具有常数竞争比 的拍卖商有利的机制。 在以前所有带限制条件的拍卖模型都只是考虑了带预算限制的模型。 在【6 ，1 7 ，2 0 】研究的模型中，拍卖商只拍卖一样物品，而且他们研究的是该 拍卖模型下的贝叶斯一纳什均衡。最近两年，【5 】和【2 】开始研究了有多个竞 拍者，且竞拍多份拷贝的情形，其中每个人都带有预算限制。 我们的工作是受到了【1 l ，2 】的启发。在【1 1 】中，拍卖商具有无限的供 货量，而且每个竞拍者至多只想要一份拷贝。很显然，这种情况下也不需要 考虑经济预算情况。在【2 】中，他研究了供货量有限的情况。而在我们的模 型中，我们即允许有限，也允许无限的供货量。而且每个买家既有经济预算 的限制，也有需求量的要求。因此，从本质上我们的模型要显得更加普遍和 复杂。 3 2 准备工作 1 4 在第2 节中，我们将给出该模型的形式定义以及相关的概念。第3 节我们 针对供货量无限的情况下，设计了拍卖商有利的机制。在第4 节，我们研究 了在该模型下竞拍者的行为策略。在第5 节，我们给出了在该机制下的无条 件竞争比。第6 节我们就供货量有限的情况进行了分析。 3 2 准备工作 3 2 1 拍卖商有利的机制以及无条件竞争比 尽管v c g 机制具有非常吸引人的特性一一它是个诚实的机制，即每个 参与者提交他的真正的类型能够保证最大化他的效用，但该机制同时也有 一些弱点。例如，在该机制下拍卖商的收入将会很低，甚至是o 。事实上，在 一个双边( 一边为买家，一边为卖家) 的市场中，如果在该市场中有大量的 不可分割的物品在销售的时候，v c g 机制将会最大化所有买家的利益，并 且相反地最小化卖家的利益f 2 7 ，1 8 1 。 在这一节中，我们将设计一种新的所谓的拍卖商有利的机制。这种机 制的主要特性就是每个竟拍者为了追求自身利益最大化而撒谎的话，不仅 不会减少拍卖商的收入，而且还有可能增加拍卖商的收入。在介绍具体的 定义之前，我们将在定义支配策略中所用到的假设推广到多维的情况。 假设3 2 1 对于每个竞拍者i ，不管其他人的提交的内容如何，如果他在自 己的某个变量上提交自己真实的类型能够最大化自己的盈利的话，他将在 这个变量上提交自a 的真实值。 很显然，从支配策略的定义我们可以看出，支配策略正是满足上述假设 的一维的纳什均衡。 定义3 2 2 拍卖商有利的机制( a u c t i o n e e r - a d v a n t a g e dm e c h a n i s m ) 在拍卖 商有利的机制之t 对于所有满足上述假设的纳什均衡拍卖商的收入均有 kr n 汹 一 只 。谢 3 2 准备工作 1 5 所以在拍卖商有利的机制之下，拍卖商的收入至少和每个竟拍者都说 实话的时候所得到的收入一样多。 为了和拍卖商有利的机制的定义相适应，我们将在g 0 1 d b e r g 等人在【1 3 】 中引入的关于拍卖的竞争比的概念进行进一步的推广。 定义3 2 3 无条件竞争比( u n c o n d i t i o n a l lc o m p e t i t i v er a t i o ) 一个拍卖4 具 有某个无条件竞争比p ，如果对于理性的竞拍者以及他们内心真实的报价 t ， 肫删( b ) 掣 其中k 是在该机制中满足i 述假设3 2 ，i 的纳什均衡r e v e n u e a 表示的是 拍卖机制a 的( 期望) 收入笋表示的如果拍卖商事先就已经知道所有 拍卖商真实的出价的话他所能够得到的最优的单价收入o ( 具体的定义将 在下面给出o ) 3 2 2有需求量要求的拍卖：模型以及符号 在这个模型之下，拍卖商拍卖一种物品，该物品有着无数多份拷贝。一 共有礼个竞拍者，i = l ，2 ，扎，参加拍卖。每个竞拍者t 有两个只有他自 己知道的信息：u 酞+ ，以及q n 。其中，u t 表示了竞拍者i 对于该物 品的每一份拷贝他所愿意支付的最大的价格，臼是表示t 所希望的购买量。 每个竞拍者 同时提交他们的竟拍价以及竟拍数量( 。，q ) 给拍卖商。 当拍卖商收到所有的竞拍价以及竞拍数量之后，拍卖商将决定每个竟拍者 将以多少的价格得到多少的拷贝。因此，该模型可以看作是多变量的单回 合秘密竞价拍卖。 定义3 2 a 给定一个按照竞拍价从高到低降序排列的竟拍矢量b = ( ( “1 ，c 1 ) ，( 缸n ，) ) ， 厂( b ) = 蕊钆七q 一一 1 s l s 奄 我们用p f 来表示这个相应的u k o ( 3 1 ) 3 3 机制：分享收入的随机划分拍卖1 6 从上面的定义可以看出如果拍卖齑事先知道所有竞拍者的芷真的竟 拍份以及竞拍数量，并且拍卖商只能够出一个统一的单价的时候，则，就 表示拍卖商所能够得到的最大的收入。而p f 就是相应的单价。 此外我们用( 吣来表示必须保证至少有两个赢家2 下的最优的单 个定价收入。即 厂2 (