A Distributed Algorithm for Anytime Coalition Structure Generation

A major research challenge in multi-agent systems is theproblem of partitioning a set of agents into mutually disjoint coalitions, such that the overall performance of thesystem is optimized. This problem is difficult because thesearch space is very large: the number of possible coalition structures increases exponentially with the number ofagents. Although several algorithms have been proposed totackle this Coalition Structure Generation (CSG) problem, all of them suffer from being inherently centralized, whichleads to the existence of a performance bottleneck and a single point of failure. In this paper, we develop the first decentralized algorithm for solving the CSG problem optimally. In our algorithm, the necessary calculations are distributedamong the agents, instead of being carried out centrally bya single agent (as is the case in all the available algorithmsin the literature). In this way, the search can be carriedout in a much faster and more robust way, and the agentscan share the burden of the calculations. The algorithmcombines, and improves upon, techniques from two existingalgorithms in the literature, namely DCVC and IP, and applies novel techniques for filtering the input and reducing the inter-agent communication load.

Authors

• Tomasz Michalak University of Warsaw IDEAS NCBR
• Jacek Sroka University of Warsaw
• Talal Rahwan
• Michael Wooldridge University of Oxford
• Peter McBurney
• Nicholas R. Jennings

Keywords

No keywords are indexed for this paper.