A Coalition Structure Generation Algorithm based on Partition Cardinality Structure
Coalition formation is a key topic on multiagent systems. As the number of coalition structures is large, it is not allowed to search the whole coalition structure tree exhaustively. So, a partial search which is guaranteed to be within a bound from optimum is interested. A large number of previous work has been done to find the optimal coalition structure in Characteristic Function Games (CFGs), where the value of a coalition was independent from co-existing coalitions in the system. However, usually it is not appropriate to the real situation because an agents effectiveness may change from one coalition structure to another. Thus, much more general Partition Function Games (PFGs) have to be applied. In this context, we develop an algorithm based on partition cardinality structure, which consider the coalition value in PFGs. We use different strategies in two classes of PFGs, and improve the bound with further search.
Multi-agent System coalition structure generation partition function games partition cardinality structure
Hai-Yan WU Shan-Li HU
College of Mathematics and Computer Science Fujian Normal University Fuzhou, China Department of Computer Science and Technology Fuzhou University Fuzhou, China
国际会议
厦门
英文
75-78
2010-10-29（万方平台首次上网日期，不代表论文的发表时间）