Efficient Size-based Hybrid Algorithm for Optimal Coalition Structure Generation

Redha Taguelmimt (Univ Lyon, UCBL, CNRS, INSA Lyon, Centrale Lyon, Univ Lyon 2, LIRIS, UMR5205), Samir Aknine (Univ Lyon, UCBL, CNRS, INSA Lyon, Centrale Lyon, Univ Lyon 2, LIRIS, UMR5205), Djamila Boukredera (Faculty of Exact Sciences, Laboratory of Applied Mathematics, University of Bejaia), Narayan Changder (TCG Centres for Research and Education in Science and Technology), Tuomas Sandholm (Carnegie Mellon University, Strategic Machine, Inc., Strategy Robot, Inc., & Optimized Markets, Inc.)

Abstract

Coalition Structure Generation (CSG) involves dividing agents into coalitions in such a way as to coordinate them into solving problems together efficiently. In this paper, we revisit the CSG problem and propose a new search method that introduces an offline phase to speed up the search process, where the best coalition sets to search are preprocessed. These sets are calculated only once regardless of the coalition values and can be reused each time a CSG instance is to be solved. Then our search in the online phase combines dynamic programming with integer partition-based search in a novel way.