Coalition Structure Generation With Given Required Bound Based On Coalition Combination
Coalition formation is a key topic in multi-agentsystems.Most of these researches concentrate on howto form a coalition and assign the revenues of thecoalition through negotiation.Another researchingbranch is to study the optimal divi-sion of agents intocoalitions(the pairwise disjoint subsets)so that thesum of the revenues of all coalitions is maximal.Onemay prefer a coalition structure that maximizes the sumof the values of the coalitions,but often the number ofcoalition structures is too large to allow exhaus-tiresearch for the optimal one.When practicalapplications can present required real bound on theworst case,and how to attain this demand via partialsearch? This paper analyzes the relations amongcoalition structures in depth and presents on a novelalgorithm based on coalition combination: the boundK(n)≥2 can be attained with searching of thosecoalition structures whose cardinality structure is inthe coalition combination set CCs(n,k).Finally,experiments show that the new algorithm is obviouslybetter than existing algorithms.
Luo Jianbin Hu Shanli Lin Yaohai
Department of Computer Science and Technology,Fuzhou University,Fuzhou,350002 Department of Computer Science and Technology,Fuzhou University,Fuzhou,350002;Department of Computer
国际会议
厦门
英文
555-559
2008-11-17（万方平台首次上网日期，不代表论文的发表时间）