一种有效的决定优胜者问题的近似算法.docx

Vol125No.7July2004第25卷第7期2004年7月小型微型计算机系统MINI-MICROSYSTEMS一种有效的决定优胜者问题的近似算法李峥,李师贤(中山大学计算机科学系,广东广州510275)摘要:组合拍卖是多Agent系统常用的一种协商机制,而决定优胜者问题是该机制不可避免的一个NP问题.这个问题的近似算法CASUS,相对于前人的工作,它主要在以下方面作了改进:提出更精确的估算收益上界的启发规则;提出对叫价进行两级处理,并在分析算法复杂度的基础上,限定有哪些信誉好的足球投注网站空间的大小,保证多项式时间内有解;大大降低了算法的空间复杂度.关键词:决定优胜者问题;组合拍卖;启发规则;深度优先有哪些信誉好的足球投注网站中图分类号:TP311.132.3文献标识码:A文章编号:100021220(2004)0721393204EfficientApproximateAlgorithmforWinnerDeterminationLIZheng,LIShi2xian(DepartmentofComputerScience,ZhongshanUniversity,Guangzhou510275,China)Abstract:CombinatorialAuctionisapopularnegotiationmechanisminMulti2agentsystem,andWinnerDeterminationistheessentialNPprobleminthismechanism.Inthisarticle,anapproximatealgorithmforWinnerDeterminationisputforward.Comparewithothers’work,thisalgorithmhasbeenimprovedintheseaspects:inheuristicsearchingprovideamoreaccurateheuristicruleforestimatingtheupperlimitofrevenue;basedonthealgorithmanalysis,re2strictthesearchingspaceefficientlybytwo2layerdisposalsonbids,thisensurethealgorithmtoobtaintheresultinpolynomialtimeandmakeitmuchbetterthanthemainstreamalgorithmsinspacecomplexity.Keywords:winnerdetermination;combinatorialauction;heuristicrule;depth-firstsearch1引言明确地表达这种关联,它同时对多种资源进行分配,允许A2gent同时抛出任意多个叫价,每个叫价都是针对一个资源集的,而不是单个资源.组合拍卖的重要性在于允许Agent根据它对资源的使用将相关联的资源作为一个整体进行叫价,这样做更为合理,Rothkopf在1998年的一篇论文中重点阐述了使用组合拍卖的合理性4.因此,在实际应用中组合拍卖有很大的适用空间,在这方面比较著名的例子是美国联邦通信协会FCC售卖通信波段的交易,在引入合理的拍卖机制后,给它带来了数十亿美元的收入3.1.1问题的提出拍卖机制越来越引起分布式人工智能领域的研究者的重视,因为拍卖是一种有效的多Agent系统中的协商机制,广泛地被应用于资源分配、时间调度、路由选择、商品交易等领域的协商系统中.在这些领域的应用中,以资源分配为例,代表竞价者的竞价Agent往往希望对一个资源的集合进行叫价,而不是对资源集合中的每项资源单独叫价.因为竞价Agent通常需要多项资源来完成一个任务,比如,某个Agent需要一台打印机和一台扫描仪来完成一项工作,在这项工作中它可以获得x元的收入,于是它就知道如果它以低于x元的价格一并获得打印机和扫描仪,它就能赚钱,因此在它的眼中,打印机和扫描仪就具有某种关联,它希望以它们作为一个资源集进行出价.在实际应用中,从用户角度出发的这种“关联”是普遍存在的,比如铁路的使用权的拍卖中,竞价者也许希望获得一组首尾相接的铁路的使用权;又比如在工厂的时间调度中,竞价者也许希望同时获得包含多个时间片的一整段时间的占用权.组合拍卖(CombinatorialAuction)就是允许竞价Agent1.2问题的描述组合拍卖中有一个不可避免的NP完全的计算问题——决定优胜者问题(WinnerDetermination).决定优胜者问题是指作为供给方的Agent在收到竞价Agent的叫价后,决定将资源分配给谁的问题.它必须在所有叫价中选出一个叫价子集,这个叫价子集中的叫价都是不相冲突的,即它们都针对不同的资源,