Properties and Application of Coalition Structure Graph

Forming effective coalitions is a major research challenge in the field of multi-agent systems. The coalition structure generation problem is extremely challenging due to the exponential number of partitions that need to be examined. But what kind of appearance the space of coalition structure is, there is few people to research on it, particularly its graph properties. Optimal coalition structure generation problem is discussed from the viewpoint of graph theory. Firstly, the space of coalition structure is taken as a coalition structure graph, the vertex in which stands for coalition structure, the edge in which stands for splitting of coalition structure. Soon after two graph properties: optimal substructure, overlapping sub-structure, are summed up, one property: the key searching set is extended, and a new graph property: connectivity of graph with few redundancy paths is given. In order to understand and apply these properties, we devise an effective dynamic programming (EDP) algorithm to search the optimal coalition structure. In addition, we prove that the lower bound of EDP is Ω(21/+n), and the upper bound is O(3/+n) in theory. Finally, empirical evaluation shows that the searching number of EDP algorithm is lower 42% than those of DP, when involving 21 agents.