Show simple item record

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

hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorLesca, Julien
hal.structure.identifierLaboratoire d'Informatique de Paris 6 [LIP6]
dc.contributor.authorPerny, Patrice
HAL ID: 9264
hal.structure.identifierKyushu, Japan
dc.contributor.authorYokoo, Makoto
dc.date.accessioned2018-03-23T09:37:47Z
dc.date.available2018-03-23T09:37:47Z
dc.date.issued2017
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/17585
dc.language.isoenen
dc.subjectMC-netsen
dc.subjectcoreen
dc.subjectcoalition structure generation problemen
dc.subjecttheory of computationen
dc.subjectgame theoryen
dc.subject.ddc519en
dc.subject.classificationjelC.C7.C71en
dc.titleCoalition Structure Generation and CS-core: Results on the Tractability Frontier for games represented by MC-netsen
dc.typeCommunication / Conférence
dc.description.abstractenThe 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.en
dc.identifier.citationpages308-316en
dc.relation.ispartoftitleProceedings of the 16th International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS'17)en
dc.relation.ispartofeditorLarson, Kate
dc.relation.ispartofeditorWinikoff, Michael
dc.relation.ispartofeditorDas, Sanmay
dc.relation.ispartofeditorDurfee, Edmund
dc.relation.ispartofpublnameACM - Association for Computing Machineryen
dc.relation.ispartofpublcityNew York, NYen
dc.relation.ispartofdate2017
dc.contributor.countryeditoruniversityotherFRANCE
dc.contributor.countryeditoruniversityotherJAPAN
dc.subject.ddclabelProbabilités et mathématiques appliquéesen
dc.relation.conftitle16th International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS'17)en
dc.relation.confdate2017-05
dc.relation.confcitySão Pauloen
dc.relation.confcountryBrazilen
dc.relation.forthcomingnonen
dc.description.ssrncandidatenonen
dc.description.halcandidatenonen
dc.description.readershiprechercheen
dc.description.audienceInternationalen
dc.relation.Isversionofjnlpeerreviewednonen
dc.relation.Isversionofjnlpeerreviewednonen
dc.date.updated2018-03-23T09:24:29Z
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut


Files in this item

Thumbnail
Name:
coalition_s.pdf
Size:
434.6Kb
Format:
PDF
View/Open

This item appears in the following Collection(s)

Show simple item record