一种公平的重叠联盟效用分配策略周鹏I，蒋建国1,2,张国富1,2合肥工业大学计算机与信息学院，合肥2300092合肥工业大学信息与通信工程博士厉科研流动站，合肥230009摘要：效用分配是联盟形成中的一个难点问题。针对重叠联阳形成中一个agentnJ'以同时参与多个任务的复杂悄形，提出一种公平的重叠联盟效用分配策略，采用讨价还价策略対多任务进行分派，基丁-多劳多得和效用非减划分多联盟效用。实例分析表明该策略可冇效避免资源冲突，保证了联盟的稳定性。关键词：多agent系统；重卷联盟形成；效用分配；资源冲突中图分类号：TP181AfairpayoffdistributionforoverlappingcoalitionformationZHOUPengi,JIANGJian-Guou,ZHANGGUO-FUI,21SchoolofComputerandInfomiation,HefeiUniversityofTechnology,Hefei2300092InformationandCommunicationEngineeringPostdoctoralResearchStation,HefeiUniversityofTechnology,Hefei230009Abstract:Payoffdistributionisadifficultproblemincoalitionformationinmulti-agentsystems(MAS).Inthispaper,thepayoffdistributioninoverlappingcoalitionformation(OCF)isdiscussed,whereanagentcanjoinmorethanonetasksatthesametime.AfairpayoffdistributionforOCFispresentedtoallocatetasksbasedonbargaininganddistributepayoffaccordingtotheprinciplesofmorepayformoreworkandnon-reducingutility・Finally,arepresentativecaseanalysisshowsthattheproposedstrategycansolveresourceconflictperfectlyandensurethestabilityofcoalitions.Keywords:Multi-agentsystems;overlappingcoalitionformation;payoffdistribution;resourceconflict联盟形成(coalitionfonnation)是联盟一切活动的基础，如何形成一个稳定均衡的联盟，使联盟朝着稳定的方向发展，是多agent系统(multi-agentsystems,MAS)理论的热点课题，基金项目:—国家I’1然科孚圧金(61004103.61174170.611(X)127).国家教冇部博士点基金(20100111110005)作者简介：周胡(1987・)，男，硕士研究生，主要研究方向：联盟博弈，多agent系统，电话：055162901392.Email：406835301@qq.com通信作者：蒋建国(1955J，男，教授，主要研究方向：分布式人工智能，复杂智能系统，电话:055162901375,Email：jgjiang@hfut.edu.cn张国富(I979-)，男，副教授，主要研究方向：人工智能.进化计算，电话：055162901392.Email：zgf@hfut.cdu.cnc正被国内外的众多学者所关注和研究，冃其应用已涉及到国民经济众多领域，如虚拟企业⑴、传感器网络［2］、多机器人协作［3］等。通常，联盟形成研究包含三个方而的问题，即联盟值计算⑷、联盟结构生成|5.6.小效用分配I8.9.10.1M2JO其中，效用分配问题主要研究如何将联盟收益划分给每个成员agent以确保协作联盟的稳定。因为，如呆效用分配不当很容易引起搭便车问题切，即有可能出现一些agen（贡献很少的资源却占据了人部分收益，而另外一些agent承担了人部分任务量却获得很少的报酬，这种分配的严重不合理会极大的打击这些agent执行任务的积极性，甚至会退出联盟，导致联盟无法稳定。然而，现冇大多数关于联盟效用分配的研究都是着眼于非重廉联盟（d⑸ointcoali・tion）［8.9.10.1LI2I，即要求一个agent在任意时刻都只能加入一个联盟。对于重叠联盟形成（overlappingcoalitionformation,OCF）问题，虽然在计算复杂性［I3.i4.i5.i6.i7.i8j、重叠联盟结构［19.20.21］等方而取得了一定的成果，但是对于重叠联盟的效用分配问题却很少涉及。究其原因，重叠联盟允许一个agent可以同时参与多个联盟，即一个联盟的若干成员可能会同时属于其他联盟，这就可能带来潜在的资源冲突问题，因为当多个联盟同时竟争某一资源有限的agent,而该agent乂无法同时满足如此多的联盟的请求时，系统就会产牛•资源冲突和联盟死锁，从而导致系统崩溃。而且，在OCF中如果某一个agent同时参与了多个联盟，那么其必然要将英持有的资源同时支配给这多个协作联盟，这时如何划分各联盟的效用给该agent就会成为一个相当棘手的难题，因为不同的资源分配形式可能会导致不同的效用分配结果。鉴于此本文在总结菲重...