An Anytime Coalition Structure Generation Algorithm Based on Cardinality Structure

Coalition formation is a key topic in multi-agent systems. One may prefer a coalition structure that maximizes the sum of the values of the coalitions, but often the number of coalition structures is too large to allow exhaustive search for the optimal one. Furthermore, finding the optimal coalition structure is NP-hard and even finding a sub-optimal solution requires searching an exponential number of solutions. But then, can the coalition structure found via a partial search be guaranteed to be within a bound from optimum? Sandholm et al. show that it suffices to search the lowest two levels of the coalition structure graph in order to establish a worst-case bound K(n). Dang et al. present an algorithm which is obviously faster than that of Sandholm et al, which is the best result known so far. Against this background, the relations among coalition structures are analyzed in depth and a novel anytime algorithm based on cardinality structure is presented, which only has to take a step further and search those coalition structures whose cardinality structure is in the CCS (n, b). Consequently, the algorithms reported are obviously better than that of Sandholm et al. (up to 10\+\35\ times faster when n=100, K=2) and Dang et al.( up to 10\+\18\ times faster when n=100, K=3).