An Anytime Algorithm for Optimal Coalition Structure Generation
Authors: Talal Rahwan, Sarvapali Dyanand Ramchurn, Nicholas Robert Jennings, Andrea Giovannucci
Date: 2014-01-15 00:00:00

Coalition formation is a fundamental type of interaction that involves the
creation of coherent groupings of distinct, autonomous, agents in order to
efficiently achieve their individual or collective goals. Forming effective
coalitions is a major research challenge in the field of multi-agent systems.
Central to this endeavour is the problem of determining which of the many
possible coalitions to form in order to achieve some goal. This usually
requires calculating a value for every possible coalition, known as the
coalition value, which indicates how beneficial that coalition would be if it
was formed. Once these values are calculated, the agents usually need to find a
combination of coalitions, in which every agent belongs to exactly one
coalition, and by which the overall outcome of the system is maximized.
However, this coalition structure generation problem is extremely challenging
due to the number of possible solutions that need to be examined, which grows
exponentially with the number of agents involved. To date, therefore, many
algorithms have been proposed to solve this problem using different techniques
ranging from dynamic programming, to integer programming, to stochastic search
all of which suffer from major limitations relating to execution time, solution
quality, and memory requirements.
  With this in mind, we develop an anytime algorithm to solve the coalition
structure generation problem. Specifically, the algorithm uses a novel
representation of the search space, which partitions the space of possible
solutions into sub-spaces such that it is possible to compute upper and lower
bounds on the values of the best coalition structures in them. These bounds are
then used to identify the sub-spaces that have no potential of containing the
optimal solution so that they can be pruned. The algorithm, then, searches
through the remaining sub-spaces very efficiently using a branch-and-bound
technique to avoid examining all the solutions within the searched subspace(s).
In this setting, we prove that our algorithm enumerates all coalition
structures efficiently by avoiding redundant and invalid solutions
automatically. Moreover, in order to effectively test our algorithm we develop
a new type of input distribution which allows us to generate more reliable
benchmarks compared to the input distributions previously used in the field.
Given this new distribution, we show that for 27 agents our algorithm is able
to find solutions that are optimal in 0.175% of the time required by the
fastest available algorithm in the literature. The algorithm is anytime, and if
interrupted before it would have normally terminated, it can still provide a
solution that is guaranteed to be within a bound from the optimal one.
Moreover, the guarantees we provide on the quality of the solution are
significantly better than those provided by the previous state of the art
algorithms designed for this purpose. For example, for the worst case
distribution given 25 agents, our algorithm is able to find a 90% efficient
solution in around 10% of time it takes to find the optimal solution.