Efficient Size-based Hybrid Algorithm for Optimal Coalition Structure Generation

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.

Authors

• Redha Taguelmimt Clermont Auvergne University, Clermont Auvergne INP, CNRS, LIMOS, F-63000 Clermont-Ferrand, France.
• Samir Aknine Univ Lyon, UCBL, CNRS, INSA Lyon, Centrale Lyon, Univ Lyon 2, LIRIS, UMR5205, Lyon, France
• Djamila Boukredera Laboratory of Applied Mathematics, Faculty of Exact Sciences, University of Bejaia, Bejaia, Algeria
• Narayan Changder TCG Centres for Research and Education in Science and Technology, Kolkata, India
• Tuomas Sandholm Carnegie Mellon University, Computer Science Department, Pittsburgh, USA Strategy Robot, Inc. Strategic Machine, Inc. Optimized Markets, Inc.

Keywords

• Coalition formation
• Coalition structure generation
• Preprocessing
• Integer partition graph