Name
Abstract | ||
|---|---|---|
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 [1] 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.
|
Year | DOI | Venue |
|---|---|---|
2012 | 10.1007/978-3-642-13073-1_15 | Internet Mathematics |
Keywords | Field | DocType |
strategic coloring,coloring game,worst case bound,chromatic number,nash equilibrium,social cost,distinct color,social optimum,worst case,strategic game,own payoff,graphs,nash equilibria | Correlated equilibrium,Mathematical economics,Combinatorics,Risk dominance,Epsilon-equilibrium,Strategy,Computer science,Best response,Strategic dominance,Repeated game,Nash equilibrium | Journal |
Volume | Issue | ISSN |
8 | 4 | 0302-9743 |
ISBN | Citations | PageRank |
3-642-13072-0 | 3 | 0.44 |
References | Authors | |
9 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Bruno Escoffier | 1 | 430 | 37.32 |
| Laurent Gourvès | 2 | 241 | 30.97 |
| Jérôme Monnot | 3 | 512 | 55.74 |