IMI Interdisciplinary Mathematics InstituteCollege of Arts and Sciences

Price of Anarchy for Graph Coloring Games

  • Sept. 30, 2016
  • 2:30 p.m.
  • LeConte 312


We present the recent work of Kliemann, Sheykhdarabadi, and Srivastav on the price of anarchy for graph coloring games with concave payoff. In such games, the players are vertices of a simple, undirected graph, $G$, and the strategy space of each player is the set of colors [k]. A tight bound of $\frac{k}{k-1}$ is known for the case that each player's payoff is the number of her neighbors with different colors than herself (Hoefer 2007, Kun et al. 2013). The study of more complex payoff functions was left as an open problem.

© Interdisciplinary Mathematics Institute | The University of South Carolina Board of Trustees | Webmaster