{'fraction_non_alphanumeric': 0.04450199203187251, 'fraction_numerical': 0.00796812749003984, 'mean_word_length': 3.9972128210232927, 'pattern_counts': {'":': 0, '<': 2, '<?xml version=': 0, '>': 2, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
The Price of Anarchy in Hypergraph Coloring Games

The price of anarchy was introduced to measure the loss incurred by a society of agents who take actions in a decentralized manner instead of through a central authority. Hypergraph coloring has traditionally been studied in the context of a central designer who chooses colors. In this paper we study the price of anarchy when the choice of color is delegated to each of the vertices which are assumed self-interested.


Introduction
Consider a population of n agents where each agent is a member in various coalitions (subsets of the agents). Each agent derives some utility from each coalition it is a member of and its overall utility is the sum of these. To put this in economic context one can think of agents as individuals and coalitions as social circles (family, work, childhood friends, etc.). Alternatively, agents can be thoughts of as conglomerates who operate in many markets while a coalition consists of the competitors in any given market. A different motivation is when agents are broadcasting posts (e.g., cellular antennas) and a coalition is the set of posts that can communicate (are in the communication range) of any single consumer of the broadcasting services.
Abstractly, each agent choose one of finitely many 'colors' and the utility agents derive in each coalition is a function of the choice of colors of the coalition members. Colors could be interpreted as a fashion choice in the social context, a pricing choice (or any other dimension of business strategy) in the conglomerates example and a choice of frequency in the broadcast context.
We consider agents that are homogeneity-averse, that is agents who prefer to be somewhat different than their coalition peers. We provide two formulations for homogeneity aversion and study the equilibrium existence and price of anarchy in the induced games. Homogeneity aversion comes up naturally in a variety of settings of which fashion, business strategy and frequency choice are concrete examples.
The theme of frequency allocation in cellular networks is studied within the discipline of combinatorics and discrete and computational geometry (see Even et al. [3] and Smorodinsky [11] among others). In this line of work, colors (frequencies) are dictated by some central authority and agents' interest are ignored. In contrast, we study the color allocation resulting from distributed choice of colors or frequencies by self-interested agents. Throughout the rest of the paper we adopt the standard jargon used in combinatorics which we now introduce.
A hypergraph is a pair (V, E) where V is a set and E is a collection of subsets of V . The elements of V are called vertices and the elements of E are called hyperedges. When all hyperedges in E contain exactly two elements of V then the pair (V, E) is a simple graph. H = (V, E) is called r-uniform if |e| = r for all e ∈ E. So, in this terminology, a 2-uniform hypergraph is a simple graph. We say that H = (V, E) is r-minimal if |e| ≥ r for all e ∈ E. We denote by H r the set of all r-uniform hypergraphs and by H ≥r the set of all r-minimal hypergraphs. For We denote by C(k) the set of all k-colorings. For a given k-coloring c and a hyperedge e ∈ E, let c(e) ⊂ [k] be the image of e, i.e., the set of colors associated with the vertices in e.
A k-coloring c of H is called proper or non-monochromatic if every hyperedge e ∈ E with |e| ≥ 2 is non-monochromatic. That is, |c(e)| ≥ 2. Let χ(H) denote the least integer k for which H admits a proper coloring with k colors. A coloring c is called a conflict-free coloring (CF-coloring for short) if every hyperedge e ∈ E contains at least one uniquely colored vertex. More formally, for every hyperedge e ∈ E there is a vertex x ∈ e such that ∀y ∈ e, y = x ⇒ c(y) = c(x). Let χ cf (H) denote the least integer k for which H admits a CF-coloring with k colors. Obviously, every CF-coloring of H is also a proper coloring of H. Hence, we have the following inequality: Notice that for simple graphs and 3-uniform hypergraphs, theses two notions of coloring (non-monochromatic and CF ) coincide. both notions of proper coloring and of CF-coloring of hypergraphs generalizes the classical notion of a proper coloring of a graph. The notion of CF-coloring was first introduced and studied in [3] and [11]. The main motivation to study such CF-colorings comes from the problem of frequency allocation in wireless networks. In such networks, on one hand there is a need to avoid "conflicts", that is, mutual interference occurring when antennas with close proximity use the same frequency and on the other hand to minimize the total spectrum of frequencies used since the spectrum of frequencies is expensive and limited. The notion of CF-coloring attracted many researchers and has been the focus of many follow-up research papers both in the computer science and mathematics communities. For more on this notion and its motivation, we refer the reader to the survey [12].
In the aforementioned literature the assignment of colors to vertices is done by a central authority. In contrast, here we assume that the vertices are self-interested agents and study the consequences when each agent chooses her own color. The outcome obtained by self interested agents need not be optimal and so we resort to the price of anarchy as a measure of the potential resulting inefficiency of the system (see below for the exact definition).
In our model each vertex is viewed as a self-interested agent that is endowed with a utility function it seeks to maximize. In particular, we consider two variants of homogeneityaversion which are the natural analog of the above two coloring notions: • A weak notion of homogeneity-aversion is when each vertex gains, in a given hyperedge, when there is at least one other vertex in the hyperedge with a different color.
• A strong notion of homogeneity-aversion is when a vertex gains, at a given hyperedge, only when its color is different from the colors of all other vertices in that hyperedge.

Related literature
Over the recent decade or more there has been a large interest in the community of computerscience and game-theory to study the implications of distributed computing with self interested agents. This had led to the the development of the prosperous discipline known as algorithmic game theory (AGT). To read more about AGT we refer the reader to [9]. One particular aspect of study within the AGT community is the ratio between the optimal outcome of a distributed computing when the choice of action for each agent is dictated centrally and that when agents are delegated the choice of action. This is known as the Price of Anarchy (PoA), introduced in [5]. In particular the PoA for coloring games over simple graphs, when agents are homogeneity averse, has been studied in [6]. For other variants of the graph coloring game, see, e.g., [2,1,4,8,10].

Our results
Before presenting our results, we need to introduce several terms. Let H = (V, E) be a hypergraph. In what follows we sometimes refer to the vertices in V as agents or players. We view the set of vertices of a hypergraph as self interested agents. As mentioned above, we endow each agent with a utility function u v : C(k) → R and study the implication of distributed colorings, where each agent chooses her own color in order to maximizes her utility. The social welfare of a k-coloring c, denoted SW (c) = v∈V u v (c), is the sum of the agents' utilities.
A coloring c is called a (pure) Nash equilibrium if no player can increase her utility by a unilateral change. Formally, denotes the coloring c with agent v substituting her color to i).
For a hypergraph H and an integer k ≥ 2, put O(H, k) = max{SW (c) | c ∈ C(k)}. Put N E(H, k) = min{SW (c) | c ∈ C(k) is a Nash Equilibrium of H}. When the number of colors k is known and is clear from the context, we sometimes abuse the notation and write O(H) and N E(H) instead.
For a given integer k ≥ 2 and a given family of hypergraphs H we define the Price of Anarchy as P oA = P oA(H, k) = sup (H∈H) We study the following two utility functions and provide upper and lower bounds on the price of anarchy in terms of two parameters: The number of available colors k and the hyperedge size, r.

1.
A vertex is called non-monochromatic seeking (a NM-vertex in short) if its utility function is given by In words, a vertex enjoys each hyperedge in which its color differs from at least one other vertex. Put differently, the utility function of v is the number of non-monochromatic hyperedges containing v. For this utility function we prove the following exact bound on the price of anarchy: For the utility function u v : In words, v enjoys each hyperedge for which its color differs from the colors of all other vertices in that hyperedge.
Note that for simple graphs (i.e., r = 2) the two utility functions coincide.

Organization of the paper
In Section 2 we study the price of anarchy for the non-monochromatic game with respect to all r-minimal hypergraphs and prove Theorem 1.1. In Section 3 we study the price of anarchy for the conflict-free coloring game with respect to all r-uniform hypergraphs and prove Theorem 1.2. Finally in Section 4 we conclude with a discussion on other utility functions and present several open problems.

Non-monochromatic seeking agents
Let H = (V, E) be a hypergraph and c a coloring of its vertices. recall that the utility function of NM-vertices is given by Potential function: Let H = (V, E) be a hypergraph and let u v (c) be a utility function. A potential function for H is a function ψ : C(k) → R such that for any two colorings c, c ∈ C(k) if c and c differ only on one vertex v ∈ V then The following lemma is well known (see, e.g., [7]): Let H be a hypergraph and u a utility function. If H admits a potential function ψ with respect to u then there exists a pure Nash equilibrium for the corresponding coloring game.
Claim 2.2. For an integer k, a hypergraph H = (V, E) and a coloring c ∈ C(k), let ψ(c) be the number of non-monochromatic hyperedges in E. Then ψ is a potential function for the corresponding coloring game.
The proof of claim 2.2 is straightforward and hence omitted. Note that Lemma 2.1 combined with claim 2.2 implies that the game played among NM-vertices admits a pure Nash equilibrium and, furthermore, that the best Nash equilibrium attains the social optimum. However, other Nash equilibria may entail low social welfare. Theorem 1.1 provides a bound the performance of a Nash equilibrium coloring over r-minimal hypergraphs. In what follows we prove the Theorem.
The proof will make use of the following notations and a Lemma: For an r-minimal hypergraph H = (V, E), a k-coloring c of H and a vertex v ∈ V we define the following four parameters: is the number of hyperedges containing v with exactly two colors, of which one vertex distinct from v has a unique color.
) is the number of hyperedges containing v that do not fall into any of the first three categories.
We denote by D i = D i (c) = v∈V d i (v) the corresponding sums. Note that for r = 2, the set of hyperedges in E(v) counted in d 1 (v) is identical to the set counted in d 3 (v) whereas for r ≥ 3 those two sets are disjoint.
We need the following lemma: 3. Let r ≥ 3 and let H be an arbitrary hypergraph in H ≥r . For any coloring c we have: counts the total number of hyperedges in e ∈ E(v) with |c(e)| = 2 so that there is vertex v ∈ e whose color is distinct from all other vertices in e. Note also that any hyperedge e ∈ E with this property is counted exactly once in some d 1 (v) and at least r − 1 times in . Following a deviation of v from c(v) to some other color i = c(v) will increase the utility by d 2 (v) (the corresponding hyperedges that are monochromatic will cease to be so) but will simultaneously decrease the utility by d i 1 (v). As c is a Nash equilibrium the net increase cannot be positive and so d i The asserted inequality follows by summing over all v.
We now turn to the proof of Theorem 1.1: Proof of Theorem 1.1. The proof has two parts. First we show that P oA ≤ 1 + 1 (k−1)r and then we show that P oA ≥ 1 + 1 (k−1)r by providing an explicit construction of an r-uniform hypergraph H and a Nash equilibrium coloring c for which O(H) SW (c) = 1 + 1 (k−1)r . Upper Bound: Let H be an arbitrary hypergraph in H ≥r and let c be a Nash equilibrium coloring that minimizes the social welfare SW (c) over all Nash equilibria so N E(H) = SW (c). Let On the other hand, as noted in the proof of Lemma 2.3, . As the enumerator is larger than the denominator this expression is monotonically decreasing in D 3 and D 4 . As D 4 ≥ 0 (k−1)r as asserted. Lower Bound: The following construction proves that P oA ≥ (1 + 1 (k−1)r ): Let A 1 , . . . , A k be k pairwise disjoint sets each containing exactly r − 1 elements. put S = k i=1 A i . We first construct an auxiliary r-uniform hypergraph G = (S, E ) as follows: E consists of all r-tuples of the form So there are a total of k(r − 1) vertices and k(k − 1)(r − 1) hyperedges and each vertex belongs to exactly r(k − 1) hyperedges. We now construct the r-uniform hypergraph H = (V, E) by taking r disjoint copies of G denoted G i = (S i , E i ) and adding for every original vertex of v ∈ S a hyperedge consisting of all r copies of v. Formally, V = r j=1 S j so |V | = r(r − 1)k. Put E 1 = r j=1 E j . For a vertex v ∈ S, let {v 1 , . . . , v r } be the set of its copies in V . Put Figure 1 for an illustration. Note that each vertex in V belongs to exactly one hyperedge of E 2 and r(k−1) hyperedges of E 1 .
Consider the following k-coloring c. A vertex v ∈ V is colored i if and only if it is a copy of vertex in G that belongs to A i . For this coloring the hyperedges in E 1 are all nonmonochromatic. However, those in E 2 are all monochromatic. Therefore u v (c) = r(k − 1) and SW (c) = |V |r(k − 1). Note that any unilateral change in the color of v adds a nonmonochromatic hypergraph to E 2 but reduces the number of nonmonochromatic hyperedges in E 1 by 1 as well and hence is not profitable. Therefore c is a Nash equilibrium coloring.
On the other hand we can properly color this hypergraph by taking the coloring c and make a cyclic shift in the colors for S 1 where all vertices of A i are colored with i + 1 mod k. Denote the resulting coloringc. As this is a proper coloring, uc(v) = r(k − 1) + 1 for each v ∈ V . This, in turn, implies that SW (c) = |V |(r(k − 1) + 1).
Note that for this hypergraph O(H) which proves that P oA(H, k) ≥ 1 + 1 (k−1)r . Theorem 1.1 complements results obtained in [6] who provide a bound of k k−1 for graphs (namely for the case where r = 2). Note that our bound does not coincide with theirs. The reason is that (as mentioned already) the hyperedges counted by the parameters d 1 (v) and d 3 (v) coincide for the case r = 2 whereas they are pairwise disjoint whenever r ≥ 3. Once we notice this our technique reaffirms the bound obtained in [6].

