Strategic Coloring of a Graph
Escoffier, Bruno; Gourvès, Laurent; Monnot, Jérôme (2010), Strategic Coloring of a Graph, Algorithms and Complexity 7th International Conference, CIAC 2010, Rome, Italy, May 26-28, 2010. Proceedings, Springer : Berlin, p. 155-156
TypeCommunication / Conférence
Conference title7th International Conference on Algorithms and Complexity CIAC 2010
Book titleAlgorithms and Complexity 7th International Conference, CIAC 2010, Rome, Italy, May 26-28, 2010. Proceedings
Series titleLecture Notes in Computer Science
MetadataShow full item record
Abstract (EN)We study a strategic game where 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, whatever how bad the social cost is. Following a previous work done by Panagopoulou and Spirakis  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, and the study of strong equilibria, their existence and how far they are from social optima.
Subjects / Keywordsgraphs
Showing items related by title and author.
Complexity and Approximation Results for the Connected Vertex Cover Problem in Graphs and Hypergraphs Monnot, Jérôme; Gourvès, Laurent; Escoffier, Bruno (2010) Article accepté pour publication ou publié