Abstract:

Coalition structure is a partition of the agent set, forming a coalition structure by coalition can make agents cooperate effectively and fulfill the tasks that a single agent can not. In this paper, we propose a BIDP (Bipartite of Integer Dynamic Programming) algorithm to solve the optimal coalition structure generation, which adopts the bipartite of integer to generate bipartite partitions, and takes the bound of integer bipartite as the bound of the search space. And a theoretical analysis proves that BIDP can save 33.3% memory in any case than DP (Dynamic Programming). An experiment analysis shows that BIDP can save 35% and 92% searching numbers on 21 agents when the coalition values meet the uniform distribution and normal distribution. Finally,the paper gives a verdict that the time complexity of the determinant algorithm to solve OCS is between Ω(2n) and O(3n), and the space complexity is Θ(2n).

Key words: optimal coalition structure, BIDP algorithm, bipartite of integer, bipartite partition, time and space complexity