
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, dans 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
Voir/Ouvrir
Type
Communication / ConférenceDate
2017Titre du colloque
16th International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS'17)Date du colloque
2017-05Ville du colloque
São PauloPays du colloque
BrazilTitre de l'ouvrage
Proceedings of the 16th International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS'17)Auteurs de l’ouvrage
Larson, Kate; Winikoff, Michael; Das, Sanmay; Durfee, EdmundÉditeur
ACM - Association for Computing Machinery
Ville d’édition
New York, NY
Pages
308-316
Métadonnées
Afficher la notice complèteAuteur(s)
Lesca, JulienLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Perny, Patrice
Laboratoire d'Informatique de Paris 6 [LIP6]
Yokoo, Makoto
Kyushu, Japan
Résumé (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.Mots-clés
MC-nets; core; coalition structure generation problem; theory of computation; game theoryPublications associées
Affichage des éléments liés par titre et auteur.
-
Fujita, Etsushi; Lesca, Julien; Sonoda, Akihisa; Todo, Taiki; Yokoo, Makoto (2018) Article accepté pour publication ou publié
-
Lesca, Julien; Fujita, Etsushi; Sonoda, Akihisa; Todo, Taiki; Yokoo, Makoto (2015) Communication / Conférence
-
Galand, Lucie; Lesca, Julien; Perny, Patrice (2013) Communication / Conférence
-
Lesca, Julien; Minoux, Michel; Perny, Patrice (2019) Article accepté pour publication ou publié