• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
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, 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

View/Open
coalition_s.pdf (434.6Kb)
Type
Communication / Conférence
Date
2017
Conference title
16th International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS'17)
Conference date
2017-05
Conference city
São Paulo
Conference country
Brazil
Book title
Proceedings of the 16th International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS'17)
Book author
Larson, Kate; Winikoff, Michael; Das, Sanmay; Durfee, Edmund
Publisher
ACM - Association for Computing Machinery
Published in
New York, NY
Pages
308-316
Metadata
Show full item record
Author(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
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 / Keywords
MC-nets; core; coalition structure generation problem; theory of computation; game theory
JEL
C71 - Cooperative Games

Related items

Showing items related by title and author.

  • Thumbnail
    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é
  • Thumbnail
    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
  • Thumbnail
    Dominance Rules for the Choquet Integral in Multiobjective Dynamic Programming 
    Galand, Lucie; Lesca, Julien; Perny, Patrice (2013) Communication / Conférence
  • Thumbnail
    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é
  • Thumbnail
    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
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo