基于有穷损害优先法求解组合拍卖竞胜标问题研究

《基于有穷损害优先法求解组合拍卖竞胜标问题研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、第21卷第3期2012年6月运筹与管理0PERATIONSRESEARCHANDMANACEMENTSCIENCEV01．21，No．3Jun．2012基于有穷损害优先法求解组合拍卖竞胜标问题研究钱巍1’2，冯玉强1，唐振宇1(I．哈尔淀工业大学经济管理学院．黑龙扛哈尔滨150001；2．东北农业大学经挤管理学院．黑龙江晗尔演t50030)摘要：迄今为止，组合拍卖竞胜标问题并不存在一个多项式时闻复杂度的算法．其计算复杂性与拍卖效率之间的矛盾一直是影响组合拍卖广泛应用的主要障碍。它是一个NP难问题，也是组合拍卖机制设计中的难题之一。而有穷损害

2、优先方法是纯粹递归论中的一个十分重要的现代方法，特别对NP难问题求解算法的设计，对研究依复杂度决定的偏序结构的构造是一个很基本的有用工具。因此．本文提出根据组合拍卖的内在特性，将各不同的拍囊商品按照拍卖机制的要求，并结合其自身的协同价值等因素，设定一个优先序，然后采用有穷损害优先法有效有序地解决。关键谣：组合拍卖；竞胜标确定；NP难问题；有穷损害优先法中圈分类号：C931．9文章标识码：A文章编号：1007-3221(2012J03-Ol“-04SolutiontotheWinnerDeterminationProbleminCombina

3、torialAuctionsByFiniteInjuryPriorityMethodQIANWeil”，FENGYU．Qiang‘，TANGZhen．Yul(1．School矿Management，HarbinInstituteofTechnology，Harbin150001，China；2．DepartmentofEconomicsmanagement。NortheastAgriculturalUniversity，Harbin150030，China)Abstract：Sofar，thewinnerdeterminationprobl

4、emincombinatorialauctionshasnothadapolynomialtimecom·plexityalgorithm．ItisanNP-hardproblem．Thefiniteinjuryprioritymethodisoneoftheveryimportantmodernmethodsinrecursiontheory．Inparticular。itisaveryusefultoolordesigningtheNP·hardproblemsolvingalgo-rithmaccordingtothecomplexi

5、tyoftheofthepartialorderstructure．So，anapproximatealgorithmisproposedforsolvingthewell．knownNPhardproblem-thewinnerdeterminationproblemincombinatorialauctions．Keywords：combinatorialauctions；thewinnerdeterminationproblem；NP·hardproblem；finiteinjuryprioritymethod0引言在组合拍卖中，如果

6、拍卖商要拍卖Ⅳ种物品，而且允许投标者可以对商品的任意组合进行投标，那么在最极端的情况下．拍卖商将会得到2”一1个不同投标集合，在这个2“一1个投标集合中．寻找能够使拍卖商收益最大化的投标组合就是所谓的组合拍卖中竞胜标确定问题(WDP)。迄今为止，对这个问题的求解的多项式时间复杂度的算法并不存在，能够求解出最有效率的分配结果，是一个NP难问题，也是组合拍卖机制设计中的难题之一，还是阻碍在实际中组合拍卖能够广泛应用的原因之一。其计算复杂性与拍卖效率之同的矛盾一直是影响组合拍卖广泛应用的主要障碍。很多国际上在拍卖领域研究的著名学者包收稿日期：20

7、11-06-23’基金项目：团謇自然科学基全簧助项日(70572023)；墨龙扛省自然科学蓉奎量助嘎茸(zd200803．oI)作者简介：钱冀(1974·)，女。在读博士．教师．研究方向：空业信息化、商务智镌；冯玉强，女．教授，博士生导师；研克方向：袅幕支特謦蟪，量理信息蠹地；磨攉宇．女。研宽馆更．研究方向：决蕈支持拳蛇，商务智能，信息童源管理。第3期钱巍，等：基于有穷损害优先法求解组合拍卖竟胜标问题研究145括Rothkopf、T．Sandholm、Nisan等都对WDP求解障碍进行了深入研究。Rothkopf等人证明，就是在每个投标的投

8、标价格都为l。并且每个竞标者也只对包含商品数目不超过3种的组合进行投标的简单情况下。组合拍卖WDP也仍然是NPC问题¨1。所以学者们先后以不同的视角提出了各式各样的WDP算法，这