Anytime Optimal Coalition Structure Generation

Talal Rahwan, Sarvapali Ramchurn, Viet D. Dang, Andrea Giovannucci, Nicholas R. Jennings

A key problem when forming effective coalitions of autonomous agents is determining the best groupings, or the optimal coalition structure, to select to achieve some goal. To this end, we present a novel, anytime algorithm for this task that is significantly faster than current solutions. Specifically, we empirically show that we are able to find solutions that are optimal in 0.082 % of the time taken by the state of the art dynamic programming algorithm (for 27 agents), using much less memory (O(2^n) instead of O(3^n) for n agents). Moreover, our algorithm is the first to be able to find solutions for more than 17 agents in reasonable time (less than 90 minutes for 27 agents, as opposed to around 2 months for the best previous solution).

Subjects: 7.1 Multi-Agent Systems; 15.7 Search

Submitted: Apr 24, 2007

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.