Improving coalition structure search with an imperfect algorithm: analysis and evaluation results

Optimal Coalition Structure Generation (CSG) is a significant research problem in multi-agent systems that remains difficult to solve. This problem has many important applications in transportation, eCommerce, distributed sensor networks and others. The CSG problem is NP-complete and finding the optimal result for n agents needs to check O(n(n)) possible partitions. The ODP-IP algorithm (Michalak et al. in Artif Intell 230:14-50, 2016) achieves the current lowest worst-case time complexity of O(3(n)). In the light of its high computational time complexity, we devise an Imperfect Dynamic Programming (ImDP) algorithm for the CSG problem with runtime O(n2(n)) given n agents. Imperfect algorithm means that there are some contrived inputs for which the algorithm fails to give the optimal result. We benchmarked ImDP against ODP-IP and proved its efficiency. Experimental results confirmed that ImDP algorithm performance is better for several data distributions, and for some it improves dramatically ODP-IP. For example, given 27 agents, with ImDP for agent-based uniform distribution time gain is 91% (i.e. 49 min).