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)
![[img]](../../style/images/fileicons/other.png)
|
PDF (Minimum Search To EstablishWorst-Case Guarantees in Coalition Structure Generation)
Download (290Kb) | Preview |
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
| Item Type: | Conference or Workshop Item (Paper) |
|---|---|
| Subjects: | Topics > Agent-based Computing Work Areas > Agile Teaming |
| Divisions: | University of Southampton |
| Depositing User: | Angela Westley |
| Date Deposited: | 10 Aug 2011 10:26 |
| Last Modified: | 17 Apr 2012 08:41 |
| URI: | http://www.orchid.ac.uk/eprints/id/eprint/5 |
Actions (login required)
 |
View Item |
