Coalition structure generation in multi-agent systems with positive and negative externalities

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

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

Abstract

Coalition structure generation has received considerable attention in recent research. Several algorithms have been proposed to solve this problem in Characteristic Function Games (CFGs), where every coalition is assumed to perform equally well in any coalition structure containing it. In contrast, very little attention has been given to the more general Partition Function Games (PFGs), where a coalition's effectiveness may change from one coalition structure to another. In this paper, we deal with PFGs with positive and negative externalities. In this context, we identify the minimum search that is required in order to establish a bound on the quality of the best coalition structure found. We then develop an anytime algorithm that improves this bound with further search, and show that it outperforms the existing state-of-the-art algorithms by orders of magnitude.

Original languageEnglish (US)
Title of host publicationIJCAI-09 - Proceedings of the 21st International Joint Conference on Artificial Intelligence
PublisherInternational Joint Conferences on Artificial Intelligence
Pages257-263
Number of pages7
ISBN (Print)9781577354260
StatePublished - 2009
Event21st International Joint Conference on Artificial Intelligence, IJCAI 2009 - Pasadena, United States
Duration: Jul 11 2009Jul 16 2009

Publication series

NameIJCAI International Joint Conference on Artificial Intelligence
ISSN (Print)1045-0823

Conference

Conference21st International Joint Conference on Artificial Intelligence, IJCAI 2009
CountryUnited States
CityPasadena
Period7/11/097/16/09

ASJC Scopus subject areas

  • Artificial Intelligence

Fingerprint Dive into the research topics of 'Coalition structure generation in multi-agent systems with positive and negative externalities'. Together they form a unique fingerprint.

Cite this