English   español  
Please use this identifier to cite or link to this item: http://hdl.handle.net/10261/131204
logo share SHARE   Add this article to your Mendeley library MendeleyBASE
Visualizar otros formatos: MARC | Dublin Core | RDF | ORE | MODS | METS | DIDL
Exportar a otros formatos:

Anytime Coalition Structure Generation on Scale-Free and Community Networks

AuthorsBistaffa, Filippo ; Farinelli, Alessandro; Cerquides, Jesús ; Rodríguez-Aguilar, Juan Antonio ; Ramchurn, Sarvapali D.
KeywordsMulti-agent systems
Coalition formation
Issue Date5-May-2014
CitationAAMAS '14: Proceedings of the 13th international conference on autonomous agents and multi Agent Systems, Paris, France, pp. 13-20, 2014.
AbstractWe consider the coalition structure generation (CSG) problem on synergy graphs, which arises in many practical applications where communication constraints, social or trust relationships must be taken into account when forming coalitions. We propose a novel representation of this problem based on the concept of edge contraction, and an innovative branch and bound approach (CFSS), which is particularly efficient when applied to a general class of characteristic functions. This new model provides a non-redundant partition of the search space, hence allowing an effective parallelisation. We evaluate CFSS on two benchmark functions, the edge sum with coordination cost and the collective energy purchasing functions, comparing its performance with the best algorithm for CSG on synergy graphs: DyCE. The latter approach is centralised and cannot be efficiently parallelised due to the exponential memory requirements in the number of agents, which limits its scalability (while CFSS memory requirements are only polynomial). Our results show that, when the graphs are very sparse, CFSS is 4 orders of magnitude faster than DyCE. Moreover, CFSS is the first approach to provide anytime approximate solutions with quality guarantees for very large systems (i.e., with more than 2700 agents).
Identifiersuri: http://www.ifaamas.org/Proceedings/aamas2014/aamas/p13.pdf
Appears in Collections:(IIIA) Comunicaciones congresos
Files in This Item:
File Description SizeFormat 
AAMAS'14_13-20.null272,96 kBUnknownView/Open
Show full item record
Review this work

WARNING: Items in Digital.CSIC are protected by copyright, with all rights reserved, unless otherwise indicated.