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 involves 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, 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 all of this techniques suffer from having no constaints on the number of coalitis ons. However, in many real-world applications, there are inherent constraints on the number of coalitions. Against this background, 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
{{custom_sec.title}}
{{custom_sec.title}}
{{custom_sec.content}}
References
[1] Iwasaki A，Ueda S, Hashimoto N, et al. Finding core Lor coalition structure utilizing dual solution Artificial Intelligence, 2015，22(5):49一66
[2] 高 阳. 中国数据挖掘研究进展. 南京大学学报(自然科学), 2011, 47(4): 351-353.
[3] Brink R V D, Dietz C. Union values for games with coalition structure. Decision Support Systems,
2014, 66(10): 1-8.
[4] Rahwan T, Michalak T, Wooldridge M, et al. Anytime coalition structure generation in multi-agent systems with positive or negative externalities. Artificial Intelligence, 2012, 186(0): 95-122.
[5] Zick Y, Markakis E, Elkind E. Arbitration and stability in cooperative games with overlapping coalitions. Journal of Artificial Intelligence Research, 2014, 50(1): 847-884.
[6] Balas E, Padberg M W. Set partitioning: A survey. SIAM review, 1976, 18(4): 710-760.
[7] Tsvetovat M, Sycara K, Chen Y, et al. Customer coalitions in the electronic marketplace. In: Proceedings of the 4th International Conference on Autonomous Agents. 2001: 263-264.
[8] 刘惊雷，张 伟，童向荣等. 一种时间复杂度的最优联盟结构生成算法. 软件学报, 2011,5(22): 938-950.
[9] Dang V D, Dash R K, Rogers A, et al. Overlapping coalition formation for efficient data fusion in multi-sensor networks. In: Proceedings of the 21th AAAI Conference on Artificial Intelligence(AAAI). 2006:635-640.
[10] Wu Q, Hao J K. Solving the winner determination problem via a weighted maximum clique heuristic. Expert Systems with Applications, 2015, 42(1): 355-365.
[11] 冯文娜. 关系规范视角下的联盟结构与联盟绩效研究. 山东大学学报, 2012, 6(5): 95-100.
[12] Sandholm T, Larson K, Andersson M, et al. Coalition structure generation with worst case guarantees. Artificial Intelligence, 1999, 111(1-2): 209-238.
[13] 刘惊雷，童向荣，张 伟. 一种快速构建最优联盟结构的方法. 计算机工程与应用, 2006, 42(4): 938-950.
[14] 苏射雄，胡山立，林超峰等. 基于局部最优的联盟结构生成算法. 计算机研究与发展, 2007,44(2): 277-281.
[15] Voice T, Polukarov M, Jennings N R. Coalition structure generation over graphs. Journal of Artificial Intelligence Research, 2012, 45: 165-196.
[16] Yeh D. A dynamic programming approach to the complete set partitioning problem. BIT Numerical Mathematics, 1986, 26(4): 467-474.
[17] Rahwan T, Jennings N R. An improved dynamic programming algorithm for coalition structure generation. In: Proceedings of the 7th International Conference on Autonomous Agents and Multi-agent Systems (AAMAS). 2008: 1417-1420.
[18] Rahwan T, Ramchurn S D. An anytime algorithm for optimal coalition structure generation. Artificial Intelligence, 2009, 34: 521-567.
[19] Rahwan T, Jennings N R. Coalition structure generation: Dynamic programming meets anytime optimisation. In: Proceedings of the 23th AAAI Conference on Artificial Intelligence (AAAI).2008: 156-161.
[20] Rahwan T, Michalak T, Elkind E, et al. Constrained coalition formation. In: Proceedings of the 25th AAAI Conference on Artificial Intelligence(AAAI). 2011: 719-725.
[21] Bistaffa F, Farinelli A, Cerquides J, et al. Anytime coalition structure generation on synergy graphs. In: Proceedings of the 2014 International Conference on Autonomous Agents and Multi-agent Systems(AAMAS). 2014: 13-20.
[22] 刘惊雷，张 伟，童向荣. 最优联盟结构生成算法中的分支限界技术. 北京交通大学学报, 2009, 6(11): 69-80.
{{custom_fnGroup.title_en}}
Footnotes
{{custom_fn.content}}
PDF(2514810 KB)
