Coalition Structure Generation and CS-core: Results on the Tractability Frontier for games represented by MC-nets
Lesca, Julien; Perny, Patrice; Yokoo, Makoto (2017), Coalition Structure Generation and CS-core: Results on the Tractability Frontier for games represented by MC-nets, in Larson, Kate; Winikoff, Michael; Das, Sanmay; Durfee, Edmund, Proceedings of the 16th International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS'17), ACM - Association for Computing Machinery : New York, NY, p. 308-316
TypeCommunication / Conférence
Conference title16th International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS'17)
Conference citySão Paulo
Book titleProceedings of the 16th International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS'17)
Book authorLarson, Kate; Winikoff, Michael; Das, Sanmay; Durfee, Edmund
MetadataShow full item record
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Laboratoire d'Informatique de Paris 6 [LIP6]
Abstract (EN)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 case 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.
Subjects / KeywordsMC-nets; core; coalition structure generation problem; theory of computation; game theory
Showing items related by title and author.
Fujita, Etsushi; Lesca, Julien; Sonoda, Akihisa; Todo, Taiki; Yokoo, Makoto (2018) Article accepté pour publication ou publié
A Complexity Approach for Core-Selecting Exchange with Multiple Indivisible Goods under Lexicographic Preferences Lesca, Julien; Fujita, Etsushi; Sonoda, Akihisa; Todo, Taiki; Yokoo, Makoto (2015) Communication / Conférence
Règles de dominance pour la recherche de solutions Choquet-optimales en optimisation combinatoire multi-objectifs Fouchal, Hugo; Galand, Lucie; Lesca, Julien; Perny, Patrice (2012) Communication / Conférence