English   español  
Please use this identifier to cite or link to this item: http://hdl.handle.net/10261/132415
Share/Impact:
Statistics
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:
Title

Anytime coalition structure generation on synergy graphs

AuthorsBistaffa, Filippo ; Farinelli, Alessandro; Cerquides, Jesús ; Rodríguez-Aguilar, Juan Antonio ; Ramchurn, Sarvapali
KeywordsNetworks
Graphs
Collective energy purchasing
Coalition formation
Issue Date5-May-2014
CitationProceedings of the 13th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2014; Paris; France; 5 May 2014 through 9 May 2014. Vol. 1, 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 paralleli-sation. 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). Copyright © 2014, International Foundation for Autonomous Agents and Multiagent Systems (www.ifaamas.org). All rights reserved.
URIhttp://hdl.handle.net/10261/132415
Identifiersisbn: 978-163439131-3
Appears in Collections:(IIIA) Comunicaciones congresos
Files in This Item:
File Description SizeFormat 
PROC_AAMAS2014_13-20.null639,27 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.