Show simple item record

hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorEscoffier, Bruno
HAL ID: 5124
*
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.accessioned2017-01-04T15:53:20Z
dc.date.available2017-01-04T15:53:20Z
dc.date.issued2012
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/16119
dc.language.isoenen
dc.subjectthéorie des jeux
dc.subjectthéorie des graphes
dc.subject.ddc003en
dc.subject.classificationjelC.C4.C44en
dc.titleStrategic Coloring of a Graph
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenWe study a strategic game in which every node of a graph is owned by a player who has to choose a color. A player’s payoff is 0 if at least one neighbor selected the same color; otherwise, it is the number of players who selected the same color. The social cost of a state is defined as the number of distinct colors that the players use. It is ideally equal to the chromatic number of the graph, but it can substantially deviate because every player cares about his own payoff, however bad the social cost may be. Following previous work in [Panagopoulou and Spirakis 08] on the Nash equilibria of the coloring game, we give worst-case bounds on the social cost of stable states. Our main contribution is an improved (tight) bound for the worst-case social cost of a Nash equilibrium, as well as the study of strong equilibria, their existence, and how far they are from social optima.
dc.relation.isversionofjnlnameInternet Mathematics
dc.relation.isversionofjnlvol8
dc.relation.isversionofjnlissue4
dc.relation.isversionofjnldate2012
dc.relation.isversionofjnlpages424-455
dc.relation.isversionofdoi10.1080/15427951.2012.709217
dc.subject.ddclabelRecherche opérationnelleen
dc.relation.forthcomingnonen
dc.relation.forthcomingprintnonen
dc.description.ssrncandidatenon
dc.description.halcandidateoui
dc.description.readershiprecherche
dc.description.audienceInternational
dc.relation.Isversionofjnlpeerreviewednon
dc.date.updated2017-01-04T15:54:58Z
hal.identifierhal-01426608*
hal.version1*
hal.update.actionupdateFiles*
hal.update.actionupdateMetadata*
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