A distributed algorithm for anytime coalition structure generation

Tomasz Michalak, Jacek Sroka, Talal Rahwan, Michael Wooldridge, Peter McBurney, Nicholas R. Jennings

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

A major research challenge in multi-agent systems is the problem of partitioning a set of agents into mutually disjoint coalitions, such that the overall performance of the system is optimized. This problem is difficult because the search space is very large: the number of possible coalition structures increases exponentially with the number of agents. Although several algorithms have been proposed to tackle this Coalition Structure Generation (CSG) problem, all of them suffer from being inherently centralized, which leads 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 distributed among the agents, instead of being carried out centrally by a single agent (as is the case in all the available algorithms in the literature). In this way, the search can be carried out in a much faster and more robust way, and the agents can share the burden of the calculations. The algorithm combines, and improves upon, techniques from two existing algorithms in the literature, namely DCVC [5] and IP [9], and applies novel techniques for filtering the input and reducing the inter-agent communication load.

Original languageEnglish (US)
Title of host publication9th International Joint Conference on Autonomous Agents and Multiagent Systems 2010, AAMAS 2010
PublisherInternational Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS)
Pages1007-1014
Number of pages8
ISBN (Print)9781617387715
StatePublished - 2010
Event9th International Joint Conference on Autonomous Agents and Multiagent Systems 2010, AAMAS 2010 - Toronto, ON, Canada
Duration: May 10 2010 → …

Publication series

NameProceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS
Volume2
ISSN (Print)1548-8403
ISSN (Electronic)1558-2914

Other

Other9th International Joint Conference on Autonomous Agents and Multiagent Systems 2010, AAMAS 2010
CountryCanada
CityToronto, ON
Period5/10/10 → …

Keywords

  • Algorithm Design
  • Coalition Formation
  • Distributed AI

ASJC Scopus subject areas

  • Artificial Intelligence

Fingerprint Dive into the research topics of 'A distributed algorithm for anytime coalition structure generation'. Together they form a unique fingerprint.

  • Cite this

    Michalak, T., Sroka, J., Rahwan, T., Wooldridge, M., McBurney, P., & Jennings, N. R. (2010). A distributed algorithm for anytime coalition structure generation. In 9th International Joint Conference on Autonomous Agents and Multiagent Systems 2010, AAMAS 2010 (pp. 1007-1014). (Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS; Vol. 2). International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS).