03 Julio 2007
University of Southampton
Talal Rahwan

Forming effective coalitions is a major research challenge in the field of multi-agent systems. Central to this endeavour is the problem of determining which of the possible coalitions to form in order to achieve some goal. Specifically, given the value (i.e. weight) of every possible coalition (i.e. subset of agents), our problem is to find an optimal coalition structure (i.e. partition of the set of agents). This is similar to the set partitioning problem, where every possible subset is included in the input. It is the size of the search space, which grows exponentially with the number of agents, that makes this problem extremely challenging. Even the lowest complexity algorithm in the literature cannot return solutions in reasonable time. Given this, we developed an algorithm that significantly outperforms existing algorithms. Specifically, we empirically show that we can find an optimal solution in 0.082% of the time required by the fastest algorithm in the literature (for 27 agents), and that is using only 33% of the memory required by that algorithm. These improvements become exponentially better given larger numbers of agents.

Institution department: 
School of Electronics and Computer Science