Faster Optimal Coalition Structure Generation via Offline Coalition Selection and Graph-Based Search
This work addresses a long-standing challenge in multi-agent systems for researchers and practitioners, offering incremental improvements in computational efficiency for coalition formation.
The paper tackles the coalition structure generation problem in multi-agent systems by introducing the SMART algorithm, which combines dynamic programming, offline coalition selection, and graph-based search to achieve faster optimal solutions than prior methods like ODP-IP and BOSS across various value distributions.
Coalition formation is a key capability in multi-agent systems. An important problem in coalition formation is coalition structure generation: partitioning agents into coalitions to optimize the social welfare. This is a challenging problem that has been the subject of active research for the past three decades. In this paper, we present a novel algorithm, SMART, for the problem based on a hybridization of three innovative techniques. Two of these techniques are based on dynamic programming, where we show a powerful connection between the coalitions selected for evaluation and the performance of the algorithms. These algorithms use offline phases to optimize the choice of coalitions to evaluate. The third one uses branch-and-bound and integer partition graph search to explore the solution space. Our techniques bring a new way of approaching the problem and a new level of precision to the field. In experiments over several common value distributions, we show that the hybridization of these techniques in SMART is faster than the fastest prior algorithms (ODP-IP, BOSS) in generating optimal solutions across all the value distributions.