A hierarchical clustering approach to large-scale near-optimal coalition formation with quality guarantees

Coalition formation is a fundamental approach to multi-agent coordination, and a key challenge in this context is the coalition structure generation problem, where a set of agents must be partitioned into the best set of coalitions. This problem is NP-hard and typical optimal algorithms do not scale to more than 50 agents: efficient approximate solutions are therefore needed for hundreds or thousands of agents. In this paper we propose a novel heuristic, based on ideas and tools used in the data clustering domain. In particular, we present a coalition formation algorithm inspired by the well known class of hierarchical agglomerative clustering techniques (Linkage algorithms). We present different variants of the algorithm, which we call Coalition Linkage (C-Link) and demonstrate how such algorithm can be adapted to graph restricted coalition formation problems (where an interaction graph defined among the agents restricts the set of feasible coalitions). Moreover, we discuss how we can provide an upper bound on the value of the optimal coalition structure, and we show that for specific characteristic functions we can provide such bounds while maintaining polynomial computational costs and memory requirements. We empirically evaluate the different variants of the C-Link algorithm on two synthetic benchmark data-sets, as well as in two real world scenarios, involving a collective energy purchasing and a ride-sharing application. In these settings C-Link achieves promising results providing high quality solutions and solving problem involving thousands of agents in few minutes.