A Synergy Coalition Group based Dynamic Programming Algorithm for Coalition Formation

Coalition formation in characteristic function games entails agents partitioning themselves into a coalition structure and assigning the numeric rewards of each coalition via a payoff vector. Various coalition structure generation algorithms have been proposed that guarantee that an optimal coalition structure is found. We present the Synergy Coalition Group-based Dynamic Programming (SCGDP) algorithm that guarantees that an optimal coalition structure and a least core stable payoff vector is found. This is completed by extending the existing results for the Synergy Coalition Group (SCG) representation to show that only coalitions in the SCG are needed to find a weak-least core stable payoff vector. The SCGDP algorithm builds on this result by performing only the search operations necessary to guarantee that coalitions in the SCG of the given characteristic function game are found. The number of operations required is significantly less for many coalition-value distributions compared to the original Dynamic Programming (DP) algorithm [34] that finds an optimal coalition structure (e.g. only ~60% of DP's coalition lookup operations are performed in SCGDP for 18 agents using a normal coalition-value distribution). Our experimental results show that a lower bound for these operations in SCG-DP converges onto 50%. This is an increase on the ~33% bound of the optimal dynamic programming (ODP) algorithm [14], but ODP does not search for a stable solution.