TY  - INPR
ID  - orchid5
UR  - http://www.orchid.ac.uk/eprints/5/
A1  - Rahwan, Talal
A1  - Michalak, Tomasz
A1  - Jennings, Nicholas R
Y1  - 2011///
N2  - 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 ? 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 ? = dn=2e. Nevertheless,
the question remained open for other values of
?. In this paper
TI  - Minimum Search To EstablishWorst-Case Guarantees
in Coalition Structure Generation
SP  - 338
M2  - Barcelona, Spain
AV  - public
EP  - 343
T2  - IJCAI 11
ER  -