A Distributed Branch-and-Bound Algorithm for Computing Optimal Coalition Structures

Coalition formation is an important area of research in multi-agent systems. Computing optimal coalition structures for a large number of agents is an important problem in coalition formation but has received little attention in the literature. Previous studies assume that each coalition value is known a priori. This assumption is impractical in real world settings. Furthermore, the problem of finding coalition values become intractable for even a relatively small number of agents. This work proposes a distributed branch-and-bound algorithm for computing optimal coalition structures in linear production domain, where each coalition value is not known a priori. The common goal of the agents is to maximize the system’s profit. In our algorithm, agents perform two tasks:

i

) deliberate profitable coalitions, and

ii

) cooperatively compute optimal coalition structures. We show that our algorithm outperforms exhaustive search in generating optimal coalition structure in terms of elapses time and number of coalition structures generated.