Coalition Structure Generation and CS-core: Results on the Tractability Frontier for games represented by MC-nets - Sorbonne Université
Conference Papers Year : 2017

Coalition Structure Generation and CS-core: Results on the Tractability Frontier for games represented by MC-nets

Patrice Perny
Makoto Yokoo
  • Function : Author
  • PersonId : 1007856

Abstract

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 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.
Fichier principal
Vignette du fichier
aamas2017.pdf (377.41 Ko) Télécharger le fichier
Origin Files produced by the author(s)
Loading...

Dates and versions

hal-01520392 , version 1 (10-05-2017)

Identifiers

  • HAL Id : hal-01520392 , version 1

Cite

Julien Lesca, Patrice Perny, Makoto Yokoo. Coalition Structure Generation and CS-core: Results on the Tractability Frontier for games represented by MC-nets. International Conference on Autonomous Agents and Multiagent Systems, May 2017, Sao-Paulo, Brazil. ⟨hal-01520392⟩
223 View
157 Download

Share

More