On the Performance of Mildly Greedy Players in k-Coloring Games

In this paper, we study the following $k$-coloring game. We are given an undirected weighted graph $G=(V,E)$ with a weight function $c:E\mapsto {ℝ}^{+}$ that assigns to each edge $\{i,j\}\in E$ a non-negative real number. Vertices represent autonomous, selfish agents²²2Throughout the paper, we use the terms agent and player interchangeably. while edges capture mutual idiosyncrasies or conflicts. In addition, a set of $k\ge 2$ colors, denoting the options or strategies available to all agents, is given. Each agent has to select a color with the goal of maximizing her utility (or payoff), defined as the sum of the weights of the edges connecting her vertex to agents who have chosen a different color. Intuitively, agents benefit from distinguishing themselves from their neighbors in the graph.

This game forms one of the basic payoff structures in Game Theory and models well a variety of real-world scenarios, specifically all those situations in which agents need to mutually anti-coordinate their strategies in order to maximize their profit or minimize their damage. Examples include companies deciding which products to develop to avoid direct competition, airlines selecting flight paths to reduce congestion, antennas selecting frequencies to reduce interference, coalition formation processes [29, 21]. For a more detailed application, consider engineers working at a software company, each aiming to acquire technical skills that would boost their individual career prospects. Ideally, to stand out, they would prefer a rare but valuable skill rather than one that is common among colleagues. We can model this as a $k$-coloring game on a graph $G=(V,E)$, where each vertex $v_i\in V$ represents an engineer and an edge $(v_i,v_j)\in E$ indicates employees $i$ and $j$ collaborate or compete within a team. The $k$ available colors correspond to distinct skill sets (e.g., C++, Python, Rust, Go, Java). By choosing a color (skill) that differs from their neighbors’, engineers strategically enhance their uniqueness in the collaboration network.

We are interested in evaluating the performance of self-emerging solutions in $k$-coloring games with respect to the utilitarian social welfare, which sums up the utilities of all players. The utilitarian social welfare is the standard social function used in the literature to measure the quality of a strategy profile, and, in the context of $k$-coloring games, coincides, up to a multiplicative factor of $2$, with the total weight of the edges whose endpoints have different colors. To compare the quality of outcomes, emerging from the strategic behavior of selfish players, against the ones that could potentially be enforced by a dictatorial authority, Koutsoupias and Papadimitriou [28] introduced the well-known concept of Price of Anarchy (PoA). The PoA measures the worst-case ratio between the social value of a Nash equilibrium (in short NE), i.e., a strategy profile in which no player can improve her payoff by unilaterally changing her strategy, and the social value of a social optimum, that is a strategy profile optimizing the social function. As subsequent results have shown that even determining the existence of a NE in several games of interest is a computationally demanding task [29, 1, 22], a large amount of work has been devoted to analyzing how well less demanding solution concepts perform.

A first approach is to relax selfishness by allowing the presence of mildly greedy players, i.e., players who are willing to accept any strategy profile in which no substantial improvement can be obtained through a unilateral deviation. This naturally leads to the notion of approximate NE [6, 12, 14, 19]. Formally, given a value $ϵ\ge 0$, a $(1+ϵ)$-approximate NE is a strategy profile in which no player can improve her payoff by a multiplicative factor of more than $1+ϵ$ by unilaterally deviating to a different strategy. The $(1+ϵ)$-approximate Price of Anarchy ($(1+ϵ)$-PoA) is the generalization of the PoA to $(1+ϵ)$-approximate NEa. Clearly, a NE is a $(1+ϵ)$-approximate NE with $ϵ=0$ and the PoA is the $(1+ϵ)$-PoA with $ϵ=0$.

Other less demanding solution concepts can be derived from best-response dynamics, which are iterative processes in which, starting from a given strategy profile, players are processed sequentially and, at each step, one of them is allowed to change her current strategy by best-responding to the strategies played by the others. Clearly, when best-responses can be computed in polynomial time, a best-response dynamic with a polynomial number of steps can be efficiently computed. Indeed, solutions generated by sequences of best-responses of bounded length can exhibit appealing properties, and hence have been widely investigated. In particular, special cases of these dynamics are covering walks, $k$-covering walks, one-round walks, $k$-round walks and random one-round walks [30]. Note that one-round walks constitute the simplest of these dynamics and thus have been the target of several recent works [30, 20, 8, 9]. It is also worth noting that best-response dynamics can also accommodate mildly greedy players, and this translates into the corresponding definition of $(1+ϵ)$-approximate best-response dynamics, that is, dynamics in which each player changes her strategy only when this improves her utility by a multiplicative factor of at least $1+ϵ$. This concept has attracted considerable interest, as studies have demonstrated that (approximate) best-response dynamics play a key role in identifying both (approximate) NEa and high-quality solutions in a wide range of (non-cooperative) games [30]. For example, in the classical $2$-coloring game, a one-round walk may yield a solution whose social welfare is arbitrarily far from the optimum. Instead, if one admits mildly greedy players, it can be shown that the approximation ratio of the solutions achieved after a $(1+ϵ)$-approximate one-round walk starting from any initial strategy profile is equal to $1/(2+ϵ)$ for any $ϵ\ge 1$ and equal to $\frac{2ϵ}{(ϵ+1)(ϵ+2)}$ for any  [20, 7].

