Coalition structure generation: Dynamic programming meets anytime optimisation

Coalition structure generation involves partitioning a set of agents into exhaustive and disjoint coalitions so as to maximize the social welfare. What makes this such a challenging prob-lem is that the number of possible solutions grows exponen-tially as the number of agents increases. To date, two main ap-proaches have been developed to solve this problem, each with its own strengths and weaknesses. The state of the art in the first approach is the Improved Dynamic Programming (IDP) al-gorithm, due to Rahwan and Jennings, that is guaranteed to find an optimal solution in O(3n), but which cannot generate a so-lution until it has completed its entire execution. The state of the art in the second approach is an anytime algorithm called IP, due to Rahwan et al., that provides worst-case guarantees on the quality of the best solution found so far, but which is O(nn). In this paper, we develop a novel algorithm that com-bines both IDP and IP, resulting in a hybrid performance that exploits the strength of both algorithms and, at the same, avoids their main weaknesses. Our approach is also significantly faster (e.g. given 25 agents, it takes only 28 % of the time required by IP, and 0.3 % of the time required by IDP)