Show simple item record

hal.structure.identifierDipartimento di Matematica Ennio De Giorgi
dc.contributor.authorBilò, Vittorio
hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorGourvès, Laurent
hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorMonnot, Jérôme
HAL ID: 178759
ORCID: 0000-0002-7452-6553
dc.date.accessioned2020-01-20T15:34:49Z
dc.date.available2020-01-20T15:34:49Z
dc.date.issued2019
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/20441
dc.descriptionPart of the Lecture Notes in Computer Science book series (LNCS, volume 11801)en
dc.language.isoenen
dc.subjectHedonic gamesen
dc.subjectPrice of anarchy/stabilityen
dc.subjectGraphsen
dc.subject.ddc519en
dc.titleOn a Simple Hedonic Game with Graph-Restricted Communicationen
dc.typeCommunication / Conférence
dc.description.abstractenWe study a hedonic game for which the feasible coalitions are prescribed by a graph representing the agents’ social relations. A group of agents can form a feasible coalition if and only if their corresponding vertices can be spanned with a star. This requirement guarantees that agents are connected, close to each other, and one central agent can coordinate the actions of the group. In our game everyone strives to join the largest feasible coalition. We study the existence and computational complexity of both Nash stable and core stable partitions. Then, we provide tight or asymptotically tight bounds on their quality, with respect to both the price of anarchy and stability, under two natural social functions, namely, the number of agents who are not in a singleton coalition, and the number of coalitions. We also derive refined bounds for games in which the social graph is restricted to be claw-free. Finally, we investigate the complexity of computing socially optimal partitions as well as extreme Nash stable ones.en
dc.identifier.citationpages252-265en
dc.relation.ispartoftitleAlgorithmic Game Theory, Proceedingsen
dc.relation.ispartofeditorFotakis, Dimitris
dc.relation.ispartofeditorMarkakis, Evangelos
dc.relation.ispartofpublnameSpringeren
dc.relation.ispartofpublcityChamen
dc.relation.ispartofdate2019
dc.relation.ispartofpages393en
dc.relation.ispartofurl10.1007/978-3-030-30473-7en
dc.subject.ddclabelProbabilités et mathématiques appliquéesen
dc.relation.ispartofisbn978-3-030-30472-0en
dc.relation.conftitle12th International Symposium on Algorithmic Game Theory, SAGT 2019en
dc.relation.confdate2019-09
dc.relation.confcityAthensen
dc.relation.confcountryGreeceen
dc.relation.forthcomingnonen
dc.identifier.doi10.1007/978-3-030-30473-7_17en
dc.description.ssrncandidatenonen
dc.description.halcandidatenonen
dc.description.readershiprechercheen
dc.description.audienceInternationalen
dc.relation.Isversionofjnlpeerreviewednonen
dc.relation.Isversionofjnlpeerreviewednonen
dc.date.updated2020-01-20T15:28:01Z
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record