Conflict-Free seeking agents
Let H = (V, E) be a hypergraph and c a coloring of its vertices. Recall from Section 1.2 that a vertex is called a CF-vertex if its utility function is u v (c) = |{e ∈ E(v) | |c(e)| = |c(e \ {v})| + 1}|. In words, the utility of a vertex v ∈ V is the number of hyperedges containing v for which the color of v is "unique" in e, that is, it is not assigned to any other vertex in e. For any coloring c and a hyperedge e ∈ E, put ϕ(c) = e∈E |c(e)|.
We also need the following lemma which provides a bound onĵ when c is a Nash Equilibrium: Note that the left hand side of the inequality satisfies: while the right hand side satisfies the following: By inequality 1 this later quantity is greater or equal |E|r(k − r) +ĵ r 2 . Hence, |E|r(k −1)−ĵ(k −1) ≥ |E|r(k −r)+ĵ r 2 . Rearranging terms we obtain the asserted bound.
(ii) Note that for any v ∈ V and for any i = c(v) the sum e∈E L(e, v, i) + M (e, v, i) is the utility of v and for i = c(v) the sum e∈E L(e, v, i) + M (e, v, i) equals zero. Therefore, Hence, by equation 2 we have: Dividing by k − 1 on both sides and resorting to the upper bound we have obtained for j in part 1 of the lemma we can conclude that SW (c) ≥ |E|r − |E|r(r−1) r 2 +k−1 . Rearranging terms yields the asserted inequality. This completes the proof.
We are now ready to proceed with the proof of the upper bounds of Theorem 1.2 which follows easily from Lemma 3.2: Proof. Let H be an arbitrary r-uniform hypergraph. Let c be a Nash-equilibrium k-coloring so that SW (c) attends N E(H). By Lemma 3. Proof of the lower bound in part 1 of Theorem 1.2: We lower bound the price of anarchy using the following construction. Consider an r-uniform r-partite hypergraph H = (V, E) as follows.
} is a set of cardinality k. A hyperedge is any subset of r elements in V consisting of exactly one vertex from each A i so there are exactly k r hyperedges and each vertex belongs to exactly k r−1 hyperedges. Consider the coloring c(v i,j ) = j. That is, every set A i is colored with all the k colors. Note that the utility of all vertices equals (k − 1) r−1 . It is easily seen that when a vertex, say v i,j , changes its color to, say l, then its utility does not change. Therefore, this coloring is a Nash equilibrium. Thus, the social welfare of this Nash equilibrium is (kr)(k − 1) r−1 .
On the other hand consider the coloring where all vertices of the set A i are colored with i ( so we use a total of r of the k given colors). Notice that for this coloring the social welfare of every vertex equal the number of hyperedges containing it, that is k r−1 . So for this coloring, the social welfare is (kr)k r−1 Dividing the two gives us the asserted lower bound as P oA(H) = O(H) N E(H) ≥ (kr)k r−1 (kr)(k−1) r−1 = ( k k−1 ) r−1 where the inequality follows from the fact that N E(H) ≤ (kr)(k − 1) r−1 .
Proof of the lower bound in part 2 of Theorem 1.2: We resort to the same example that we use for demonstrating a lower bound for the case k ≥ r. As before, the coloring c(v ij ) = j is a Nash equilibrium with SW (c) = (kr)(k − 1) r−1 . Consider also the coloring c where all vertices of the set A i are colored with i for 1 ≤ i ≤ k−1 and with k for k ≤ i ≤ r. Note that each vertex in A i (1 ≤ i ≤ k − 1) gets a utility of k r−1 and each other vertex gets a utility zero. So SW (c ) = k(k − 1)k r−1 . Hence: Proof of part 3 of Theorem 1.2: Let H be the hypergraph with r vertices all of which form the unique hyperedge of H. The socially optimal coloring assigns k − 1 vertices a unique color and the rest of the vertices the remaining color. On the other hand in a coloring which assigns vertices (i, 2i) the color i, for i = 1, . . . , k and vertices 2k + 1, . . . , r color 1 forms a Nash equilibrium coloring where no agents gains and so its social welfare is zero. 2

