# American Institute of Mathematical Sciences

• Previous Article
Control systems of interacting objects modeled as a game against nature under a mean field approach
• JDG Home
• This Issue
• Next Article
Global analysis of solutions on the Cournot-Theocharis duopoly with variable marginal costs
January  2017, 4(1): 41-58. doi: 10.3934/jdg.2017003

## Price of anarchy for graph coloring games with concave payoff

 Department of Computer Science, Kiel University, Christian-Albrechts-Platz 4,24118 Kiel, Germany

* Corresponding author: Lasse Kliemann lki@informatik.uni-kiel.de

Received  February 2016 Revised  November 2016 Published  December 2016

Fund Project: L. Kliemann is supported by DFG grants KL 2087/1-1 and SR 7/15-1. E. Shirazi Sheykhdarabadi is supported by a Federal State Scholarship at Kiel University.

We study the price of anarchy in graph coloring games (a subclass of polymatrix common-payoff games). Players are vertices of an undirected graph, and the strategies for each player are the colors $\left\{ {1, \ldots ,k} \right\}$. A tight bound of $\frac{k}{k-1}$ is known (Hoefer 2007, Kun et al. 2013), if each player's payoff is the number of neighbors with different color than herself.

In our generalization, payoff is computed by determining the distance of the player's color to the color of each neighbor, applying a concave function $f$ to each distance, and then summing up the resulting values. This is motivated, e. g., by spectrum sharing, and includes the payoff functions suggested by Kun et al. (2013) for future work as special cases.

Denote $f^*$ the maximum value that $f$ attains on $\left\{ {0, \ldots ,k - 1} \right\}$. We prove an upper bound of $2$ on the price of anarchy if $f$ is non-decreasing or assumes $f^*$ somewhere in $\left\{ {0, \ldots ,{\frac{k}{2}}} \right\}$. Matching lower bounds are given for the monotone case and if $f^*$ is assumed in $\frac{k}{2}$ for even $k$. For general concave $f$, we prove an upper bound of $3$. We use a new technique that works by an appropriate splitting $\lambda = \lambda_1 + \ldots + \lambda_k$ of the bound $\lambda$ we are proving.

Citation: Lasse Kliemann, Elmira Shirazi Sheykhdarabadi, Anand Srivastav. Price of anarchy for graph coloring games with concave payoff. Journal of Dynamics & Games, 2017, 4 (1) : 41-58. doi: 10.3934/jdg.2017003
##### References:

show all references

##### References:
 [1] Fan Sha, Deren Han, Weijun Zhong. Bounds on price of anarchy on linear cost functions. Journal of Industrial & Management Optimization, 2015, 11 (4) : 1165-1173. doi: 10.3934/jimo.2015.11.1165 [2] J. William Hoffman. Remarks on the zeta function of a graph. Conference Publications, 2003, 2003 (Special) : 413-422. doi: 10.3934/proc.2003.2003.413 [3] Marta Faias, Emma Moreno-García, Myrna Wooders. A strategic market game approach for the private provision of public goods. Journal of Dynamics & Games, 2014, 1 (2) : 283-298. doi: 10.3934/jdg.2014.1.283 [4] Xue-Yan Wu, Zhi-Ping Fan, Bing-Bing Cao. Cost-sharing strategy for carbon emission reduction and sales effort: A nash game with government subsidy. Journal of Industrial & Management Optimization, 2020, 16 (4) : 1999-2027. doi: 10.3934/jimo.2019040 [5] Carey Caginalp, Gunduz Caginalp. Asset price volatility and price extrema. Discrete & Continuous Dynamical Systems - B, 2020, 25 (5) : 1935-1958. doi: 10.3934/dcdsb.2020010 [6] Ganfu Wang, Xingzheng Ai, Chen Zheng, Li Zhong. Strategic inventory under suppliers competition. Journal of Industrial & Management Optimization, 2020, 16 (5) : 2159-2173. doi: 10.3934/jimo.2019048 [7] C. T. Cremins, G. Infante. A semilinear $A$-spectrum. Discrete & Continuous Dynamical Systems - S, 2008, 1 (2) : 235-242. doi: 10.3934/dcdss.2008.1.235 [8] Junichi Minagawa. On the uniqueness of Nash equilibrium in strategic-form games. Journal of Dynamics & Games, 2020, 7 (2) : 97-104. doi: 10.3934/jdg.2020006 [9] Nickolas J. Michelacakis. Strategic delegation effects on Cournot and Stackelberg competition. Journal of Dynamics & Games, 2018, 5 (3) : 231-242. doi: 10.3934/jdg.2018015 [10] Gang Chen, Zaiming Liu, Jingchuan Zhang. Analysis of strategic customer behavior in fuzzy queueing systems. Journal of Industrial & Management Optimization, 2020, 16 (1) : 371-386. doi: 10.3934/jimo.2018157 [11] Misha Perepelitsa. A model of cultural evolution in the context of strategic conflict. Kinetic & Related Models, 2021, 14 (3) : 523-539. doi: 10.3934/krm.2021014 [12] Eric Babson and Dmitry N. Kozlov. Topological obstructions to graph colorings. Electronic Research Announcements, 2003, 9: 61-68. [13] Oded Schramm. Hyperfinite graph limits. Electronic Research Announcements, 2008, 15: 17-23. doi: 10.3934/era.2008.15.17 [14] John Kieffer and En-hui Yang. Ergodic behavior of graph entropy. Electronic Research Announcements, 1997, 3: 11-16. [15] Roberto De Leo, James A. Yorke. The graph of the logistic map is a tower. Discrete & Continuous Dynamical Systems, 2021, 41 (11) : 5243-5269. doi: 10.3934/dcds.2021075 [16] Shaolin Ji, Xiaomin Shi. Recursive utility optimization with concave coefficients. Mathematical Control & Related Fields, 2018, 8 (3&4) : 753-775. doi: 10.3934/mcrf.2018033 [17] Juliang Zhang, Jian Chen. Information sharing in a make-to-stock supply chain. Journal of Industrial & Management Optimization, 2014, 10 (4) : 1169-1189. doi: 10.3934/jimo.2014.10.1169 [18] Dan Mangoubi. A gradient estimate for harmonic functions sharing the same zeros. Electronic Research Announcements, 2014, 21: 62-71. doi: 10.3934/era.2014.21.62 [19] Rafael Bravo De La Parra, Luis Sanz. A discrete model of competing species sharing a parasite. Discrete & Continuous Dynamical Systems - B, 2020, 25 (6) : 2121-2142. doi: 10.3934/dcdsb.2019204 [20] Osman Palanci, Mustafa Ekici, Sirma Zeynep Alparslan Gök. On the equal surplus sharing interval solutions and an application. Journal of Dynamics & Games, 2021, 8 (2) : 139-150. doi: 10.3934/jdg.2020023

Impact Factor:

## Metrics

• HTML views (166)
• Cited by (2)

• on AIMS