2021/06/01 by Nikolaos Fryganiotis, Symeon Papavassiliou, Fryganiotis, Nikolaos +3
Business, Management and Accounting · Decision Sciences · Economics, Econometrics and Finance · #Computer Science and Game Theory (cs.GT) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Facility Location and Emergency Management #Game Theory and Applications #Game Theory and Voting Systems
paper · pdf · doi:10.48550/arxiv.2106.00402
openalex publication_date 2021/06/01 · openalex created_date 2022/07/25 · openalex updated_date 2026/07/28
The network coloring game has been proposed in the literature of social sciences as a model for conflict-resolution circumstances. The players of the game are the vertices of a graph with n vertices and maximum degree Δ. The game is played over rounds, and in each round all players simultaneously choose a color from a set of available colors. Players have local information of the graph: they only observe the colors chosen by their neighbors and do not communicate or cooperate with one another. A player is happy when she has chosen a color that is different from the colors chosen by her neighbors, otherwise she is unhappy, and a configuration of colors for which all players are happy is a proper coloring of the graph. It has been shown in the literature that, when the players adopt a particular greedy randomized strategy, the game reaches a proper coloring of the graph within O(log(n)) rounds, with high probability, provided the number of colors available to each player is at least Δ+2. In this note we show that a modification of the aforementioned greedy strategy yields likewise a proper coloring of the graph, provided the number of colors available to each player is at least Δ+1, and results in a simple randomized distributed algorithm for the (Δ+1)-coloring problem..