Minimum search to establish worst-case guarantees in coalition structure generation
OA Location
Author(s)
Rahwan, T
Michalak, T
Jennings, NR
Type
Conference Paper
Abstract
Coalition formation is a fundamental research topic in multi-agent systems. In this context, while it is desirable to generate a coalition structure that maximizes the sum of the values of the coalitions, the space of possible solutions is often too large to allow exhaustive search. Thus, a fundamental open question in this area is the following: Can we search through only a subset of coalition structures, and be guaranteed to find a solution that is within a desirable bound (beta) from optimum? If so, what is the minimum such subset? To date, the above question has only been partially answered by Sandholm et al. in their seminal work on anytime coalition structure generation [Sandholm et al., 1999]. More specifically, they identified minimum subsets to be searched for two particular bounds: ? = n and ? = [n/2]. Nevertheless, the question remained open for other values of ?. In this paper, we provide the complete answer to this question.
Date Issued
2011-07-16
Date Acceptance
2011-07-16
Citation
Proceedings of the Twenty-Second international joint conference on Artificial Intelligence (IJCAI '11), 2011, pp.338-343
ISBN
978-1-57735-513-7
Publisher
AAAI Press
Start Page
338
End Page
343
Journal / Book Title
Proceedings of the Twenty-Second international joint conference on Artificial Intelligence (IJCAI '11)
Copyright Statement
© 2011AAAI Press
Identifier
http://eprints.soton.ac.uk/272270/
Source
Twenty-Second international joint conference on Artificial Intelligence (IJCAI '11)
Publication Status
Published
Start Date
2011-07-16
Finish Date
2011-07-22
Coverage Spatial
Barcelona, Spain