In this paper, we focus on the performance of mildly greedy players in $k$-coloring games. Using the primal-dual method of Bilò [4], we are able to lower bound the $(1+ϵ)$-PoA of any instance of the $k$-coloring game by $\frac{k-1}{(k-1)ϵ+k}$. Moreover, we construct specific instances of the game for which such a bound is tight for any possible value of $k$ and $ϵ$. Next, we shift our attention to approximate one-round walks, i.e., approximate best-response dynamics in which each player plays exactly once. In particular, we study the approximation ratio of the solutions achieved after a $(1+ϵ)$-approximate one-round walk starting from any initial strategy profile. This notion can be seen as an adaptation of the $(1+ϵ)$-PoA to $(1+ϵ)$-approximate one-round walks and is defined as the worst-case ratio between the social value of a strategy profile realized at the end of the walk and the social optimum. For this ratio, we provide a lower bound of $\min \{\frac{k-2}{k},\frac{k-1}{(k-1)ϵ+k}\}$, for any $ϵ\ge 0$ and $k\ge 5$, while for $k=3$ and $k=4$, we give finer bounds depending on $ϵ$. Our results generalize those known for cut games – the special case of $2$-coloring games – for which the $(1+ϵ)$-PoA and the approximation ratio of the solutions achieved after a $(1+ϵ)$-approximate one-round walk starting from any initial strategy profile have been shown to be equal to $\frac{1}{2+ϵ}$ and $\min \{\frac{1}{2+ϵ},\frac{2ϵ}{(1+ϵ)(2+ϵ)}\}$, respectively [7].

$k$-coloring games have been first investigated in [27, 29], where it is shown that a NE always exists and can be computed in polynomial time if the graph is unweighted. In weighted graphs, instead, a NE always exists, but the problem of computing one is PLS-complete even for $k=2$ [34]. Note that $2$-coloring games are exactly equivalent to max-cut games, where players partition vertices into sets to maximize the number of edges between sets. If the maximum degree of the graph is at most $3$, then a NE can be computed in polynomial time for $2$-coloring games [32]. A related investigation for the same class of games is presented in [3, 13], where the authors give an algorithm that, for any $ϵ>0$, computes a $(3+ϵ)$-approximate NE in time polynomial in $\frac{1}{ϵ}$ and the size of the graph. A better algorithm, returning a $2.7371$-approximate NE has been recently designed in [15]. All these results are obtained by suitably exploiting the potential function method. The performance of NEa in $k$-coloring games has been addressed in [23], while the authors of [18] consider NEa where players also have an extra profit depending on the chosen color. Finally, results on the existence of strong NEa, i.e., solutions resistant to coalitional deviations, for $k$-coloring games (also referred as max-k-cut games) have been given in [25, 26, 16, 2, 24].

The more general version of $k$-coloring games defined on directed graphs does not admit any potential function, and the problem of understanding whether they have a NE is NP-complete for any fixed $k\ge 2$, even in the unweighted case [29]. These games have been extensively studied in [17, 21], in which the authors provide (i) a randomized algorithm with polynomial expected running time that, given any constant $k\ge 2$, computes a constant-approximate NE when the minimum outgoing degree of the graph is at least as big as the sum of the logarithm of the maximum outgoing degree and that of the maximum ingoing degree; (ii) a deterministic polynomial time algorithm computing a $(1+ϵ)$-approximate NE, for any $ϵ>0$, by using $O(\frac{\log (n)}{ϵ})$ colors; (iii) an experimental evaluation of such algorithms, which are compared with an heuristic based on best-response dynamics.

Several methods have been proposed to characterize the quality of self-emerging solutions in non-cooperative systems [33, 31, 4]. Among them, the primal-dual framework in [4] has been successfully applied in a variety of situations. For example, the authors of [5] used this method to find a lower bounding instance for the sequential PoA of cut games. In [9, 11] the primal-dual method has been exploited to design efficient tax functions for weighted congestion games with polynomial latency functions. Many other successful applications of the method can be found in [4, 10] and references therein.

In this section, we establish background information and terminology used throughout the paper. We mostly follow definitions and notation given in [7].

