南京大学学报（自然科学版）Issue(4)：749-761,13.DOI:10.13232/j.cnki.jnju.2015.04.013
带有联盟个数约束的最优联盟结构生成
The optimal coalition structure generation with the constrained number of coalition
摘要
Abstract
Forming effective coalitions is a major area of research in the field of multi-agent systems.Coalition formation is one of the basic methods for establishing cooperations among agents that involve the creation of coherent groupings of independent agents for the sake of achieving their individual or collective goals efficiently. What′s more,this usually needs to calculate a value for every possible coalition,and the value of coalition indicates the profit that coalition would generate if it was formed.However,once these values are calculated,the agents usually need to find a combination of coalitions known as coalition structure,in which every agent belongs to exactly one coalition and there is no intersection between coalitions,and the overall outcome of the system is maximized by forming coalition structure.CSG(coalition structure generation)involves partitioning a set of agents into coalitions so that social surplus is maximized.However,the CSG problem is extremely challenging due to the number of possible solutions that need to be examined,which grows exponentially with the number of agents involved.Traditionally, there have been put forward many algorithms to solve this problem ranging from dynamic programming to improved dynamic programming,to integer programming,and all of these techniques suffer from having no constaints on the number of coalitions.However,in many real-world applications,there are inherent constraints on the number of coalitions.In this paper,we present the first systematic study of constraint on the number of coalition,and use the DP(dynamic programming)theory to develop an algorithm,which is named as CCDP(coalition constraint dynamic programming),for generating an optimal(welfare-maximizing)coalition structure.Furthermore,it is proved that the time complexity of this algorithm is O(3n ).In the end,we analyze and verify the influence of agent’s number and the size of values of constraints on the algorithm performance through detailed experiments.关键词
联盟结构/联盟个数约束/动态规划/联盟约束动态规划(CCDP)/时间复杂度Key words
coalition structure/the constraint of the number of coalition/dynamic programming/coalition constraint dynamic programming(CCDP)/time complexity分类
信息技术与安全科学引用本文复制引用
徐广斌,刘惊雷..带有联盟个数约束的最优联盟结构生成[J].南京大学学报（自然科学版）,2015,(4):749-761,13.基金项目
国家自然科学基金(61403328,61403329),山东省自然科学基金(ZR2013FM011,ZR2013FQ023,ZR2013FQ020, ZR2014FL009),山东省教育厅科技计划(J14LN23) （61403328,61403329）
