A hierarchical clustering approach to large-scale near-optimal coalition formation with quality guarantees. (March 2017)

• Record Type: Journal Article
• Authors: Farinelli, Alessandro; Bicego, Manuele; Bistaffa, Filippo; Ramchurn, Sarvapali D.
• Is Part Of: Engineering applications of artificial intelligence. Volume 59(2016:Nov.)
• Page Start: 170
• Page End: 185
• Publication Date: 2017-03
• Subjects: Coalition formation -- Large scale systems -- Collective energy purchasing -- Ride-sharing -- Hierarchical clustering; Engineering -- Data processing -- Periodicals; Artificial intelligence -- Periodicals; Expert systems (Computer science) -- Periodicals; Ingénierie -- Informatique -- Périodiques; Intelligence artificielle -- Périodiques; Systèmes experts (Informatique) -- Périodiques; Artificial intelligence; Engineering -- Data processing; Expert systems (Computer science); Periodicals; 620.00285
• DOI: 10.1016/j.engappai.2016.12.018
• Languages: English
• ISSNs: 0952-1976

Abstract

Abstract: 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. Abstract : Highlights: An heuristic approach to coalition structure generation based on data clustering. Designed for large scale systems (i.e., thousands of agents). Evaluated in realistic scenarios (collective energy and ride-sharing) Provide quality guarantees for specific characteristic functions.