Por favor, use este identificador para citar o enlazar a este item:
http://hdl.handle.net/10261/154723
COMPARTIR / EXPORTAR:
SHARE CORE BASE | |
Visualizar otros formatos: MARC | Dublin Core | RDF | ORE | MODS | METS | DIDL | DATACITE | |
Título: | Algorithms for graph-constrained coalition formation in the real world |
Autor: | Bistaffa, Filippo CSIC ORCID ; Farinelli, Alessandro; Cerquides, Jesús CSIC ORCID ; Rodríguez-Aguilar, Juan Antonio CSIC ORCID CVN ; Ramchurn, Sarvapali | Palabras clave: | Collective energy purchasing: Graphs Coalition formation Networks |
Fecha de publicación: | 2017 | Editor: | Association for Computing Machinery | Citación: | ACM Transactions on Intelligent Systems and Technology 8 (4) Nº60 (2017) | Resumen: | Coalition formation typically involves the coming together of multiple, heterogeneous, agents to achieve both their individual and collective goals. In this article, we focus on a special case of coalition formation known as Graph-Constrained Coalition Formation (GCCF) whereby a network connecting the agents constrains the formation of coalitions. We focus on this type of problem given that in many real-world applications, agents may be connected by a communication network or only trust certain peers in their social network.We propose a novel representation of this problem based on the concept of edge contraction, which allows us to model the search space induced by the GCCF problem as a rooted tree. Then, we propose an anytime solution algorithm (Coalition Formation for Sparse Synergies (CFSS)), which is particularly efficient when applied to a general class of characteristic functions called m+ a functions. Moreover, we show how CFSS can be efficiently parallelised to solve GCCF using a nonredundant partition of the search space. We benchmark CFSS on both synthetic and realistic scenarios, using a real-world dataset consisting of the energy consumption of a large number of households in the UK. Our results show that, in the best case, the serial version of CFSS is four orders of magnitude faster than the state of the art, while the parallel version is 9.44 times faster than the serial version on a 12-core machine. Moreover, CFSS is the first approach to provide anytime approximate solutions with quality guarantees for very large systems of agents (i.e., with more than 2,700 agents). | URI: | http://hdl.handle.net/10261/154723 | DOI: | 10.1145/3040967 | Identificadores: | doi: 10.1145/3040967 e-issn: 2157-6912 issn: 2157-6904 |
Aparece en las colecciones: | (IIIA) Artículos |
Ficheros en este ítem:
Fichero | Descripción | Tamaño | Formato | |
---|---|---|---|---|
accesoRestringido.pdf | 15,38 kB | Adobe PDF | Visualizar/Abrir |
CORE Recommender
SCOPUSTM
Citations
16
checked on 17-abr-2024
WEB OF SCIENCETM
Citations
11
checked on 28-feb-2024
Page view(s)
314
checked on 23-abr-2024
Download(s)
82
checked on 23-abr-2024
Google ScholarTM
Check
Altmetric
Altmetric
NOTA: Los ítems de Digital.CSIC están protegidos por copyright, con todos los derechos reservados, a menos que se indique lo contrario.