• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Aide
  • Connexion
  • Langue 
    • Français
    • English
Consulter le document 
  •   Accueil
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • Consulter le document
  •   Accueil
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • Consulter le document
JavaScript is disabled for your browser. Some features of this site may not work without it.

Afficher

Toute la baseCentres de recherche & CollectionsAnnée de publicationAuteurTitreTypeCette collectionAnnée de publicationAuteurTitreType

Mon compte

Connexion

Enregistrement

Statistiques

Documents les plus consultésStatistiques par paysAuteurs les plus consultés
Thumbnail

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
coalition_s.pdf (434.6Kb)
Type
Communication / Conférence
Date
2017
Titre du colloque
16th International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS'17)
Date du colloque
2017-05
Ville du colloque
São Paulo
Pays du colloque
Brazil
Titre 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ète
Auteur(s)
Lesca, Julien
Laboratoire 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 theory
JEL
C71 - Cooperative Games

Publications associées

Affichage des éléments liés par titre et auteur.

  • Vignette de prévisualisation
    A Complexity Approach for Core-Selecting Exchange under Conditionally Lexicographic Preferences 
    Fujita, Etsushi; Lesca, Julien; Sonoda, Akihisa; Todo, Taiki; Yokoo, Makoto (2018) Article accepté pour publication ou publié
  • Vignette de prévisualisation
    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
  • Vignette de prévisualisation
    Dominance Rules for the Choquet Integral in Multiobjective Dynamic Programming 
    Galand, Lucie; Lesca, Julien; Perny, Patrice (2013) Communication / Conférence
  • Vignette de prévisualisation
    The Fair OWA One-to-One Assignment Problem: NP-Hardness and Polynomial Time Special Cases 
    Lesca, Julien; Minoux, Michel; Perny, Patrice (2019) Article accepté pour publication ou publié
  • Vignette de prévisualisation
    Some results on the McKean–Vlasov optimal control and mean field games : Limit theorems, dynamic programming principle and numerical approximations 
    Djete, Fabrice (2020-12-16) Thèse
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Tél. : 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo