Price of anarchy for graph coloring games with concave payoff

DOI10.3934/JDG.2017003zbMATH Open1354.91030arXiv1507.08249OpenAlexW2963503787MaRDI QIDQ501743FDOQ501743

Authors: Anand Srivastav, Elmira Shirazi Sheykhdarabadi, Lasse Kliemann 

Publication date: 10 January 2017

Published in: Journal of Dynamics and Games (Search for Journal in Brave)

Abstract: We study the price of anarchy in a class of graph coloring games (a subclass of polymatrix common-payoff games). In those games, players are vertices of an undirected, simple graph, and the strategy space of each player is the set of colors from $1$ to $k$. A tight bound on the price of anarchy of $frackk-1$ is known (Hoefer 2007, Kun et al. 2013), for the case that each player's payoff is the number of her neighbors with different color than herself. The study of more complex payoff functions was left as an open problem. We compute payoff for a player by determining the distance of her color to the color of each of her neighbors, applying a non-negative, real-valued, concave function $f$ to each of those distances, and then summing up the resulting values. This 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 the possible distances $0,dots,k-1$. We prove an upper bound of $2$ on the price of anarchy for concave functions $f$ that are non-decreasing or which assume $f^{*}$ at a distance on or below $lfloorfrack2floor$. Matching lower bounds are given for the monotone case and for the case that $f^{*}$ is assumed in $frack2$ for even $k$. For general concave functions, we prove an upper bound of $3$. We use a simple but powerful technique: we obtain an upper bound of $lambdageq1$ on the price of anarchy if we manage to give a splitting $lambd{a}_1+dots+lambd{a}_k=lambda$ such that $su{m}_{s=1}^{k}lambd{a}_{s}cdotf(|s-p|)geq{f}^{\ast }$ for all $pin1,dots,k$. The discovery of working splittings can be supported by computer experiments. We show how, once we have an idea what kind of splittings work, this technique helps in giving simple proofs, which mainly work by case distinctions, algebraic manipulations, and real calculus.

Full work available at URL: https://arxiv.org/abs/1507.08249

Recommendations

• Generalized graph \(k\)-coloring games
• Generalized graph \(k\)-coloring games
• Strategic Coloring of a Graph
• Strategic coloring of a graph
• A Game Theoretic Approach for Efficient Graph Coloring

zbMATH Keywords

graph coloringprice of anarchyconcave functionstrategic gamespectrum sharing

Mathematics Subject Classification ID

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

Cites Work

• Worst-case equilibria
• Title not available (Why is that?)
• Approximate graph coloring by semidefinite programming
• \(T\)-colorings of graphs: recent results and open problems
• Three short proofs in graph theory
• A survey on labeling graphs with a condition at distance two
• Graph labeling and radio channel assignment
• Algorithms, games, and the internet
• Title not available (Why is that?)
• Essentials of game theory. A concise, multidisciplinary introduction.
• Models and solution techniques for frequency assignment problems
• Distributed Graph Coloring: Fundamentals and Recent Developments
• Generation of lower bounds for minimum span frequency assignment
• Coordination games on graphs
• On spectrum sharing games
• Anti-coordination games and stable graph colorings
• Efficient equilibria in polymatrix coordination games
• Mathematical optimization models for WLAN planning
• Strategic coloring of a graph
• A Game Theoretic Approach for Efficient Graph Coloring
• On minmax theorems for multiplayer games

Cited In (6)

• Strategic coloring of a graph
• Generalized graph \(k\)-coloring games
• Generalized graph \(k\)-coloring games
• A Game Theoretic Approach for Efficient Graph Coloring
• The Local and Global Price of Anarchy of Graphical Games
• Price of Anarchy for the N-Player Competitive Cascade Game with Submodular Activation Functions

Uses Software

• CALMA

This page was built for publication: Price of anarchy for graph coloring games with concave payoff

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q501743)