Generating coalition structures with finite bound from the optimal guarantees
OA Location
Author(s)
Dang, VD
Jennings, NR
Type
Conference Paper
Abstract
The coalition formation process, in which a number of independent, autonomous agents come together to act as a collective, is an important form of interaction in multi-agent systems. When effective, such coalitions can improve the performance of the individual agents and/or of the system as a whole. However, one of the main problems that hinders the widespread adoption of coalition formation technologies is the computational complexity of coalition structure generation. That is, once a group of agents has been identified, how can it be partitioned in order to maximize the social payoff? This problem has been shown to be NP-hard and even finding a sub-optimal solution requires searching an exponential number of solutions. Against this background, this paper reports on a novel anytime algorithm for coalition structure generation that produces solutions that are within a finite bound from the optimal. Our algorithm is benchmarked against Sandholm et al’s algorithm [8] (the only other known algorithm for this task that can also establish a worst-case bound from the optimal) and is shown to be up to 10379 times faster (for systems containing 1000 agents) when small bounds from the optimal are desirable.
Date Issued
2004
Citation
2004, pp.564-571
Start Page
564
End Page
571
Identifier
http://eprints.soton.ac.uk/259550/
Source
3rd International Conference on Autonomous Agents and Multi-Agent Systems
Notes
Event Dates: 2004
Publication Status
Unpublished