Given a positive integer $r$, we denote by $[r]$ the set $\{1,\mathrm{\dots },r\}$. Let $G=(V,E)$ be an undirected weighted graph, with $|V|=n$ and let $c$ be a weight function $c:E\mapsto {ℝ}^{+}$ that assigns to each edge $\{i,j\}\in E$ a non-negative real number. Throughout the paper, we use the standard notation $V(G)$ and $E(G)$ to denote the set of vertices and the set of edges of a graph $G$, respectively, when they are not explicitly defined. Moreover, we assume that all vertices in $V(G)$ are numbered from $1$ to $n$, so that $V(G)=[n]$. We shall drop the argument $G$ from the notation when the reference graph $G$ is clear from the context.

An instance of the $k$-coloring game $𝒦(G)$ can be uniquely associated to a graph $G$ and a set of colors $K=[k]$ as follows. Each vertex $i\in V$ is a player whose set of strategies is exactly the set of $k$-colors $K$. A strategy profile $\sigma =(\sigma (1),\mathrm{\dots },\sigma (n))$, also called a state, is a vector such that, for each $i\in V$, $\sigma (i)\in K$ denotes the color chosen by player $i$. Given a strategy profile $\sigma$, the notation $({\sigma }_{-i},\tau )$ denotes the strategy profile in which player $i$ picks $\tau \in K$ as strategy in place of ${\sigma }_i$, while the strategy of the other players remains unchanged. Denote with Adj($i$)$:=\{j\in V:\{i,j\}\in E\}$ the set of neighboring vertices of vertex $i$, for each $i\in V$, and with $c_{ij}:=c(\{i,j\})$ the weight of edge $\{i,j\}\in E$. The utility of player $i$ in strategy profile $\sigma$ is

In other words, the utility of player $i$ is equal to the sum of the weights of the edges $\{i,j\}\in E$ incident to $i$, for which, in $\sigma$, player $j$ chooses a color different from the one selected by player $i$. As a measure of the quality of a strategy profile $\sigma$, half of the sum of the players’ utilities is a commonly used metric. Formally, we consider the following social function

which sums the weights of the edges whose endpoints have different colors. It is easy to see that $\text{COL}(\sigma )=\frac{1}{2}{\sum }_{i\in V}{U}_i(\sigma )$ for each strategy profile $\sigma$, so that COL can be seen as an alternative, and more intuitive, definition for the utilitarian social welfare.

Fix a strategy profile $\sigma$ and a value $ϵ\ge 0$. A $(1+ϵ)\text{-approximate improving deviation}$ for player $i$ in $\sigma$ is any strategy $\tau \in K$ such that $U_i(({\sigma }_{-i},\tau ))>(1+ϵ)U_i(\sigma )$. A $(1+ϵ)$-approximate NE is a strategy profile $\sigma$ such that, for each $i\in N$ and $\tau \in K$, we have $U_i(({\sigma }_{-i},{\tau }_i))\le (1+ϵ)U_i(\sigma )$, that is, no player has a $(1+ϵ)$-approximate improving deviation in $\sigma$. A $(1+ϵ)$-approximate best-response dynamics is a sequence of strategy profiles in which, at each step, a mildly greedy player is allowed to make the following type of choice: if she does not possess a $(1+ϵ)$-approximate improving deviation, then she confirms her current choice; otherwise, she changes her strategy in favor of the strategy giving her the largest utility. A $(1+ϵ)$-approximate one-round walk is a $(1+ϵ)$-approximate best-response dynamics in which each player is allowed to change strategy, in turn, exactly once. Formally, a $(1+ϵ)$-approximate one-round walk $W$ is a sequence of $n+1$ strategy profiles $W=({\sigma }^{(0)},{\sigma }^{(1)},\mathrm{\dots },{\sigma }^{(n)})$ such that ${\sigma }^{(0)}$ and ${\sigma }^{(n)}$ are, respectively, the starting and final states of the walk and, for each $i\in V$, state ${\sigma }^{(i)}$ is obtained from ${\sigma }^{(i-1)}$ as a result of the choice of player $i$. We shall denote with $f(W)$ the final state of a $(1+ϵ)$-approximate one-round walk $W$.

For a $k$-coloring game $𝒦(G)$, let ${\text{NE}}_{ϵ}(𝒦(G))$ be its set of $(1+ϵ)$-approximate NEa and let ${\sigma }^{\ast }$ be the strategy profile maximizing the social function COL. Then, the $(1+ϵ)\text{-approximate PoA}$ of $𝒦(G)$ is defined as:

which, by definition, belongs to the interval $[0,1]$. This notion can be generalized to the entire class of $k$-coloring games, denoted as $𝒦$, by defining the $(1+ϵ)\text{-approximate PoA}$ of class $𝒦$ as:

