Coalition Structure Generation with Worst-Case Finite Bound from the Optimal Guarantees

Coalition formation is a key topic in multi-agent systems. However, finding the optimal coalition structure is NP-complete. Sandholm et al. show that it is 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 a further search after the lowest two levels of the coalition structure graph is a problem which hasn't been resolved for a long time. Dang et al. have presented an algorithm: for the odd bound k≥3, those coalition structures are further searched whose biggest coalition's cardinality is not less than n(k-1)/(k+1), which is the first algorithm known whose searching unit is not level and it is obviously faster than that of Sandholm et al for the smaller bound. The authors analyze the relations among coalition structures deeply and present an algorithm that only needs to search those coalition structures whose biggest coalition's cardinality is equal to n(k-1)/(k+1) to decrease largely the number of coalition structures needed to be searched. Moreover, the algorithm is improved to search skillfully those corresponding levels whose coalition structures are fewer than some of those coalition structures whose biggest coalition's cardinality is equal to n(k-1)/(k+1), therefore decreasing further the number of coalition structures needed to be searched and improving largely the work of Sandholm et al. and Dang et al.