Model and Application of Optimal Coalition Structure

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. What kind of appearance the space of coalition structure is, there is few man to research it. This paper take the space of coalition structure as a coalition structure graph, give four properties of OCS (optimal coalition structure) model: optimal substructure, overlapping subproblems, minimal searching set, redundancy paths to OCS, using these properties, we devise an efficient dynamic programming (EDP) algorithm that perform fewer operations than DP (dynamic programming), because it need not evaluate the splits of coalition whose size is greater ¿2n/3¿. Finally, we prove that upper bound of EDP time complexity is O(3ⁿ). Experiment analysis shows the validity of the proposed algorithm, because it performs fewer operations which save 42% time than DP (given 21 agents).