TY - GEN
T1 - Constrained coalition formation
AU - Rahwan, Talal
AU - Michalak, Tomasz
AU - Elkind, Edith
AU - Faliszewski, Piotr
AU - Sroka, Jacek
AU - Wooldridge, Michael
AU - Jennings, Nicholas R.
PY - 2011
Y1 - 2011
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=80055047947&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=80055047947&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:80055047947
SN - 9781577355083
T3 - Proceedings of the National Conference on Artificial Intelligence
SP - 719
EP - 725
BT - AAAI-11 / IAAI-11 - Proceedings of the 25th AAAI Conference on Artificial Intelligence and the 23rd Innovative Applications of Artificial Intelligence Conference
T2 - 25th AAAI Conference on Artificial Intelligence and the 23rd Innovative Applications of Artificial Intelligence Conference, AAAI-11 / IAAI-11
Y2 - 7 August 2011 through 11 August 2011
ER -