Let ${\text{ORW}}_{ϵ}(𝒦(G))$ be the set of $(1+ϵ)$-approximate one-round walks starting from any initial strategy profile of a $k$-coloring game $𝒦(G)$. The approximation ratio of the solutions achieved after a $(1+ϵ)$-approximate one-round walk  starting from any initial strategy profile of $𝒦(G)$ is defined as:

As above, this notion can be generalized to the entire class $𝒦$ as:

In this section, we provide the primal and dual formulations of the $k$-coloring game following the approach of Bilò et al. [4]. Note in fact that, since such game is a weighted congestion game, the primal-dual framework of [4] can be naturally applied to it. As in any primal-dual method, the key challenge is to find the correct formulation that better fits the method. Although the same framework has been applied to the cut-game (i.e., the case with $k=2$) [7], the generalization to the $k$-coloring game with $k\ge 3$ requires a fundamentally different model. In fact, it is no longer sufficient to know that two adjacent agents select different colors; the decision variables must also record the choice made by each agent. This results in a formulation whose dual counterpart poses more challenges due to the presence of an higher number of primal constraints, defined on any combination of vertices and colors, as discussed in what follows.

Given a $k$-coloring game $𝒦(G)$, let us denote with $\sigma$ a generic $(1+ϵ)$-approximate NE of $𝒦(G)$, and with ${\sigma }^{\ast }$ the social optimum. As per the general framework, we are going to consider $\sigma$ and ${\sigma }^{\ast }$ as fixed constants, while, for each $\{i,j\}\in E(G)$, the values $c_{ij}$ defining the edge weights are variables that must suitably be chosen so that: (i) $\sigma$ is indeed a $(1+ϵ)$-approximate NE of $𝒦(G)$, and (ii) the value of the social optimum ${\sigma }^{\ast }$ is equal to 1. These two constraints together allow to formulate the problem of computing the worst-case ratio $\frac{\text{COL}(\sigma )}{\text{COL}({\sigma }^{\ast })}$ as the minimization of the social value $\text{COL}(\sigma )$, since (ii) normalizes the value of the social optimum to 1.

Given a strategy profile $\sigma$, we introduce variables ${\alpha }_{is}^{\sigma }$ for indices $i\in V$ and $s\in K$ so that

That is, ${\alpha }_{is}^{\sigma }$ indicates whether player $i$ picks color $s$ in $\sigma$ or not. Note that the case in which $k=2$ is easier to model since one can exploit binary variables and their complements to describe if a pair of agents picks different colors.

The primal formulation, that we denote by $LP(\sigma ,{\sigma }^{\ast })$, reads:

The objective function (1) encodes the cost of the social function under strategy $\sigma$, for which the cost of the $\{i,j\}$ is considered when the color assigned by $\sigma$ to $j$ is different from that assigned to $i$ (this is encoded by the negation of ${\alpha }_{j\sigma (i)}^{\sigma }$). Constraints (2) ensure that no player $i$ has an $(1+ϵ)$-approximate improving deviation in $\sigma$ (i.e. that $\sigma$ is a $(1+ϵ)$-approximate NE). Equality (3) normalizes to $1$ the cost of the social optimum ${\sigma }^{\ast }$.

In this section, we give the primal formulation for the $(1+ϵ)$-approximate one-round walk of the $k$-coloring game. In particular, let $W$ be a $(1+ϵ)$-approximate one-round walk for a fixed game $𝒦(G)$, with $ϵ\ge 0$. Denote by ${\sigma }^S$ and ${\sigma }^F$ the initial and final states of $W$, respectively, and by $𝒞\mathscr{H}$ the set of players who change their strategy during the walk, that is, $𝒞\mathscr{H}=\{i\in V:{\sigma }_i^F\ne {\sigma }_i^S\}$. Using the same approach as in the previous section, we obtain the following linear program $LP({\sigma }^S,{\sigma }^F,{\sigma }^{\ast })$:

Inequalities (9) state that for each player $i\in V$ not changing her strategy, and any color $l\in K,l\ne {\sigma }^S(i)$, the utility she is gaining at the time she is processed by the walk is at least $1+ϵ$ times the one she would get by choosing color $l$. Inequalities (10) ensure that each player $i\in 𝒞\mathscr{H}$ has an $(1+ϵ)$-approximate improving deviation in ${\sigma }_S(i)$ (although the definition of improving deviations requires the inequality to be strict, this simplification is without loss of generality). Moreover, differently from the cut game (i.e., $k$-coloring games with $k=2$), an agent may have several different such deviations. To model the dynamics in which each player is changing strategy to the one that is the most promising at the time it is processed, inequalities (11) are required.