@article {55909, title = {Algorithms for Graph-Constrained Coalition Formation in the Real World}, journal = {ACM Transactions on Intelligent Systems}, volume = {8}, year = {2017}, pages = {1-24}, publisher = {ACM}, abstract = { 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). }, doi = {10.1145/3040967}, url = {https://dl.acm.org/citation.cfm?doid=3055535.3040967}, author = {Filippo Bistaffa and Alessandro Farinelli and Juan A. Rodr{\'\i}guez-Aguilar and Jes{\'u}s Cerquides and Sarvapali D. Ramchurn} }