TY - GEN
T1 - Coalition structure generation and cs-core
T2 - 16th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2017
AU - Lesca, Julien
AU - Perny, Patrice
AU - Yokoo, Makoto
N1 - Publisher Copyright:
© Copyright 2017, International Foundation for Autonomous Agents and Multiagent Systems (www.ifaamas.org). All Rights Reserved.
PY - 2017
Y1 - 2017
N2 - The coalition structure generation (CSG) problem consists in partitioning a group of agents into coalitions to maximize the sum of their values. We consider here the rase of coalitional games whose characteristic function is compactly represented by a set of weighted conjunctive formulae (an MC-net). In this context the CSG problem is known to be computationally hard in general. In this paper, we first study some key parameters of MC- nets that complicate solving make the CSG problem. Then we consider a specific class of MC-nets, called bipolar MC- nets, and prove that the CSG problem is polynomial for this class. Finally, we show that the CS-core of a game represented by a bipolar MC-net is never empty, and that an imputation belonging to the CS-core can be computed in polynomial time.
AB - The coalition structure generation (CSG) problem consists in partitioning a group of agents into coalitions to maximize the sum of their values. We consider here the rase of coalitional games whose characteristic function is compactly represented by a set of weighted conjunctive formulae (an MC-net). In this context the CSG problem is known to be computationally hard in general. In this paper, we first study some key parameters of MC- nets that complicate solving make the CSG problem. Then we consider a specific class of MC-nets, called bipolar MC- nets, and prove that the CSG problem is polynomial for this class. Finally, we show that the CS-core of a game represented by a bipolar MC-net is never empty, and that an imputation belonging to the CS-core can be computed in polynomial time.
UR - http://www.scopus.com/inward/record.url?scp=85046422727&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85046422727&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:85046422727
T3 - Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS
SP - 308
EP - 316
BT - 16th International Conference on Autonomous Agents and Multiagent Systems, AAMAS 2017
A2 - Durfee, Edmund
A2 - Das, Sanmay
A2 - Larson, Kate
A2 - Winikoff, Michael
PB - International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS)
Y2 - 8 May 2017 through 12 May 2017
ER -