An improved dynamic programming algorithm for coalition structure generation

ABSTRACT

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(nⁿ) possible partitions. To date, the only algorithm that can find an optimal solution in O(3ⁿ) 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.

REFERENCES

• 1: Viet Dung Dang , Nicholas R. Jennings, Generating Coalition Structures with Finite Bound from the Optimal Guarantees, Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems, p.564-571, July 19-23, 2004, New York, New York [doi>10.1109/AAMAS.2004.132]
• 2: T. Rahwan, S. D. Ramchurn, A. Giovannucci, V. D. Dang, and N. R. Jennings. Anytime optimal coalition structure generation. In AAAI-07, pages 1184--1190, 2007.
• 3: Michael H. Rothkopf , Aleksandar Pekec , Ronald M. Harstad, Computationally Manageable Combinational Auctions, Management Science, v.44 n.8, p.1131-1147, August 1998 [doi>10.1287/mnsc.44.8.1131]
• 4: Tuomas Sandholm , Kate Larson , Martin Andersson , Onn Shehory , Fernando Tohmé, Coalition structure generation with worst case guarantees, Artificial Intelligence, v.111 n.1-2, p.209-238, July 1999 [doi>10.1016/S0004-3702(99)00036-3]
• 5: Tuomas W. Sandholm , Victor R. Lesser, Coalitions among computationally bounded agents, Artificial Intelligence, v.94 n.1-2, p.99-137, July 1997 [doi>10.1016/S0004-3702(97)00030-1]
• 6: Searching for Optimal Coalition Structures, Proceedings of the Fourth International Conference on MultiAgent Systems (ICMAS-2000), p.287, July 10-12, 2000
• 7: Onn Shehory , Sarit Kraus, Methods for task allocation via agent coalition formation, Artificial Intelligence, v.101 n.1-2, p.165-200, May 1998 [doi>10.1016/S0004-3702(98)00045-9]
• 8: D. Yun Yeh, A dynamic programming approach to the complete set partitioning problem, BIT, v.26 n.4, p.467-474, Jan. 1986 [doi>10.1007/BF01935053]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Dynamic programming

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.11 Distributed Artificial Intelligence
            Subjects: Coherence and coordination; Multiagent systems
  I.6 SIMULATION AND MODELING
      I.6.4 Model Validation and Analysis

General Terms:
Algorithms, Design, Management, Performance, Theory