An Effective Dynamic Programming Algorithm for Optimal Coalition Structure Generation

Coalition formation is one of the most studied topics in multi-agent systems. Central to this endeavor is the problem of partitioning the set of agents into exhaustive and disjoint coalitions so as to maximize social welfare. The coalition structure generation problem is challenging due to the fact that it needs to explore an exponential number of partitions. The fastest exact algorithm to solve this combinatorial optimization problem is ODP-IP [1], which is a hybrid version of two previously established algorithms, namely IDP (Improved Dynamic Programming [2] and IP [3]. Given this, it is desirable to come up with a new algorithm which could build on the same principles as IDP follows and which in turn, improves upon the state. In this paper, we propose a new algorithm EDP (Effective Dynamic Programming). This algorithm is a new design paradigm for this difficult problem. Both EDP and IDP have been implemented and tested on well-known data distribution. We prove that EDP is practically faster than IDP.