  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.
