creators_name: Rahwan, Talal
creators_name: Michalak, Tomasz
creators_name: Elkind, Edith
creators_name: Faliszewski, Piotr
creators_name: Sroka, Jacek
creators_name: Wooldridge, Michael
creators_name: Jennings, Nicholas R
type: conference_item
datestamp: 2011-08-10 10:26:04
lastmod: 2012-04-17 08:42:16
metadata_visibility: show
title: Constrained Coalition Formation
ispublished: inpress
subjects: ABC
subjects: at
full_text_status: public
pres_type: paper
abstract: The conventional model of coalition formation considers every
possible subset of agents as a potential coalition. However,
in many real-world applications, there are inherent constraints
on feasible coalitions: for instance, certain agents
may be prohibited from being in the same coalition, or the
coalition structure may be required to consist of coalitions of
the same size. In this paper, we present the first systematic
study of constrained coalition formation (CCF). We propose
a general framework for this problem, and identify an important
class of CCF settings, where the constraints specify
which groups of agents should/should not work together. We
describe a procedure that transforms such constraints into a
structured input that allows coalition formation algorithms to
identify, without any redundant computations, all the feasible
coalitions. We then use this procedure to develop an algorithm
for generating an optimal (welfare-maximizing) constrained
coalition structure, and show that it outperforms existing
state-of-the-art approaches by several orders of magnitude.
date: 2011
pagerange: 719-725
event_title: Proc. 25th Conference on AI (AAAI)
event_location: San Francisco, USA 
event_dates: 7-11 August 2011
event_type: conference
refereed: TRUE
citation:   Rahwan, Talal and Michalak, Tomasz and Elkind, Edith and Faliszewski, Piotr and Sroka, Jacek and Wooldridge, Michael and Jennings, Nicholas R  (2011) Constrained Coalition Formation.  In: Proc. 25th Conference on AI (AAAI), 7-11 August 2011, San Francisco, USA .    (In Press)  
document_url: http://www.orchid.ac.uk/eprints/6/1/Constrained_Coalition_Formation.pdf