×

Price of anarchy for graph coloring games with concave payoff. (English) Zbl 1354.91030

Summary: 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 \(\{1,\ldots,k\}\). A tight bound of \(\frac{k}{k-1}\) is known [M. Hoefer, Cost sharing and clustering under distributed competition. Konstanz: Univ. Konstanz (Diss.) (2007), https://people.mpi-inf.mpg.de/~mhoefer/05-07/diss.pdf; J. Kun et al., Lect. Notes Comput. Sci. 8146, 122–133 (2013; Zbl 1319.91047)], 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. [loc. cit.] for future work as special cases.
Denote \(f^\ast\) the maximum value that \(f\) attains on \(\{0,\ldots,k-1\}\). We prove an upper bound of 2 on the price of anarchy if \(f\) is non-decreasing or assumes \(f^\ast\) somewhere in \(\{0,\ldots,\lfloor\frac{k}{2}\rfloor\}\). Matching lower bounds are given for the monotone case and if \(f^\ast\) 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 + \cdots + \lambda_k\) of the bound \(\lambda\) we are proving.

MSC:

91A43 Games involving graphs
91A10 Noncooperative games
05C15 Coloring of graphs and hypergraphs

Citations:

Zbl 1319.91047

Software:

CALMA
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] K. I. Aardal, Models and solution techniques for frequency assignment problems,, Annals of Operations Research, 153, 79 (2007) · Zbl 1157.90005 · doi:10.1007/s10479-007-0178-0
[2] S. M. Allen, Generation of lower bounds for minimum span frequency assignment,, Discrete Applied Mathematics, 119, 59 (2002) · Zbl 1102.90372 · doi:10.1016/S0166-218X(01)00265-7
[3] K. Apt, Coordination games on graphs,, International Journal of Game Theory, 1 (2016) · Zbl 1415.91063 · doi:10.1007/s00182-016-0560-8
[4] L. Barenboim, <em>Distributed Graph Coloring: Fundamentals and Recent Developments</em>,, Morgan & Claypool Publishers (2013) · Zbl 1310.68004 · doi:10.2200/S00520ED1V01Y201307DCT011
[5] S. Bosio, Mathematical optimization models for WLAN planning,, Graphs and Algorithms in Communication Networks (Arie M.C.A. Koster and Xavier Muñoz, 283 (2010) · Zbl 1187.68022 · 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, 194 (1941) · JFM 67.0733.02 · doi:10.1017/S030500410002168X
[7] Y. Cai, On minmax theorems for multiplayer games,, Proceedings of the 22th Annual ACM-SIAM Symposium on Discrete Algorithms, 217 (2011) · Zbl 1377.91009
[8] T. Calamoneri, The \(L(h,k)\)-labelling problem: An updated survey and annotated bibliography,, The Computer Journal, 54, 1344 (2011) · doi:10.1093/comjnl/bxr037
[9] I. Chatzigiannakis, Distributed game-theoretic vertex coloring,, Principles of Distributed Systems, 103 (6490) · doi:10.1007/978-3-642-17653-1_9
[10] K. Chaudhuri1, A network coloring game,, Proceedings of the 4th International Workshop on Internet and Network Economics, 5385, 522 (2008) · doi:10.1007/978-3-540-92185-1_58
[11] E. Driouch, Greedy spectrum sharing for cognitive MIMO networks,, Proceedings of the 4th IEEE International Conference on Communications and Information Technology, 139 (2012) · doi:10.1109/ICCITechnol.2012.6285777
[12] B. Escoffier, Strategic coloring of a graph,, Algorithms and complexity, 6078, 155 (2010) · Zbl 1284.05168 · doi:10.1007/978-3-642-13073-1_15
[13] F. H. P. Fitzek, <em>Cognitive Wireless Networks: Concepts, Methodologies and Visions Inspiring the Age of Enlightenment of Wireless Communications</em>,, 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, 8 (1986) · doi:10.1109/T-VT.1986.24063
[15] L. Gourvès, On strong equilibria in the max cut game,, Internet and Network Economics, 608 (2009) · doi:10.1007/978-3-642-10841-9_62
[16] W. K. Hale, Frequency assignment: Theory and applications,, Proceedings of the IEEE, 68, 1497 (1980) · doi:10.1109/PROC.1980.11899
[17] M. M. Halldórsson, On spectrum sharing games,, Distributed Computing, 22, 235 (2010) · Zbl 1267.91007 · doi:10.1007/s00446-010-0098-0
[18] T. Hasunuma, Algorithmic aspects of distance constrained labeling: A survey,, International Journal of Networking and Computing, 4, 251 (2014) · doi:10.15803/ijnc.4.2_251
[19] M. Hoefer, <em>Cost Sharing and Clustering Under Distributed Competition</em>,, Ph.D. thesis, 05 (2007)
[20] J. C. M. Janssen, <em>Channel Assignment and Graph Labeling</em>,, Handbook of Wireless Networks and Mobile Computing (2002) · doi:10.1002/0471224561.ch5
[21] D. R. Karger, Approximate graph coloring by semidefinite programming,, Journal of the ACM, 45, 246 (1998) · Zbl 0904.68116 · doi:10.1145/274787.274791
[22] R. M. Karp, Reducibility among combinatorial problems,, Complexity of Computer Computations, 85 (1972) · Zbl 0366.68041 · doi:10.1007/978-1-4684-2001-2_9
[23] M. Kearns, An experimental study of the coloring problem on human subject networks,, Science, 313, 824 (2006) · doi:10.1126/science.1127207
[24] Elias Koutsoupias, Worst-case equilibria,, Proceedings of the 16th Annual Symposium on Theoretical Aspects of Computer Science, 1563, 404 (1999) · Zbl 1099.91501 · doi:10.1007/3-540-49116-3_38
[25] J. Kun, Anti-coordination games and stable graph colorings,, Proceedings of the 6th Annual ACM-SIAM Symposium on Algorithmic Game Theory, 8146, 122 (2013) · Zbl 1319.91047 · doi:10.1007/978-3-642-41392-6_11
[26] K. Leyton-Brown, <em>Essentials of Game Theory: A Concise Multidisceplanary Introduction</em>,, Morgan & Claypool Publishers (2008) · Zbl 1203.91002
[27] L. Lovász, Three short proofs in graph theory,, Journal of Combinatorial Theory, 19, 269 (1975) · Zbl 0322.05142 · doi:10.1016/0095-8956(75)90089-1
[28] P. N. Panagopoulou, A game theoretic approach for efficient graph coloring,, Proceedings of the 19th International Symposium on Algorithms and Computation, 5369, 183 (2008) · Zbl 1183.68585 · 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, 749 (2001) · Zbl 1323.68022 · doi:10.1145/380752.380883
[30] C. Peng, Utilization and fairness in spectrum assignment for opportunistic spectrum access,, Mobile Networks and Applications, 11, 555 (2006) · doi:10.1007/s11036-006-7322-y
[31] M. Rahn, Efficient equilibria in polymatrix coordination games,, Mathematical foundations of computer science 2015, 529 (2015) · Zbl 1468.91027 · 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, 229 (1991) · Zbl 0751.05042 · doi:10.1016/0012-365X(91)90258-4
[33] O. Schink, <em>Der Price of Anarchy und Die Komplexität von Stabilen Graphfärbungen,</em>, Master’s thesis (2014)
[34] K. Smith, Static and dynamic channel assignment using neural networks,, IEEE Journal on Selected Areas in Communications, 15, 238 (2002) · doi:10.1109/49.552073
[35] J. van den Heuvel, Graph labeling and radio channel assignment,, Journal of Graph Theory, 29, 263 (1998) · Zbl 0930.05087 · 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, 381 (1968) · Zbl 0205.49002
[37] R. K. Yeh, A survey on labeling graphs with a condition at distance two,, Discrete Mathematics, 306, 1217 (2006) · Zbl 1094.05047 · doi:10.1016/j.disc.2005.11.029
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.