文档介绍：中国海洋大学硕士学位论文若干拍卖中的算法及复杂度研究姓名:赵佳申请学位级别:硕士专业:运筹学与控制论指导教师:方奇志20090601若干拍卖中的算法及复杂度研究击斋西于茼晏拍卖模型可描述如下:设有物品集合M和竞价人集合为Ⅳ;每个竞价人得到某些物品都会产生一定的利益,可用效用函数佻:2M一矿(i∈Ⅳ)来表示。效用函数往往是竞价人的私人信息,不对拍卖人和其他竞价人公开;进行拍卖时,每个竞标人提供一个并非真实的竞标函数bl:2M一肘(i∈N),即也不一定与仇相同。拍卖人的任务就是设计一个物品分配方案以及确定得到物品的竞价人所需支付的费用一拍卖机制设计:一方面促使竞价人采取其真实的效用函数进行投标,另一方面使得拍卖的收益(竞价人的收益或拍卖人的收益)达到最大。在实际中,效用函数往往满足一定的组合性质(如子模性质等),这类拍卖模型称为组合拍卖。组合拍卖机制设计主要是从算法和计算复杂性角度来进行的。当一个效用函数t,的值口(S)只依赖于S中物品的个数时,口被称为对称的,此时相应的拍卖模型称为多重物品拍卖。一般地,多重物品拍卖机制包含一个将m个相同物品分配给n个竞价人的分配算法以及一个支付函数,其目标是使得竞价人的公共福利达到最大。本文首先对组合拍卖机制设计理论进行总结和归纳,并对两种多重物品拍卖机制进行研究,这方面的主要研究结果有:对于边际效用递减的多重物品拍卖模型,给出了最优分配的关于m,n的多项式时间算法,并利用线性规划对偶理论加以证明。另外,当只有竞价人个数n看作是问题的输入时,利用贪心算法和MIR算法思想,得到了基于VCG支付的一个实价机制,该机制在以扎,logm为输入的多项式运算时间内可得到(1一E)一近似度(￡>0是任意给定常数)的近似最优分配方案。针对XDS报价类的多重物品拍卖问题,首先证明了该问题等价于平均效用递减模型,其次给出了一个基于贪心算法的近似分配算法,并分析了算法近似度;同时指出该机制并不是实价机制。由于在拍卖问题中,拍卖人实质上是物品拥有者,在市场中扮演着卖方的角色,对以拍卖人的收益最大化为目标的拍卖机制的研究也具有重要意义。以此为目标,本文总结并探讨了电子产品的拍卖。所谓电子产品,就是该物品可用小到几乎可以忽略不计的成本来复制,如mp3版权等。现有的研究表明在实价机制的前提下不存在近似度为常数的确定型有效分配算法。本文在这方面的主要结果有:提出了数字产品拍卖中的一个带有需求量和附加费用的多价格随机拍卖机制,并讨论了它们的性质和拍卖人收益的竞争比。关键词:Ⅳ;VCG机制;M,R算法;SM;;eachbidderhasavaluationfunction仇:2M_R+(i∈Ⅳ),representingthebidder’—truthfulbiddings机:2朋_冗+(i∈N)insteadoftheirvaluations,.,,:(eithertheprofitofauctioneerortheprofitofthebidders).,thebidder’binatorialproperties(suchaSsubmodularproperty).’Svaluationfunction口issymmetricifv(s)onlydependsonthenumberofitemsinS,andinsuchcase,theauctioniscalledmulti-,themechani