C-Link: A Hierarchical Clustering Approach to Large-scale Near-optimal Coalition Formation

Coalition formation is a fundamental approach tomulti-agent coordination. In this paper we addressthe specific problem of coalition structure gener-ation, and focus on providing good-enough solu-tions using a novel heuristic approach that is basedon data clustering methods. In particular, we pro-pose a hierarchical agglomerative clustering ap-proach (C-Link), which uses a similarity criterionbetween coalitions based on the gain that the sys-tem achieves if two coalitions merge. We empir-ically evaluate C-Link on a synthetic benchmarkdata-set as well as in collective energy purchasingsettings. Our results show that the C-link approachperforms very well against an optimal benchmarkbased on Mixed-Integer Programming, achievingsolutions which are in the worst case about 80%of the optimal (in the synthetic data-set), and 98%of the optimal (in the energy data-set). Thus weshow that C-Link can return solutions for problemsinvolving thousands of agents within minutes.