creators_name: Rahwan, Talal
creators_name: Michalak, Tomasz
creators_name: Jennings, Nicholas R
type: conference_item
datestamp: 2011-08-10 10:26:18
lastmod: 2012-04-17 08:41:42
metadata_visibility: show
title: Minimum Search To EstablishWorst-Case Guarantees
in Coalition Structure Generation
ispublished: inpress
subjects: ABC
subjects: at
full_text_status: public
pres_type: 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 � 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
date: 2011
pagerange: 338-343
event_title: IJCAI 11
event_location: Barcelona, Spain
event_dates: July 16-22 2011
event_type: conference
refereed: TRUE
citation:   Rahwan, Talal and Michalak, Tomasz and Jennings, Nicholas R  (2011) Minimum Search To EstablishWorst-Case Guarantees in Coalition Structure Generation.  In: IJCAI 11, July 16-22 2011, Barcelona, Spain.    (In Press)  
document_url: http://www.orchid.ac.uk/eprints/5/1/Rahwan_Michalak_Jennings_1338_camera_ready.pdf