title: Minimum Search To EstablishWorst-Case Guarantees  in Coalition Structure Generation
creator: Rahwan, Talal
creator: Michalak, Tomasz
creator: Jennings, Nicholas R
subject: Agent-based Computing
subject: Agile Teaming
description: 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
type: Conference or Workshop Item
type: PeerReviewed
format: application/pdf
identifier: http://www.orchid.ac.uk/eprints/5/1/Rahwan_Michalak_Jennings_1338_camera_ready.pdf
identifier:   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)  
relation: http://www.orchid.ac.uk/eprints/5/