TY - GEN

T1 - An Improved Dynamic Programming algorithm for coalition structure generation

AU - Rahwan, Talal

AU - Jennings, Nicholas R.

PY - 2008

Y1 - 2008

N2 - Forming effective coalitions is a major research challenge in the field of multi-agent systems. Central to this endeavour is the problem of partitioning the set of agents into exhaustive and disjoint coalitions such that the social welfare is maximized. This coalition structure generation problem is extremely challenging due to the exponential number of partitions that need to be examined. Specifically, given n agents, there are O(nn) possible partitions. To date, the only algorithm that can find an optimal solution in O(3n) is the Dynamic Programming (DP) algorithm, due to Rothkopf et al. However, one of the main limitations of DP is that it requires a significant amount of memory. In this paper, we devise an Improved Dynamic Programming algorithm (IDP) that is proved to perform fewer operations than DP (e.g. 38.7% of the operations given 25 agents), and is shown to use only 33.3% of the memory in the best case, and 66.6% in the worst.

AB - Forming effective coalitions is a major research challenge in the field of multi-agent systems. Central to this endeavour is the problem of partitioning the set of agents into exhaustive and disjoint coalitions such that the social welfare is maximized. This coalition structure generation problem is extremely challenging due to the exponential number of partitions that need to be examined. Specifically, given n agents, there are O(nn) possible partitions. To date, the only algorithm that can find an optimal solution in O(3n) is the Dynamic Programming (DP) algorithm, due to Rothkopf et al. However, one of the main limitations of DP is that it requires a significant amount of memory. In this paper, we devise an Improved Dynamic Programming algorithm (IDP) that is proved to perform fewer operations than DP (e.g. 38.7% of the operations given 25 agents), and is shown to use only 33.3% of the memory in the best case, and 66.6% in the worst.

UR - http://www.scopus.com/inward/record.url?scp=84899951120&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84899951120&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:84899951120

SN - 9781605604701

T3 - Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS

SP - 1385

EP - 1388

BT - 7th International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS 2008

PB - International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS)

T2 - 7th International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS 2008

Y2 - 12 May 2008 through 16 May 2008

ER -