Discussion and Open Problems
In this paper we depart from the traditional literature on graph and hypergraph coloring and consider a setting where the choice of colors is delegated to the individual vertices, where each vertex is identified with a self-interested agent. Thus, a vertex chooses its color in order to maximize some utility function. A specification of a hypergraph, a set of colors and the utility functions induces a non-cooperative game. We associate with each such game its Nash equilibrium outcome. Whereas individual vertices act optimally in such an equilibrium the overall implications on the society need not be optimal. The PoA measures the loss from the decentralized approach.
The distributed setting we propose and the corresponding game-theoretic approach entail a variety of interesting research questions, some of which we discuss below. We view this paper as a humble stepping stone to a potentially rich research domain.
Any instance of the problem is identified by a specification of the utility function that each vertex is endowed with, a structure on the set of hypergraphs under study and a specification of a social welfare function. In this paper we focus on two specific utility functions (nonmonochromatic and conflict-free seeking), we consider the set of r-minimal and r-uniform hypergraphs and we restrict attention to the most prevalent social welfare function which is just the sum of utilities across all vertices.
For non-monochromatic seeking agents we provide a tight bound on the PoA for rminimal hypergraphs. In particular, the bound we obtain demonstrates that there is almost no loss of social welfare when decisions are decentralized as long as either the number of colors or the size of the minimal hyperedge is large enough. For conflict-free seeking agents the bound on the PoA we provide is not tight and hence calls for further research. When the size of the hyperedges is roughly α times the number of available colors (k = αr) ) and is large we provide an upper bound of 2+α 2−α whenever α ≤ 1 and a bound of 2+α α(2−α) for 1 < α < 2 (for α ≥ 2 the PoA is infinite). On the other hand the lower bounds we have for large k and r are exp α for the former case and exp α α for the latter case. In particular for the case α = 1 (namely, k = r) we have e ≤ P oA ≤ 3. We hope that further research will help close this gap.
We assert that the analysis of the PoA in hypergraph coloring games is of interest beyond the two utility functions that we study in this paper. Note that the common feature of these two utility functions is that each vertex' utility is additive in the sense that it is obtained by summing the utility derived from each hyperedge separately. Inspired by this, there are various other utility functions that come to mind. For example: • Consider the case where a vertex v enjoys a utility of 1 from each hyper-edge in which he is the unique vertex with a unique color. Each such hyperedge represents a situation where the vertex has some monopoly power it can exert. Unfortunately, nothing meaningful can be said for any pair r, k such that r > 2 and k > 2. Indeed, consider a hypergraph with only one hyperedge e with r vertices. Any coloring which has at least two unique colors in e (say all vertices are colored by 3 except for two vertices x and y such that x is colored with 1 and y is colored with 2) forms a Nash equilibrium for which no vertex gains more than zero. On the other hand coloring one vertex by 1 and all the rest by color 2 provides a social welfare equal to 1. Since the ratio between the two is infinite the price of anarchy is unbounded.
• Assume a vertex enjoy a positive utility if its color is unique, however the utility is proportional to the number of such vertices in an edge. This represents a setting here only vertices of a unique color can enjoy some benefit but this benefit is distributed equally among all those unique ones.
• A third natural candidate for a utility function is one where each vertex enjoys a hyperedge whenever that hyperedge has some vertex with a unique color (or maybe even a single vertex with a unique color).
Orthogonal to the question of which utility function the vertices are endowed with, there is the question on the domain of hypergraphs. In this paper we paid attention to r-uniform and r-minimal hypergraphs however there are other natural families of hypergraphs that are of interest. For example, geometric hypergraphs induced by, say, discs in the plane (see, e.g., [12]) which arise in the context of frequency assignment in wireless networks.
Most of the literature on the price of anarchy, similar to our approach, identifies the societal objectives with the sum of agents' utilities (the social welfare) and hence the PoA is defined as a ratio between the social welfare in the two cases -centralized vs. decentralized decision making. However, often there are other ways to define the objective of the society which would induce an alternative formulation for the PoA. Consider, as an example, the motivating example of frequency assignment. The overall objective in that case could be to provide service to as many customers as possible. This would translate to maximizing the number of hyperedges containing a vertex which color is unique. However, from the individual vertex point of view it would like to maximize the number of hyperedges for which its own color is unique (CF-seeking). Note that in this case the social welfare does not coincide with the societal objective function and consequently the bounds on the induced PoA could be different from those obtained in Theorem 1.2.
Finally, let us propose an alternative, yet closely related, notion to the PoA. Given a hypergraph let us define the 'coloring burden of anarchy' as the ratio between the number of colors required to obtain a conflict-free coloring in an equilibrium of the game in which vertices choose their own color and the minimal number of colors required to obtain conflictfree coloring when colors are dictated centrally (χ cf (H)). More broadly the notion of 'coloring burden of anarchy' could refer to the ratio in the number of colors for obtaining some social criterion between the decentralized and the centralized cases.