An Anytime Coalition Structure Generation Based on the Grouping Idea of Cardinality Structure

Coalition formation is a key topic in multi-agent system. However, finding the optimal coalition structure is NP-complete. Sandholm and Larson et al. showed that it was necessary and sufficient to search the lowest two levels of the coalition structure graph in order to establish a worst-case bound k. How to do further search after the lowest two levels of the coalition structure graph is a problem which hasnt been resolved well for a long time. In actual problem such as task assignment, the different coalitions have the characteristics of the same cardinality and same value, or the value of two coalitions with the same cardinality differs a bit. This paper studies the problem about the optimal cardinality structure generation, analyzes the grouping thought of cardinality structures and presents a new anytime algorithm of coalition structure generation. The algorithm gives further search that can decrease bound to 2. After the minimal search, the complement search from the bottom to top in the process is also discussed that declines bound from 2 to 1. It is obviously better than Sandholm et al. and Dang et al. s in the searching number of cardinality structure and coalition structure, or attaining bound, which is a important progress in the problem of coalition structure generation based on cardinality structure.