Price of anarchy for graph coloring games with concave payoff

Lasse Kliemann; Elmira Shirazi Sheykhdarabadi; Anand Srivastav

doi:10.3934/jdg.2017003

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

Lasse Kliemann ^, , Elmira Shirazi Sheykhdarabadi and Anand Srivastav

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.

Keywords: Graph coloring, strategic game, price of anarchy, concave function, spectrum sharing.

Mathematics Subject Classification: Primary: 91A43, 91A06; Secondary: 05C15.

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

References:

[1]	K. I. Aardal, S. P. M. van Hoesel, A. M. C. A. Koster, C. Mannino and A. Sassano, Models and solution techniques for frequency assignment problems, Annals of Operations Research, 153 (2007), 79-129. doi: 10.1007/s10479-007-0178-0.
[2]	S. M. Allen, D. H. Smith and S. Hurley, Generation of lower bounds for minimum span frequency assignment, Discrete Applied Mathematics, 119 (2002), 59-78. doi: 10.1016/S0166-218X(01)00265-7.
[3]	K. Apt, M. Rahn, G. Schäfer and S. Simon, Coordination games on graphs, International Journal of Game Theory, (2016), 1-27, available from http://arxiv.org/abs/1501.07388. doi: 10.1007/s00182-016-0560-8.
[4]	L. Barenboim and M. Elkin, Distributed Graph Coloring: Fundamentals and Recent Developments Morgan & Claypool Publishers, 2013. doi: 10.2200/S00520ED1V01Y201307DCT011.
[5]	S. Bosio, A. Eisenblätter, H. -F. Geerdes, I. Siomina and D. Yuan, Mathematical optimization models for WLAN planning, Graphs and Algorithms in Communication Networks (Arie M. C. A. Koster and Xavier Muñoz, eds. ), Springer-Verlag Berlin Heidelberg, 2010,283-309. doi: 10.1007/978-3-642-02250-0_11.
[6]	R. Leonard Brooks, On colouring the nodes of a network, Mathematical Proceedings of the Cambridge Philosophical Society, 37 (1941), 194-197. doi: 10.1017/S030500410002168X.
[7]	Y. Cai and C. Daskalakis, On minmax theorems for multiplayer games, Proceedings of the 22th Annual ACM-SIAM Symposium on Discrete Algorithms, San Francisco, CA, USA, January 2011 (SODA 2011), 2011,217{234, available from http://hdl.handle.net/1721.1/73129.
[8]	T. Calamoneri, The L(h, k)-labelling problem: An updated survey and annotated bibliography, The Computer Journal, 54 (2011), 1344-1371. doi: 10.1093/comjnl/bxr037.
[9]	I. Chatzigiannakis, C. Koninis, P. N. Panagopoulou and P. G. Spirakis, Distributed gametheoretic vertex coloring, Principles of Distributed Systems, Volume 6490 of the series Lecture Notes in Computer Science, 2010,103-118. doi: 10.1007/978-3-642-17653-1_9.
[10]	K. Chaudhuri1, F. Chung Graham and M. S. Jamall, A network coloring game, Proceedings of the 4th International Workshop on Internet and Network Economics, Shanghai, China, December 2008 (WINE 2008), 5385 (2008), 522-530. doi: 10.1007/978-3-540-92185-1_58.
[11]	E. Driouch and W. Ajib, Greedy spectrum sharing for cognitive MIMO networks, Proceedings of the 4th IEEE International Conference on Communications and Information Technology, Hammamet, Tunisia, June 2012 (IEEE ICCIT 2012), 2012,139-143. doi: 10.1109/ICCITechnol.2012.6285777.
[12]	B. Escoffier and J. Monnot and L. Gourvès, Strategic coloring of a graph, Algorithms and complexity, Lecture Notes in Comput. Sci., Springer, Berlin, 6078 (2010), 155-166. doi: 10.1007/978-3-642-13073-1_15.
[13]	F. H. P. Fitzek and M. D. Katz, Cognitive Wireless Networks: Concepts, Methodologies and Visions Inspiring the Age of Enlightenment of Wireless Communications Springer Netherlands, 2007. doi: 10.1007/978-1-4020-5979-7.
[14]	A. Gamst, Some lower bounds for a class of frequency assignment problems, IEEE Transactions on Vehicular Technology, 35 (1986), 8-14. doi: 10.1109/T-VT.1986.24063.
[15]	L. Gourvès and J. Monnot, On strong equilibria in the max cut game, Internet and Network Economics, Volume 5929 of the series Lecture Notes in Computer Science, (2009), 608-615. doi: 10.1007/978-3-642-10841-9_62.
[16]	W. K. Hale, Frequency assignment: Theory and applications, Proceedings of the IEEE, 68 (1980), 1497-1514. doi: 10.1109/PROC.1980.11899.
[17]	M. M. Halldórsson, J. Y. Halpern, L. E. Li and V. S. Mirrokni, On spectrum sharing games, Distributed Computing, 22 (2010), 235-248, Conference version at PODC 2004. doi: 10.1007/s00446-010-0098-0.
[18]	T. Hasunuma, T. Ishii, H. Ono and Y. Uno, Algorithmic aspects of distance constrained labeling: A survey, International Journal of Networking and Computing, 4 (2014), 251-259, available from http://www.ijnc.org/index.php/ijnc/article/view/85. doi: 10.15803/ijnc.4.2_251.
[19]	M. Hoefer, Cost Sharing and Clustering Under Distributed Competition, Ph. D. thesis, Department of Computer and Information Science, University of Konstanz, 2007, available from https://people.mpi-inf.mpg.de/~mhoefer/05-07/diss.pdf.
[20]	J. C. M. Janssen, Channel Assignment and Graph Labeling Handbook of Wireless Networks and Mobile Computing, John Wiley & Sons, Inc., New York, USA, 2002. doi: 10.1002/0471224561.ch5.
[21]	D. R. Karger, R. Motwani and M. Sudan, Approximate graph coloring by semidefinite programming, Journal of the ACM, 45 (1998), 246-265, Conference version at FOCS 1994. doi: 10.1145/274787.274791.
[22]	R. M. Karp, Reducibility among combinatorial problems, Complexity of Computer Computations, Springer US, 1972, 85-103, available from http://cgi.di.uoa.gr/~sgk/teaching/grad/handouts/karp.pdf. doi: 10.1007/978-1-4684-2001-2_9.
[23]	M. Kearns, S. Suri and N. Montfort, An experimental study of the coloring problem on human subject networks, Science, 313 (2006), 824-827. doi: 10.1126/science.1127207.
[24]	Elias Koutsoupias and Christos H. Papadimitriou, Worst-case equilibria, Proceedings of the 16th Annual Symposium on Theoretical Aspects of Computer Science, Trier, Germany, March 1999 (STACS 1999), 1563 (1999), 404-413. doi: 10.1007/3-540-49116-3_38.
[25]	J. Kun, B. Powers and L. Reyzin, Anti-coordination games and stable graph colorings, Proceedings of the 6th Annual ACM-SIAM Symposium on Algorithmic Game Theory, Aachen, Germany, October 2013 (SAGT 2013) (Berthold Vöcking, ed. ), Lecture Notes in Computer Science, 8146 (2013), 122-133. doi: 10.1007/978-3-642-41392-6_11.
[26]	K. Leyton-Brown and Y. Shoham, Essentials of Game Theory: A Concise Multidisceplanary Introduction Morgan & Claypool Publishers, 2008, available from http://www.morganclaypool.com/doi/abs/10.2200/S00108ED1V01Y200802AIM003.
[27]	L. Lovász, Three short proofs in graph theory, Journal of Combinatorial Theory, Series B, 19 (1975), 269-271. doi: 10.1016/0095-8956(75)90089-1.
[28]	P. N. Panagopoulou and P. G. Spirakis, A game theoretic approach for efficient graph coloring, Proceedings of the 19th International Symposium on Algorithms and Computation, Gold Coast, Australia, December 2008 (ISAAC 2008), 5369 (2008), 183-195. doi: 10.1007/978-3-540-92182-0_19.
[29]	C. H. Papadimitriou, Algorithms, games, and the Internet, Proceedings of the 33rd Annual ACM Symposium on Theory of Computing, Crete, Greece, July 2001 (STOC 2001), 2001, Extended abstract at ICALP, 2001,749-753. doi: 10.1145/380752.380883.
[30]	C. Peng, H. Zheng and B. Y. Zhao, Utilization and fairness in spectrum assignment for opportunistic spectrum access, Mobile Networks and Applications, 11 (2006), 555-576. doi: 10.1007/s11036-006-7322-y.
[31]	M. Rahn and G. Schäfer, Efficient equilibria in polymatrix coordination games, Mathematical foundations of computer science 2015, Part Ⅱ, 529-541, Lecture Notes in Comput. Sci., 9235, Springer, Heidelberg, 2015, available from http://arxiv.org/abs/1504.07518. doi: 10.1007/978-3-662-48054-0_44.
[32]	F. S. Roberts, T-colorings of graphs: Recent results and open problems, Discrete Mathematics, 93 (1991), 229-245. doi: 10.1016/0012-365X(91)90258-4.
[33]	O. Schink, Der Price of Anarchy und Die Komplexität von Stabilen Graphfärbungen, Master's thesis, Christian-Albrechts-Universität Kiel, Mathe-matisches Seminar, 2014.
[34]	K. Smith and M. Palaniswami, Static and dynamic channel assignment using neural networks, IEEE Journal on Selected Areas in Communications, 15 (2002), 238-249. doi: 10.1109/49.552073.
[35]	J. van den Heuvel, R. A. Leese and M. A. Shepherd, Graph labeling and radio channel assignment, Journal of Graph Theory, 29 (1998), 263-283. doi: 10.1002/(SICI)1097-0118(199812)29:4<263::AID-JGT5>3.0.CO;2-V.
[36]	E. Borisovna Yanovskaya, Equilibrium points in polymatrix games, Litovskii Matematicheskii Sbornik, 8 (1968), 381-384, In Russian.
[37]	R. K. Yeh, A survey on labeling graphs with a condition at distance two, Discrete Mathematics, 306 (2006), 1217-1231. doi: 10.1016/j.disc.2005.11.029.

show all references

References:

[1]	K. I. Aardal, S. P. M. van Hoesel, A. M. C. A. Koster, C. Mannino and A. Sassano, Models and solution techniques for frequency assignment problems, Annals of Operations Research, 153 (2007), 79-129. doi: 10.1007/s10479-007-0178-0.
[2]	S. M. Allen, D. H. Smith and S. Hurley, Generation of lower bounds for minimum span frequency assignment, Discrete Applied Mathematics, 119 (2002), 59-78. doi: 10.1016/S0166-218X(01)00265-7.
[3]	K. Apt, M. Rahn, G. Schäfer and S. Simon, Coordination games on graphs, International Journal of Game Theory, (2016), 1-27, available from http://arxiv.org/abs/1501.07388. doi: 10.1007/s00182-016-0560-8.
[4]	L. Barenboim and M. Elkin, Distributed Graph Coloring: Fundamentals and Recent Developments Morgan & Claypool Publishers, 2013. doi: 10.2200/S00520ED1V01Y201307DCT011.
[5]	S. Bosio, A. Eisenblätter, H. -F. Geerdes, I. Siomina and D. Yuan, Mathematical optimization models for WLAN planning, Graphs and Algorithms in Communication Networks (Arie M. C. A. Koster and Xavier Muñoz, eds. ), Springer-Verlag Berlin Heidelberg, 2010,283-309. doi: 10.1007/978-3-642-02250-0_11.
[6]	R. Leonard Brooks, On colouring the nodes of a network, Mathematical Proceedings of the Cambridge Philosophical Society, 37 (1941), 194-197. doi: 10.1017/S030500410002168X.
[7]	Y. Cai and C. Daskalakis, On minmax theorems for multiplayer games, Proceedings of the 22th Annual ACM-SIAM Symposium on Discrete Algorithms, San Francisco, CA, USA, January 2011 (SODA 2011), 2011,217{234, available from http://hdl.handle.net/1721.1/73129.
[8]	T. Calamoneri, The L(h, k)-labelling problem: An updated survey and annotated bibliography, The Computer Journal, 54 (2011), 1344-1371. doi: 10.1093/comjnl/bxr037.
[9]	I. Chatzigiannakis, C. Koninis, P. N. Panagopoulou and P. G. Spirakis, Distributed gametheoretic vertex coloring, Principles of Distributed Systems, Volume 6490 of the series Lecture Notes in Computer Science, 2010,103-118. doi: 10.1007/978-3-642-17653-1_9.
[10]	K. Chaudhuri1, F. Chung Graham and M. S. Jamall, A network coloring game, Proceedings of the 4th International Workshop on Internet and Network Economics, Shanghai, China, December 2008 (WINE 2008), 5385 (2008), 522-530. doi: 10.1007/978-3-540-92185-1_58.
[11]	E. Driouch and W. Ajib, Greedy spectrum sharing for cognitive MIMO networks, Proceedings of the 4th IEEE International Conference on Communications and Information Technology, Hammamet, Tunisia, June 2012 (IEEE ICCIT 2012), 2012,139-143. doi: 10.1109/ICCITechnol.2012.6285777.
[12]	B. Escoffier and J. Monnot and L. Gourvès, Strategic coloring of a graph, Algorithms and complexity, Lecture Notes in Comput. Sci., Springer, Berlin, 6078 (2010), 155-166. doi: 10.1007/978-3-642-13073-1_15.
[13]	F. H. P. Fitzek and M. D. Katz, Cognitive Wireless Networks: Concepts, Methodologies and Visions Inspiring the Age of Enlightenment of Wireless Communications Springer Netherlands, 2007. doi: 10.1007/978-1-4020-5979-7.
[14]	A. Gamst, Some lower bounds for a class of frequency assignment problems, IEEE Transactions on Vehicular Technology, 35 (1986), 8-14. doi: 10.1109/T-VT.1986.24063.
[15]	L. Gourvès and J. Monnot, On strong equilibria in the max cut game, Internet and Network Economics, Volume 5929 of the series Lecture Notes in Computer Science, (2009), 608-615. doi: 10.1007/978-3-642-10841-9_62.
[16]	W. K. Hale, Frequency assignment: Theory and applications, Proceedings of the IEEE, 68 (1980), 1497-1514. doi: 10.1109/PROC.1980.11899.
[17]	M. M. Halldórsson, J. Y. Halpern, L. E. Li and V. S. Mirrokni, On spectrum sharing games, Distributed Computing, 22 (2010), 235-248, Conference version at PODC 2004. doi: 10.1007/s00446-010-0098-0.
[18]	T. Hasunuma, T. Ishii, H. Ono and Y. Uno, Algorithmic aspects of distance constrained labeling: A survey, International Journal of Networking and Computing, 4 (2014), 251-259, available from http://www.ijnc.org/index.php/ijnc/article/view/85. doi: 10.15803/ijnc.4.2_251.
[19]	M. Hoefer, Cost Sharing and Clustering Under Distributed Competition, Ph. D. thesis, Department of Computer and Information Science, University of Konstanz, 2007, available from https://people.mpi-inf.mpg.de/~mhoefer/05-07/diss.pdf.
[20]	J. C. M. Janssen, Channel Assignment and Graph Labeling Handbook of Wireless Networks and Mobile Computing, John Wiley & Sons, Inc., New York, USA, 2002. doi: 10.1002/0471224561.ch5.
[21]	D. R. Karger, R. Motwani and M. Sudan, Approximate graph coloring by semidefinite programming, Journal of the ACM, 45 (1998), 246-265, Conference version at FOCS 1994. doi: 10.1145/274787.274791.
[22]	R. M. Karp, Reducibility among combinatorial problems, Complexity of Computer Computations, Springer US, 1972, 85-103, available from http://cgi.di.uoa.gr/~sgk/teaching/grad/handouts/karp.pdf. doi: 10.1007/978-1-4684-2001-2_9.
[23]	M. Kearns, S. Suri and N. Montfort, An experimental study of the coloring problem on human subject networks, Science, 313 (2006), 824-827. doi: 10.1126/science.1127207.
[24]	Elias Koutsoupias and Christos H. Papadimitriou, Worst-case equilibria, Proceedings of the 16th Annual Symposium on Theoretical Aspects of Computer Science, Trier, Germany, March 1999 (STACS 1999), 1563 (1999), 404-413. doi: 10.1007/3-540-49116-3_38.
[25]	J. Kun, B. Powers and L. Reyzin, Anti-coordination games and stable graph colorings, Proceedings of the 6th Annual ACM-SIAM Symposium on Algorithmic Game Theory, Aachen, Germany, October 2013 (SAGT 2013) (Berthold Vöcking, ed. ), Lecture Notes in Computer Science, 8146 (2013), 122-133. doi: 10.1007/978-3-642-41392-6_11.
[26]	K. Leyton-Brown and Y. Shoham, Essentials of Game Theory: A Concise Multidisceplanary Introduction Morgan & Claypool Publishers, 2008, available from http://www.morganclaypool.com/doi/abs/10.2200/S00108ED1V01Y200802AIM003.
[27]	L. Lovász, Three short proofs in graph theory, Journal of Combinatorial Theory, Series B, 19 (1975), 269-271. doi: 10.1016/0095-8956(75)90089-1.
[28]	P. N. Panagopoulou and P. G. Spirakis, A game theoretic approach for efficient graph coloring, Proceedings of the 19th International Symposium on Algorithms and Computation, Gold Coast, Australia, December 2008 (ISAAC 2008), 5369 (2008), 183-195. doi: 10.1007/978-3-540-92182-0_19.
[29]	C. H. Papadimitriou, Algorithms, games, and the Internet, Proceedings of the 33rd Annual ACM Symposium on Theory of Computing, Crete, Greece, July 2001 (STOC 2001), 2001, Extended abstract at ICALP, 2001,749-753. doi: 10.1145/380752.380883.
[30]	C. Peng, H. Zheng and B. Y. Zhao, Utilization and fairness in spectrum assignment for opportunistic spectrum access, Mobile Networks and Applications, 11 (2006), 555-576. doi: 10.1007/s11036-006-7322-y.
[31]	M. Rahn and G. Schäfer, Efficient equilibria in polymatrix coordination games, Mathematical foundations of computer science 2015, Part Ⅱ, 529-541, Lecture Notes in Comput. Sci., 9235, Springer, Heidelberg, 2015, available from http://arxiv.org/abs/1504.07518. doi: 10.1007/978-3-662-48054-0_44.
[32]	F. S. Roberts, T-colorings of graphs: Recent results and open problems, Discrete Mathematics, 93 (1991), 229-245. doi: 10.1016/0012-365X(91)90258-4.
[33]	O. Schink, Der Price of Anarchy und Die Komplexität von Stabilen Graphfärbungen, Master's thesis, Christian-Albrechts-Universität Kiel, Mathe-matisches Seminar, 2014.
[34]	K. Smith and M. Palaniswami, Static and dynamic channel assignment using neural networks, IEEE Journal on Selected Areas in Communications, 15 (2002), 238-249. doi: 10.1109/49.552073.
[35]	J. van den Heuvel, R. A. Leese and M. A. Shepherd, Graph labeling and radio channel assignment, Journal of Graph Theory, 29 (1998), 263-283. doi: 10.1002/(SICI)1097-0118(199812)29:4<263::AID-JGT5>3.0.CO;2-V.
[36]	E. Borisovna Yanovskaya, Equilibrium points in polymatrix games, Litovskii Matematicheskii Sbornik, 8 (1968), 381-384, In Russian.
[37]	R. K. Yeh, A survey on labeling graphs with a condition at distance two, Discrete Mathematics, 306 (2006), 1217-1231. doi: 10.1016/j.disc.2005.11.029.

[1]	Fan Sha, Deren Han, Weijun Zhong. Bounds on price of anarchy on linear cost functions. Journal of Industrial and 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 and Games, 2014, 1 (2) : 283-298. doi: 10.3934/jdg.2014.1.283
[4]	Ying Wang, Haohao Song. A game theoretic strategic model for understanding the online-offline competition and fairness concern under community group buying. Journal of Industrial and Management Optimization, 2022 doi: 10.3934/jimo.2022012
[5]	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 and Management Optimization, 2020, 16 (4) : 1999-2027. doi: 10.3934/jimo.2019040
[6]	Carey Caginalp, Gunduz Caginalp. Asset price volatility and price extrema. Discrete and Continuous Dynamical Systems - B, 2020, 25 (5) : 1935-1958. doi: 10.3934/dcdsb.2020010
[7]	Ganfu Wang, Xingzheng Ai, Chen Zheng, Li Zhong. Strategic inventory under suppliers competition. Journal of Industrial and Management Optimization, 2020, 16 (5) : 2159-2173. doi: 10.3934/jimo.2019048
[8]	C. T. Cremins, G. Infante. A semilinear $A$-spectrum. Discrete and Continuous Dynamical Systems - S, 2008, 1 (2) : 235-242. doi: 10.3934/dcdss.2008.1.235
[9]	Shaolin Ji, Xiaomin Shi. Recursive utility optimization with concave coefficients. Mathematical Control and Related Fields, 2018, 8 (3&4) : 753-775. doi: 10.3934/mcrf.2018033
[10]	Junichi Minagawa. On the uniqueness of Nash equilibrium in strategic-form games. Journal of Dynamics and Games, 2020, 7 (2) : 97-104. doi: 10.3934/jdg.2020006
[11]	Nickolas J. Michelacakis. Strategic delegation effects on Cournot and Stackelberg competition. Journal of Dynamics and Games, 2018, 5 (3) : 231-242. doi: 10.3934/jdg.2018015
[12]	Gang Chen, Zaiming Liu, Jingchuan Zhang. Analysis of strategic customer behavior in fuzzy queueing systems. Journal of Industrial and Management Optimization, 2020, 16 (1) : 371-386. doi: 10.3934/jimo.2018157
[13]	Misha Perepelitsa. A model of cultural evolution in the context of strategic conflict. Kinetic and Related Models, 2021, 14 (3) : 523-539. doi: 10.3934/krm.2021014
[14]	Eric Babson and Dmitry N. Kozlov. Topological obstructions to graph colorings. Electronic Research Announcements, 2003, 9: 61-68.
[15]	Oded Schramm. Hyperfinite graph limits. Electronic Research Announcements, 2008, 15: 17-23. doi: 10.3934/era.2008.15.17
[16]	John Kieffer and En-hui Yang. Ergodic behavior of graph entropy. Electronic Research Announcements, 1997, 3: 11-16.
[17]	Roberto De Leo, James A. Yorke. The graph of the logistic map is a tower. Discrete and Continuous Dynamical Systems, 2021, 41 (11) : 5243-5269. doi: 10.3934/dcds.2021075
[18]	Juliang Zhang, Jian Chen. Information sharing in a make-to-stock supply chain. Journal of Industrial and Management Optimization, 2014, 10 (4) : 1169-1189. doi: 10.3934/jimo.2014.10.1169
[19]	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
[20]	Rafael Bravo De La Parra, Luis Sanz. A discrete model of competing species sharing a parasite. Discrete and Continuous Dynamical Systems - B, 2020, 25 (6) : 2121-2142. doi: 10.3934/dcdsb.2019204

American Institute of Mathematical Sciences

Price of anarchy for graph coloring games with concave payoff

References:

References:

Tools

Metrics

Other articles
by authors

Tools

Tools

Metrics

Other articles
by authors

American Institute of Mathematical Sciences

Price of anarchy for graph coloring games with concave payoff

References:

References:

Tools

Metrics

Other articlesby authors

Tools

Tools

Metrics

Other articlesby authors

Other articles
by authors

Other articles
by authors