Constrained Coalition Formation

Authors

  • Talal Rahwan University of Southampton
  • Tomasz Michalak University of Warsaw
  • Edith Elkind Nanyang Technological University
  • Piotr Faliszewski AGH University of Science and Technology
  • Jacek Sroka University of Warsaw
  • Michael Wooldridge University of Liverpool
  • Nicholas Jennings University of Southampton

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.

Downloads

Published

2011-08-04

How to Cite

Rahwan, T., Michalak, T., Elkind, E., Faliszewski, P., Sroka, J., Wooldridge, M., & Jennings, N. (2011). Constrained Coalition Formation. Proceedings of the AAAI Conference on Artificial Intelligence, 25(1), 719-725. Retrieved from https://ojs.aaai.org/index.php/AAAI/article/view/7888

Issue

Section

AAAI Technical Track: Multiagent Systems