Título | Algorithms for Graph-Constrained Coalition Formation in the Real World |
Publication Type | Journal Article |
Year of Publication | 2017 |
Authors | Bistaffa F, Farinelli A, Rodríguez-Aguilar JA, Cerquides J, Ramchurn SD |
Journal | ACM Transactions on Intelligent Systems |
Volume | 8 |
Incidencia | 4 |
Paginación | 1-24 |
Editorial | ACM |
Resumen | Coalition formation typically involves the coming together of multiple, heterogeneous, agents to achieve both their individual and collective goals. In this paper, 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 (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 non-redundant 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 4 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 2700 agents). |
URL | https://dl.acm.org/citation.cfm?doid=3055535.3040967 |
DOI | 10.1145/3040967 |