Generating coalition structures with finite bound from the optimal guarantees

The coalition formation process, in which a number of independent, autonomous agents come together to act as a collective, is an important form of interaction in multi-agent systems. When effective, such coalitions can improve the performance of the individual agents and/or of the system as a whole. However, one of the main problems that hinders the wide spread adoption of coalition formation technologies is the computational complexity of coalition structure generation. That is, once a group of agents has been identified, how can it be partitioned in order to maximise the social pay off? This problem has been shown to be NP-hard and even finding a sub-optimal solution requires searching an exponential number of solutions. Against this background, this paper reports on a novel anytime algorithm for coalition structure generation that produces solutions that are within a finite bound from the optimal. Our algorithm is benchmarked against Sandholm et al. s algorithm [8] (the only other known algorithm for this task that can also establish a worst-case bound from the optimal) and is shown to be up to 10379 times faster (for systems containing 1000 agents) when small bounds from the optimal are desirable