Randomized coalition structure generation Original Research Article

Randomization can be employed to achieve constant factor approximations to the coalition structure generation problem in less time than all previous approximation algorithms. In particular, this manuscript presents a new randomized algorithm that can generate a image approximate solution in image time, improving upon the previous algorithm that required image time to guarantee the same performance. Also, the presented new techniques allow a image approximate solution to be generated in the optimal time of image and improves on the previous best approximation ratio obtainable in image time of image. The presented algorithms are based upon a careful analysis of the sizes and numbers of coalitions in the smallest optimal coalition structures. An empirical analysis of the new randomized algorithms compared to their deterministic counterparts is provided. We find that the presented randomized algorithms generate solutions with utility comparable to what is returned by their deterministic counterparts (in some cases producing better results on average). Moreover, a significant speedup was found for most approximation ratios for the randomized algorithms over the deterministic algorithms. In particular, the randomized image approximate algorithm runs in approximately image of the time required for the deterministic image approximation algorithm for problems with between 20 and 27 agents.