（运筹学与控制论专业论文）若干拍卖中的算法及复杂度研究.pdf

若干拍卖中的算法及复杂度研究 击斋西 于茼晏 拍卖模型可描述如下：设有物品集合m 和竞价人集合为；每个竞价人得 到某些物品都会产生一定的利益，可用效用函数佻：2 m 一矿( i ) 来表示。 效用函数往往是竞价人的私人信息，不对拍卖人和其他竞价人公开；进行拍卖 时，每个竞标人提供一个并非真实的竞标函数b l ：2 m 一肘( i n ) ，即也不一 定与仇相同。拍卖人的任务就是设计一个物品分配方案以及确定得到物品的竞 价人所需支付的费用一拍卖机制设计：一方面促使竞价人采取其真实的效用函 数进行投标，另一方面使得拍卖的收益( 竞价人的收益或拍卖人的收益) 达到 最大。 在实际中，效用函数往往满足一定的组合性质( 如子模性质等) ，这类拍卖 模型称为组合拍卖。组合拍卖机制设计主要是从算法和计算复杂性角度来进 行的。当一个效用函数t ，的值口( s ) 只依赖于s 中物品的个数时，口被称为对称的， 此时相应的拍卖模型称为多重物品拍卖。一般地，多重物品拍卖机制包含一个 将m 个相同物品分配给n 个竞价人的分配算法以及一个支付函数，其目标是使得 竞价人的公共福利达到最大。本文首先对组合拍卖机制设计理论进行总结和归 纳，并对两种多重物品拍卖机制进行研究，这方面的主要研究结果有： 对于边际效用递减的多重物品拍卖模型，给出了最优分配的关于m ，n 的 多项式时间算法，并利用线性规划对偶理论加以证明。另外，当只有竞价 人个数n 看作是问题的输入时，利用贪心算法和m i r 算法思想，得到了基 于v c g 支付的一个实价机制，该机制在以扎，l o g m 为输入的多项式运算时 间内可得到( 1 一e ) 一近似度( 0 是任意给定常数) 的近似最优分配方案。 针对x d s 报价类的多重物品拍卖问题，首先证明了该问题等价于平均效 用递减模型，其次给出了一个基于贪心算法的近似分配算法，并分析了算 法近似度；同时指出该机制并不是实价机制。 由于在拍卖问题中，拍卖人实质上是物品拥有者，在市场中扮演着卖方的 角色，对以拍卖人的收益最大化为目标的拍卖机制的研究也具有重要意义。以 此为目标，本文总结并探讨了电子产品的拍卖。所谓电子产品，就是该物品可 用小到几乎可以忽略不计的成本来复制，如m p 3 版权等。现有的研究表明在实 价机制的前提下不存在近似度为常数的确定型有效分配算法。本文在这方面的 主要结果有： 提出了数字产品拍卖中的一个带有需求量和附加费用的多价格随机拍卖 机制，并讨论了它们的性质和拍卖人收益的竞争比。 关键词：p 困难；v c g 机制；m ，r 算法；s m ；x o s a l g o r i t h m sa n dc o m p l e x i t yr e s e a r c h e so ns o m ea u c t i o n s a b s t r a c t i na l la u c t i o nm o d e l t h e r ei sas e tmo fi t e r n sa n das e tno fb i d d e r s ； e a c hb i d d e rh a sav a l u a t i o nf u n c t i o n 仇：2 m _ r + ( i ) ，r e p r e s e n t i n gt h e b i d d e r sv a l u a t i o no ne a c hs u b s e to fi t e r n s i ng e n e r a l t h ev a l u a t i o nf u n c t i o n i sap r i v a t ei n f o r m a t i o nw h i c hi sn o tk n o w nb yt h ea u c t i o n e e ra n dt h eo t h e r b i d d e r s a n dt h eb i d d e r sm a ys u b m i tn o n t r u t h f u lb i d d i n g s 机：2 朋_ 冗+ ( i n ) i n s t e a do ft h e i rv a l u a t i o n s ，i e ，玩m a yn o tb ee q u a lt o 耽b a s e do n t h e s es u b m i t t e db i d d i n g s ，t h ea u c t i o n e e rt r i e st og i v e8 2 1a l l o c a t i o no ft h ei t e m s i i lmt ot h eb i d d e r sa n dt od e t e r m i n et h ep r i c e sf o rt h eb i d d e r sw h oo b t a i ns o m e i t e m s w h a tt h ea u c t i o n e e ra i m st oa r et w op o i n t s ：o n ei st of o r c et h eb i d d e r st o s u b m i tt h e i rt r u t h f u lv a l u a t i o n s a n dt h eo t h e ri st om a x i m i z et h ea u c t i o nu t i l i t y ( e i t h e rt h ep r o f i to fa u c t i o n e e ro rt h ep r o f i to ft h eb i d d e r s ) t h i si sc a l l e da u c t i o n m e c h a n i s md e s i g n ， i np r a c t i c e ，t h eb i d d e r sv a l u a t i o nf u n c t i o no f t e ns a t i s f i e ss o m ec o m b i n a t o r i a l p r o p e r t i e s ( s u c ha ss u b m o d u l a rp r o p e r t y ) t h e s ek i n do fa u c t i o n sa r er e f e r r e d t oc o m b i n a t o r i a la u c t i o n s t h em e c h a n i s md e s i g no fc o m b i n a t o r i a la u c t i o nf o c u s o ni t sa l g o r i t h m i ci s s u e sa n dc o m p u t a t i o n a lc o m p l e x i t y t h eb i d d e r sv a l u a t i o n f u n c t i o n 口i ss y m m e t r i ci fv ( s ) o n l yd e p e n d so nt h en u m b e ro fi t e m si ns ，a n di n s u c hc a s e ，t h ea u c t i o ni sc a l l e dm u l t i - u n i ta u c t i o n f o r m a l l y , t h em e c h a n i s mo f am u l t i - u n i ta u c t i o ni n c l u d e sa na u o c a t i o na l g o r i t h mw h i c ha l l o c a t emi d e n t i c a l i t e m st onb i d d e r s ，a n dap a y m e n tf u n c t i o nf o rt h eb i d d e r s ；i t sg o a li st om a x i m i z e t h et o t a ls o c i a lw a r f a r e i nt h i st h e s i s ，w ef i r s tg i v eas u r v e yo nt h ec 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 md e s i g n ，a n dt h e nd i s c u s st w ok i n d so fm u l t i u n i ta u c t i o n m o d e l s t h er e s u l t so nt h e s em o d e l sa r ea sf o l l o w s ： t h em u l t i u n i ta u c t i o nw i t hd e c r e a s i n gm a r g i n a lu t i l i t i e si sd i s c u s s e d f i r s t ，b a s e do nt h ed u a lt h e o r yo fl i n e a rp r o g r a m m i n g ，a no p t i m a la l - l o c a t i o na l g o r i t h mw i t hr u n n i n gt i m ep o l y n o m i a li n 仇a n dni sg i v e n n e x t ，w h e nna n dl o gm a r ev i e w e da st h ei n p u ts i z e ，m a k i n gu s eo ft h e 若干拍卖中的算法及复杂度研究 m e t h o d so fg r e e d ya l g o r i t h ma n dm i ra l g o r i t h m ，a ni n c e n t i v e c o m p a t i b l e c o m p u t a t i o n a l l y - e f f i c i e n tv c g b a s e dm e c h a n i s mi so b t a i n e d ，w h i c hg u a r - a n t e e s ( 1 一e ) 一a p p r o x i m a t i o nr a t i o ( w h e r ee 0 i saf i x e dc o n s t a n t ) a sf o rt h em u l t i u n i ta u c t i o nw i t hx o sv a l u a t i o nf u n c t i o n i ti sf i r s tp r o v e d t h a tt h i sk i n do fa u c t i o ni se q u i v a l e n tt ot h ea u c t i o n sw i t hd e c r e a s i n ga v e r - a g eu t i l i t i e s f o rs u c hm o d e l s ，a na p p r o x i m a t eo p t i m a la l l o c a t i o na l g o r i t h m i sg i v e nb a s e do ng r e e d ya p p r o a c h ，a n d t h ep e r f o r m a n c er a t i oi sa l s oa n a - l y z e d m e a n w h i l e ，i ti ss h o w nt h a tt h eg i v e nm e c h a n i s mi sn o tt r u t h f u l s i n c et h ea u c t i o n e e rp o s s e s s e st h ei t e m s ，h e s h ea c t sa st h es e h e ri nt h em a r - k e t s oi ti sm e a n i n g f u lt os t u d yt h ea u c t i o nm e c h a n i s mf r o mt h ea u c t i o n e e r s m a x i m u mp r o f i tp o i n to fv i e w a sf o rt h i sp r o b l e m ，w ed i s c u s st h ea u c t i o n so f d i g i t a lg o o d s d i g i t a lg o o d sa r es p e c i a lg o o d sw h i c hh a v ea ni m p o r t a n tp r o p e r t y ： i tc a nb ec o p i e de a s i l ya n dt h ec o p yc o s tc a nb ei g n o r e d ，s u c ha s ，m p 3c o p y r i g h t s o m ek n o w nr e s u l t si m p l i e st h a tt h e r ei sn oe f f i c i e n td e t e r m i n ea l l o c a t i o na l g o - r i t h mw i t hc o n s t a n ta p p r o x i m a t i o nr a t i ot oe n s u r et h et r u t h f u lm e c h a n i s m a s f o rt h ea u c t i o no fd i g i t a lg o o d s w eh a v et h ef o l l o w i n gr e s u l t s ： at r u t h f u lm u l t i p r i c ea u c t i o nm e c h a n i s mf o rd i g i t a lg o o d sa u c t i o ni sp r o - p o s e d ，a n dt h ea u c t i o n e e r sc o m p e t i t i v er a t i oi sa l s og i v e n m e a n w h i l e ，w e i n v e s t i g a t es o m ep r o p e r t i e so ft h i sm e c h a n i s m k e y w o r d s ：n p h a r d ；v c gm e c h a n i s m ；m i ra l g o r i t h m ；s m ；x o s x 独创声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含未获得 或其他教育机构的学位或证书使用过的材料。与我一同工作的同志对本研究所 做的任何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名：走佳签字日期：7 , - , 0 1 年f 月g 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，有权保留 并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。 本人授权学校可以将学位论文的全部或部分内容编入有关数据库进行检索，可 以采用影印、缩印或扫描等复制手段保存、汇编学位论文。( 保密的学位论文在 解密后适用本授权书) 学位论文作者签名： 良佳 签字日期：刀年歹月，日 导师签字：豸弓易 签字日期：如7 年歹月多日 第1 章综述 1 1机制设计与组合拍卖理论 1 1 1 机制设计 机制设计是经济学的一个分支，对机制的设计类似于对算法的设计或者是 函数的构造。通常情况下，不同参与人提供有利于自己的非真实的信息，机制设 计则是利用这些信息来进行决策或确定行动方案，以达到一定的利益目标，这 种利益可以是参与人的利益，也可以是决策者的利益。以下给出几个机制设计 的例子： 选举：每个投票者都可以看作一个参与人，他们的总利益通常由选举的 结果所确定。在这里，机制的设计就是确定采取何种投票形式、如何从众多选 票中提取结果等，使得投票的结果尽可能符合投票者的意愿。 工程选址： 当政府想要建一项公共设施( 如超市、图书馆、地铁站等) 时， 设施的选址是很重要的问题。这里，受益于这项工程的人或城市都是参与者，同 时他们也将承担修建设施的费用。不同的参与人往往从个人的利益出发提供对 选址问题的看法和信息，使得设施的建立对自己更有利，因此这些信息往往不 是真实的。机制设计就是利用这些信息来确定一个设旌建立的地址，同时给出 设施建立费用的分配方案，使得参与人的真实利益之和能够达到最大。 拍卖：一般来说，经济模型中市场上买方及卖方越多，这个模型就越接近 现实。拍卖是机制设计的一种特殊情况，它考虑的是市场上只有一个卖方( 称 为拍卖人) ，买方( 称为竞价人) 可以是多个的情况。它是利用众多竞价者所提 供的价格和信息，来确定如何分配拍卖品以及相应的拍卖价格，以达到一定的 目标，例如使拍卖人的利益或竞价人的总利益达到最大等。 拍卖机制理论及应用将在下几节叙述。 1 1 2 拍卖模型 拍卖问题的研究起源于一个非常简单的情况：拍卖人只拥有一个物品，他 将该物品分配给多个竞价人。由此提出两个问题：一是谁将得到这个物品：二是 若干拍卖中的算法及复杂度研究 得到这个物品的竞价人要付出的费用。诺贝尔经济学奖得主w i l h a r nv i c k r e y 1 1 对这种单个物品的拍卖模型的研究是拍卖理论研究的开始。 一般地，拍卖模型可描述如下： 设有物品集合m ( i m i = m ) ，竞价人集合( 1 n i = 几) ；每个竞标人得到某 些物品都会产生一定的利益，可用效用函数表示：饥：2 m _ 矿( i n ) ，效用 函数往往是竞价人的私人信息，不对拍卖人和其他竞价人公开；进行拍卖时， 每个竞价人提供一个并非真实的竞标函数b i ：2 m _ 矿( i n ) ，即6 i 不一定 与仇相同；拍卖人的任务是设计一个物品分配方案以及得到物品的竞价人所需 支付的费用一拍卖机制设计，其目的一方面促使竞价人采取其真实的效用函数 进行投标，另一方面使得拍卖的收入达到一定的目标。 总假定竞价人的效用函数满足两个条件： 单调性：对v s t m ，有v ( s ) v ( t ) 。 单位化：v ( o ) = 0 。 不同的竞价人具有不同的效用函数。一般地，每个竞价人对于m 个拍卖物 品有2 m 一1 个不同的效用函数值，因此描述一个一般的拍卖模型是非常复杂的。 然而，在实际中，效用函数往往满足一定的组合性质( 如子模性质等) ，这类 拍卖模型称为组合拍卖。以下给出几个效用函数的例子。若一个效用函数7 3 的 值u ( s ) 只依赖于s 中物品的个数，则称v 是对称的；否则，称之为非对称的。 对称的效用函数： ( 1 ) 单位需求效用函数：竞价人只需要一个物品，且其效用为1 ，即对任 何s d ，v ( s ) = 1 。 ( 2 ) 一预算效用函数：当物品子集s 中物品个数不超过k 时，其效用函数值 为俐，即 ( s ) = m i n k ，i s l 。 ( 3 ) 多数占优效用函数：当物品集合s 中物品个数不少于仇2 时，v ( s ) = 1 ；否 则，v ( s ) = 0 。 ( 4 ) 一般的对称效用函数：锄1 ，p 2 ，是非负实数，鼽表示竞价人获取 第i 个物品的效用，则任意物品集s 的效用值为u ( s ) = 逛| s l 亿。 ( 5 ) 边际效用递减效用函数：若在上述一般对称效用函数中，p l p 2 成立，则称相应的效用函数是边际递减的。 2 若干拍卖中的算法及复杂度研究 非对称的效用函数： ( 1 ) 可加性效用函数：竞价人对每个物品歹有一个效用值，对任意物品子 集s 的效用值是s 中各单个物品的效用值之和，即可( s ) = f s v j 。 ( 2 ) 单元需求效用函数：竞价人对每个物品j 有一个效用值，但他只需要一 个物品，h p v ( s ) = m a x j s 。、 ( 3 ) 代表性效用函数：物品分；k i n 2 对，竞价人只需要每对物品中的一个，并 且其效用为1 则给定物品子集s ，当s 中包含七个完全的物品对和f 个不配 对物品时( i s i = 2 k + ：) ，k s ) = 七+ f 。 1 1 3 拍卖的应用 拍卖理论先已被应用于很多领域，并且为企业以及政府等许多”拍卖人”创 造了丰厚的利润。 电磁波谱拍卖这种类型的拍卖如今受到了很多国家尤其是美国的关注。 通常政府是拍卖人，他们将不同地区的不同频段的电磁波拍卖给众多的竞价人， 如电话公司等。2 0 0 6 年8 月，美国联邦电信委员会将可用的电磁波分为1 1 2 2 个频 段，每个包含1 0 - 2 0m h z 的频率带宽，分别在不同地区进行拍卖，所得收入超 过1 0 亿美元。 网络流拍卖考虑图g ( ke ) ，竞价人需要将物品从图上的某一顶点运送到 另一顶点，为了通过图上的某一些边需要支付一定的费用，此时的拍卖人需要 考虑的是图上的哪些边允许哪些竞价人通过，才能使得所有竞价人支付的费用 之和达到最少。在这里每一条边不能让两个以上的竞价人使用。 关键词拍卖关键词拍卖已经被很多网络运营商，尤其是搜索引擎使用， 他们将不同的关键词拍卖给众多广告商，广告商们报价的不同将决定用户在 键入关键词进行搜索时其广告在网络页面上所处的位置。g o o g l e 在2 0 0 5 的收 入为6 1 4 亿美元，其中有9 8 的收入来源于关键词拍卖。y a h o o ! 也靠关键词拍卖 在2 0 0 5 挣得5 2 6 亿美元。 1 2 报价语言 拍卖模型主要由效用函数所确定，因此对于效用函数的系统化的描述可以 使拍卖模型更加清晰。粗略地讲，对于效用函数系统化的描述方法被称为报价 3u 若干拍卖中的算法及复杂度研究 语言。以下我们将列举一些正文中涉及到的报价语言，关于这方面的更多内容 参见f 2 】 1 原子报价( a t o m i cb i d ) 每个竞价人提交一个值对( s p ) ，其中s ，p 是竞价人对物品子集s 所愿 意支付的价格。对任意t m ，若s t ，v ( t ) = u ( s ) ：否贝j j v ( t ) = 0 。原子报 价又称单一需求( s i n g l e m i n d e d ) 报价。 在原子报价中，若对每个竞价人提交的s 是单一物品集( 即i s i = 1 ) ，则称 此原子报价为单元报价( s i n g l e t o nb i d s ) 。 2 o r 报价 每个竞价人提交一组原子报价，即( & ，p i ) ，其中s m ，a 是竞价人对物品 子集& 所愿意支付的价格( t = l ，2 ，七) 。此时，竞价人愿意以上述价格得到若 干互不相交的原子报价中的物品子集。o r 报价记为 ( & ，p 1 ) o r o r ( 鼠，m ) ， 对任意t m ，u ( t ) 定义为： u ( 丁) = m a x i 。日，e p t ， i e i o 其中，o = l s t ) ，于= j ogi l v i ，j i o ，& ns j = j 2 i - 。 3 x o r 报价 每个竞价人提交一组原子报价，即( & ，p i ) ，其中& m ，a 是竞价人对物品 子集s 所愿意支付的价格( i = 1 ，2 ，七) 。此时，竞价人愿意以上述价格得到原 子报价中价格最高的物品子集。x o r 报价记为 ( 是，p t ) x o r x o r ( 瓯，矶) ， 对任意丁m ，u ( t ) 定义为： v ( t ) = m a d c t ：& c _ t p i ，- 我们可以将o r 和x o r 作为效用函数的两种运算来定义更多类型的拍卖模 型。x o r 运算可以看作是选取参与运算的两个对象之一，而0 剐主算可以看作是 对参与运算的两个对象中的物品进行划分。严格地，有如下定义： 4 若干拍卖中的算法及复杂度研究 令u 和乱是两个效用函数，则( ux o r 牡) 和( uo ru ) 是由”和让得到的效用函 数： ( 口x o ru ) ( s ) = m a x ( u ( s ) ，u ( s ) ) ( 口o ru ) ( s ) = m a x r , t c _ s ，f n r ：毋( u ( r ) + u ( t ) ) 由此，给出如下两种报价语言。 4 x o s 报价 每个竞价入提交一组由单元报价构成的o r 报价，且他愿意获得这组o r 报 价中的一个。记竞价人提交的o r 报价为 矿= ( 歹1 ，p j 。) o r o r ( j k ，欺) ，j = 1 ，2 ，t 则x o s 报价u 的定义为： 影：u 1x o ru 2x o r x o r 5 o x s 报价 每个竞价人提交一组由单元报价构成的x o r 报价，且他愿意以提供的价格 获得若干组报价物品。记竞价人提交的x o r 报价为 护= ( j l ，功，) x o r x o r ( a ，p j 。) ，j = 1 ，2 ，t 则o x s 报价u 的定义为： u = t ，10 rv 20 r d r 口o 除了利用上述竞价人的报价语言来描述拍卖模型外，还可以利用效用函数 满足的性质对拍卖问题进行分类。l e h m a n n 等学者 3 】列举了具有经济学背景且 应用较多的几类效用函数： c f ：对任意的a ，b m ，若每个竞价人的效用函数口满足：v ( a ) + u ( b ) v ( a ub ) ，则口属于c f 类。 s m ：对任意的z ，y a f 和s m ，若每个竞价人的效用函数口满足： t ，( 1 ，e 越接近1 ，近似度越好。 随着对n p 困难问题的深入研究，人们开发出许多近似算法的方法和技巧， 如贪心算法，局部搜索法，基于线性规划的近似算法( 原始对偶算法和l p 舍入 法) ，动态规划，随机算法等，它们在解决不同的组合优化问题时，各有很好的 应用。 l - 4实价机制与拍卖机制设计 拍卖问题是利用众多投标者所提供的价格和信息，来确定如何分配拍卖品 及相应的拍卖价格( 支付函数) ，以达到一定的目标。这里我们假定每个竞价人 8 若干拍卖中的算法及复杂度研究 都是理性的，即他们想得到最大的收益。因此，物品的分配方案和支付函数的 选定都会迫使竞价人对提交的投标价采取一定的策略：报实价( 其真实的效用 函数) 还是进行某种程度的谎报。一般情况下，为追求真实的最大利益，往往要 求所设计的拍卖机制能够迫使竞价人采取报实价的策略，即实价机制。这方面 最重要的一个机制理论就是v c g 机制。以下将给出相关的定义和基本结论。 1 4 1 拍卖机制与实价机制 定义1 4 1 ( 机制) 给定物品集合m 和竞价人集合；每个竞价人i n 都 具有一个策略集合，他可以选择其中任意策略a k ；所有竞价入的策略空间 为y = ，k ( 佗= i 1 ) 。机$ i j m ( o ( v ) ，p ( y ) ) 包含两个元素： ( 1 ) 分配函数d ：n ：1 _ m n ：对任意 n ，o i = o i ( a 1 ，a 2 ，a n ) 是该机 制所确定的分配给竞价人i 的物品子集； ( 2 ) 支付函数p ：n ：lk _ 舻：对任意t n ，p i = p i ( a 1 a n ) 是该机制所确 定的向竞价人i 收取的费用； ( 3 ) 对任意i n ，其收益是其效用函数值与机制所确定的支付费用之差，即 啦= 饥( 晚( n 1 ，矿) ) - p i ( a 1 ，扩) 理性的竞价人总是采取使其收益达到最大的策略。 定义1 4 2 ( 占优策略) 给定竞价人的策略空间v = 和拍卖机 制m ( d ，p ) 。若存在一个策略向量( 口1 ，a n ) ( a k ，v i ) ，使得 对任意的k 都成立，则称策略( 0 1 ，矿) 为机制m ( d ，p ) 下的占优策略，且 称该机s j j m ( o ，p ) 含有占优策略。 定义1 4 3 ( 实价机制) 给定拍卖机制m ( d ，p ) ，若每个竞价人i n 报实价 的策略所组成的策略向量是此机制下的占优策略，则称该机n m ( o ，p ) 是一个实 价机制。 9 n 0 l + 0驴 一 a口 p 一 ， 卵卵 m 鼽一 一驴 、，l，- 口 d 0 0 吼 吼 忧 优 一 若干拍卖中的算法及复杂度研究 1 4 2v c g 机制 拍卖物品集合必对竞价人集合的分配记为( & ，s 2 ，& ) ，其中当i j 时s n 岛= d 。记竞价人i 的效用函数为仇：2 m _ r + 。分配( & ：岛，& ) 所 确定的公共福利定义为所有竞价人相应效用函数值的和，即 ：。v , ( s 0 。 在许多情况下，拍卖的目的都是寻找能够使得公共福利达到最大的分配算 法，称此时的分配为最优分配。然而，r m k a r p 4 1 于1 9 7 2 年给出从最大独立集 问题到单一需求报价组合拍卖的分配问题的判定形式的多项式变换，从而证明 了求解一般情况下的组合拍卖问题的最优分配是p 一困难的。 v c g 机制是由v i c k r e y 1 】、c l a r k e 9 】、g r o v e s 1 0 给出的一种实价拍卖机制， 在拍卖理论研究中具有重要的意义。 定义1 4 4 ( v c g 机制) 若拍卖机f 矗l j m ( o ，p ) 满足： ( 1 ) o ( y ) = ( 0 1 ，0 2 ，0 n ) 是使得公共福利最大的分配，即最优分配； ( 2 ) 竞价人i n 的支付定义为 轨( ) = i j ( d ( y ) ) + h i ( v 一) ， ( 1 4 1 ) 其中 一= ( u l ，忱一1 ，v i + 1 ，v n ) ，_ r h ( ) 是u 一的任意函数。 则称该机$ l j m ( o ，p ) 为v c g 机制；且具有形如( 1 4 1 ) 的支付函数的机制称为基 于v c g 支付的机制。 定理1 4 5 1 1 1 1v c g 机制是实价机制。 由于v c g 机制要求分配函数是最优分配，然而，如前所述，这在一般情况 下是p 一困难的。当考虑的机制是建立在近似最优分配基础上时，基于v c g 支 付的机制通常不再是实价机n i i l 。对于一般的组合拍卖问题，目前仍没有在近 似最优分配基础上通用的保证是实价机制的支付函数的构造方法。 然而，针对某些具体的拍卖模型，许多学者给出了基于近似最优分配的实 价机制的好的结果，如n i s a n 等 1 2 给出的m i r 算法，它在多重物品拍卖模型中 有很好的应用。 1 0 若干拍卖中的算法及复杂度研究 1 4 3 多重物品拍卖与m i r 算法 多重物品拍卖是指将m 个相同物品分配给扎个竞价人的组合拍卖，它是组 合拍卖的一种特殊情况。单一需求的组合拍卖问题的分配问题实质上是背包问 题，因此对于一般情况下的多重物品拍卖的分配问题仍然是n p - 困难的，若 想使用v c g 机制得到实价机制在算法上就不能实现了。n i s a n 等学者f 1 2 1 给出 的m i r 算法则是针对多重物品拍卖给出了在近似最优分配基础上的实价机制。 定义1 4 6 ( m i r 算法) 对所有可能的分配集合a 及其子集冗，称分配算 法0 是m i r 算法若对于任意的报价b 。有o ( b ) r ，且在r 中的所有分配中，当分 配为d ( u ) 时，公共福利达到最大，则称分配算法是m i r 算法。 引理1 4 7 1 1 2 1 分配算法是m i r 算法，且基于v c g 支付的拍卖机制是实价机 制。 在m i r 算法的应用中，d o b z i n s k i 1 3 针对多重物品拍卖模型，构造了一个时 间复杂度为o ( n l o g m + n 5 ) 的2 近似算法。本文将针对多重物品拍卖，对s m 类 和x o s 类模型进行讨论，主要研究结果有： ( 1 )对于边际效用递减的多重物品拍卖模型，给出了最优分配的关于m ，n 的 多项式时间算法，并利用线性规划对偶理论加以证明。另外，当只有竞价 人个数佗看作是问题的输入规模时，利用贪心算法和m i r 算法思想，得到 了基于v c g 的一个实价机制，该机制在以n ，l o g m 为输入的多项式运算时 间内可得到( 1 一e ) 近似度( e 0 是任意给定常数) 的近似最优分配方案。 ( 2 ) 针对x o s 报价类的多重物品拍卖问题，首先证明了该问题等价于平均 效用递减类模型，其次给出了一个基于贪心算法的近似分配算法，并分析 了算法近似度；同时指出该机制并不是实价机制。 1 4 4 其他实价机制的构造 自k a r p 4 证明了一般情况下的拍卖问题的分配问题是n p 困难的之后，众 多学者开始构造具有特殊结构的拍卖模型的实价机制。n i s a n 1 4 ：l t 匿过使用线 性规划对偶理论和椭球算法证明了g s 类的组合拍卖问题的分配问题是多项 式可解的。事实上，g s 类的组合拍卖是含有w a l r a s i a a 均衡价格【1 5 1 的，在文 献f 1 5 】中，g u l 等学者还证明了所有的实价机制都存在w a l r a s i a n 均衡价格，并 且所有存在w 甜r a s i a n 均衡价格的组合拍卖都可以容易地构造出实价机制。然 若干拍卖中的算法及复杂度研究 而，对于s m 类拍卖模型，l e h m a n n 3 1 已指出它不存在w a l r a s i a n 均衡价格，因此 对于此类及其更宽泛的模型实价机制的构造就非常困难了。l e h m a n n 放弃了寻 求s m 类组合拍卖的实价机制的努力，找到了关于此类拍卖的分配问题的2 近 似算法。 目前，拍卖机制的研究大多以公共福利最大化为目标，对于以拍卖人收益 最大化为目的的拍卖，相关的结论较少。最近，随着电子产品和网络拍卖的迅 速发展，这方面的研究有较大进展。g o l d b e r g 等f 1 6 】讨论了电子产品的拍卖。所 谓电子产品，即是拍卖者仅有一个物品，但是这个物品可用小到几乎可以忽略 不计的成本来复制。g o l d b e r g 等在他们的文章中指出在实价机制的前提下，不 存在近似度为常数的确定型有效分配算法。对于电子产品这种简化情况尚且有 如此“差”的近似度，更何况那些一般的情况，这或许是以拍卖人的收益最大化 为目标的相关研究比较少的原因。 g o l d b e r g 等f 1 6 】针对电子产品拍卖模型，提出了二划分的支付函数的设计思 想，这一思想对实价机制的构造有很大的贡献，但不足之处在于他们提出的是 随机分配算法，而非确定型的，这在实际应用中有一定的局限性。f i a t 等f 1 7 l 在 文献f 1 6 1 的基础上提出了可取消的拍卖以及成本均担的拍卖模型的实价机制，这 些实价机制的构造更加联系实际，有很好的实际意义。 本文第三章的工作建立在文献 1 6 1 文献1 7 1 的基础上，针对带有需求量和附 加费用的电子产品的拍卖模型，提出了一种随机的多价格拍卖机制，并讨论了 他们的性质和拍卖人收益的竞争比。 第2 章多重物品拍卖 本章讨论两类多重物品拍卖问题，分别给出了这些问题的分配算法，以及 支付函数的构造。对于分配算法不是最优的情况给出了近似度。 2 1边际效用递减的多重物品拍卖 2 1 1预备知识：线性规划及其对偶理论 线性规划问题是指在一些线性约束的前提下使得目标函数最大或者最小的 问题。其数学定义如下： r a i nc r = fa x b( 2 1 1 ) i 瓤0 i = 1 ，2 ，佗 其中a = ( ) m n ，b = ( b 1 ，5 2 ，6 m ) t ， c = ( c 1 ，c 2 ，岛) t ，z = ( x l ，z 2 ，$ n ) t 。称满足式( 2 1 1 ) 的约束条件的 解z 为可行解，对应的c 乇值为目标值。若可行解x 使得目标值达到最小，称此可 行解为最优解，最优解对应的目标值为最优值，记为o p t ( z ) 。 现实中存在许多与组合问题有关的线性规划，这些问题以各种方式与对偶 的思想相联系。线性规划对偶理论正是在这种背景下被提出的。称如下线性规 划( 2 1 2 ) 是线性规划( 2 1 1 ) 的对偶规划： m a xy t b s t j m c( 2 1 2 ) iy i 0 t = 1 ，2 ，m 其中可= ( y t ，y 2 ，) t 。称( 2 1 1 ) 为原始规划，( 2 1 2 ) 为其对偶规划。可以证 明，对偶规划的对偶是其原始规划。 互为对偶的一对线性规划不仅只是表面的关系，它们之间存在着本质的联 系，这些联系构成了线性规划对偶理论的基础。 若干拍卖中的算法及复杂度研究 弱对偶定理对于形如式( 2 1 1 ) 的线性规划，其任意可行解的目标值不小 于其对偶线性规划可行解的目标值。 强对偶定理如果一个l p 有最优解，则它的对偶也有最优解，并且它们的目 标值相等。反之，若z ，可为原始l p 和其对偶的可行解并且它们的目标函数值相 等，则z ，秒分别为原始l p 和对偶l p 的最优解。 2 1 2 贪心算法 多重物品拍卖是指将m 个相同物品分配给n 个竞价人的组合拍卖，如无特别 说明本章所讨论的模型均在多重物品拍卖范围内。它是组合拍卖的一种特殊情 况。本章将着重叙述满足边际效用递减的多重物品拍卖，先给出此类拍卖的一 些记号。 记号：m 物品个数。 n 竞价入个数。 仇( 七) 竞价人i 对七个物品集的报价。i = l ，2 ，礼；七= 1 ，2 ，m 。 只( 七) = 仉( 忌) 一仇( 七一1 ) i = 1 ，2 i ，佗；k = 1 ，2 ，仇。 定义2 1 1 称只( 忌) 为第i 个竞价人的边际效用，边际效用递减的性质有如下 的数学表达式 只( 七) 只( 七+ 1 ) i = 1 ，2 ，礼；七= 1 ，2 ，m 一1 事实上，在多重物品拍卖中o x s = g s = s m ，如引理2 1 2 所示： 引理2 1 2 在多重物品拍卖中d x s = s m 。 证明：只需证s mco x s 臣p 可。 由s m 的定义可知，它与边际效用递减是等价的 3 】。设p i = u ( i ) 一u ( i 1 ) ，i = 1 ，2 ，m ，则由边际效用递减的性质可知p i p i + 1 ( i = l ，2 ，m 一1 ) 。p 可 用d x s 表示如下： 定义o x s 的x o r 原子报价为= ( 1 ，p i ) x o r ( 2 ，p i ) x o r x o r ( m ，p t ) ，i = l ，2 ，m 。则u ( i ) = u 1o r o r ( i = 1 ，2 ，m ) ，由此可知s mco x s 。 定理得证。 针对边际效用递减的多重物品拍卖模型，考察如下的分配算法： 贪心算法 1 4 若干拍卖中的算法及复杂度研究 s t e p0 令q 1 = q 2 = = = 0 s t e p1 设q = m a x p i ( 吼+ 1 ) ：i = l ，2 ，礼) = p i 。( 哦。+ 1 ) 令q i 。+ 1 _ 儡o s t e p2 若n i - - - - - 1m o p t ( i p ) 。l p r 的对偶规划为 r a i n m u + s i ( d l p ) s 一裳虢( 七) i = 1 , 2 , - - - n ；k = 1 , 2 , - - - , 识 i 乱0 ，s f 0 i = 1 ，2 ，n 由弱对偶定理可知o p t ( o l p ) _ o p t ( l p r ) 。 令矿为贪心算法最后一次迭代中q 的值且s ：= 撕( g ) 一矿q t ，其中口l ，9 2 ，为 算法的输出。接下来将证明向量( “，s ：，s ：) 为d l p 的最优解。 由边际效用递减的性质及矿的构造可得 a ( 吼+ 1 ) u 4 a ( 岱) ，s ；0 i = 1 ，2 ，n 1 5 谤 净 魄 n 谶 m 黼 觚m 一 j 七 o = ； = m随讯l，、-_i_【 ts 若干拍卖中的算法及复杂度研究 同时，对任意的i = 1 ，2 ，佗；凫= 1 ，2 ，m ，有： 1 ) 若忌吼，则 七七 七u 。+ s ；一仇( 七) i ( 七一吼) 乱+ 一魂( 歹) 2 ( k - 依)