{'fraction_non_alphanumeric': 0.04065061475409836, 'fraction_numerical': 0.004277663934426229, 'mean_word_length': 4.415591621584131, 'pattern_counts': {'":': 0, '<': 4, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Pure Nash Equilibria: Complete Characterization of Hard and Easy Graphical Games

We consider the computational complexity of pure Nash equilibria in graphical games. It is known that the problem is NP-complete in general, but tractable (i.e., in P) for special classes of graphs such as those with bounded treewidth. It is then natural to ask: is it possible to characterize all tractable classes of graphs for this problem? In this work, we provide such a characterization for the case of bounded in-degree graphs, thereby resolving the gap between existing hardness and tractability results. In particular, we analyze the complexity of PUREGG(C, -), the problem of deciding the existence of pure Nash equilibria in graphical games whose underlying graphs are restricted to class C. We prove that, under reasonable complexity theoretic assumptions, for every recursively enumerable class C of directed graphs with bounded in-degree, PUREGG(C, -) is in polynomial time if and only if the reduced graphs (the graphs resulting from iterated removal of sinks) of C have bounded treewidth. We also give a characterization for PURECHG(C,-), the problem of deciding the existence of pure Nash equilibria in colored hypergraphical games, a game representation that can express the additional structure that some of the players have identical local utility functions. We show that the tractable classes of bounded-arity colored hypergraphical games are precisely those whose reduced graphs have bounded treewidth modulo homomorphic equivalence. Our proofs make novel use of Grohe's characterization of the complexity of homomorphism problems.


INTRODUCTION
There has been recent interest in using game theory to model and analyze large multi-agent systems such as network routing, peer-Cite as: Pure  to-peer file sharing, auctions and other market mechanisms. One fundamental class of computational problems in game theory is the computation of solution concepts of a finite game, such as Nash equilibria. These kinds of computational tasks can be understood in the language of AI as reasoning about the game: what are the likely outcomes of the game, under certain models of rationality of the agents? The goal is to be able to efficiently carry out such reasoning for real-world systems.
Much of the existing game theoretic literature models simultaneous action games using the normal form (also known as the strategic form), i.e. a game's payoff function is represented as a matrix with one entry for each player's payoff each combination of the actions of all players. The size of this representation grows exponentially in the number of players. Computations that are "polynomialtime" in the input size are nevertheless impractical. As a result the normal form is unsuitable for representing large systems.
Fortunately, most real-world large games have highly-structured utility functions, which allows them to be represented compactly. A line of research thus exists looking for compact game representations that are able to succinctly describe structured games, and efficient algorithms for computing solution concepts that run in time polynomial in the size of the representation. An influential compact representation of games is graphical games proposed by Kearns et al. [16]. A graphical game is associated with a graph whose nodes correspond to the players of the game and edges correspond to payoff influence between players. In other words, each player's payoffs depend only on the actions of himself and his neighbors in the graph. The representation size of a graphical game is exponential in the size of its largest neighborhood. This can be exponentially smaller than the normal form representation of the same game, especially for sparse graphs.
A compact game representation is not very useful if we cannot perform computations that are efficient relative to its size. In this paper we focus on the problem of computing pure-strategy Nash equilibria (PSNE). Unlike mixed-strategy Nash equilibria, which are guaranteed to exist for finite games [18], in general pure Nash equilibria are not guaranteed to exist. Nevertheless, in many ways pure Nash equilibrium is a more attractive solution concept than mixed-strategy Nash equilibrium. First, pure Nash equilibrium can be easier to justify because it does not require the players to randomize. Second, it can be easier to analyze because of its discrete nature (see, e.g., [2]). Gottlob et al. [11] were the first to analyze the problem of computing pure Nash equilibria in graphical games. They proved that the problem is NP-complete in general, even when the graphs have neighborhood size at most 3. On the other hand, for games with graphs of bounded hypertree-width there exists a dynamic-programming algorithm that determines the existence of pure Nash equilibria in polynomial time in the size of the representation. Daskalakis and Papadimitriou [7] reduced the problem of finding pure strategy Nash equilibrium in graphical games to a Markov Random Field (MRF), and then applied the standard clique tree algorithm to the resulting MRF. Among their results they showed that for graphical games on graphs with logsized treewidth, bounded neighborhood size and bounded number of actions per player, deciding the existence of pure Nash equilibria is in polynomial time.
A natural question arises: are there other tractable classes of graphical games? Such a tractable class can be defined by restrictions over the graph structure as well as the local utility functions.
In this paper, we analyze the complexity of PURE-GG(C, −), the problem of determining the existence of pure Nash equilibria in graphical games whose underlying digraphs 1 are restricted to class C (while other aspects of the game representation can be arbitrary). We say C is tractable if PURE-GG(C, −) is in polynomial time.
Throughout the paper we make the restriction that the graphical games have bounded neighborhood size (i.e. bounded in-degree). Graphical games with large in-degree have the same problem as normal form games: even if we find polynomial-time algorithms for them, that would still be impractical due tb the large input size.
Previous results [11,7] do not answer whether bounded treewidth is the sole measure of tractability of PURE-GG(C, −). For example, it was unknown whether games with log-sized treewidth and unbounded number of actions per player are tractable. Furthermore, there are other graph parameters that affect the tractability of certain computational problems on directed graphs, e.g. directed tree-width [15], D-width [20], DAG-width [19], and Kelly-width [13]. Since these parameters take advantage of the directionality of the edges, they could potentially give a better characterization of the tractability of PURE-GG(C, −).
In this paper we give a complete characterization of the tractable classes of bounded-indegree graphs, thereby resolving the gap between existing tractability and hardness results. Our results are summarized below.
1. Bounded-treewidth graphs are not the only tractable kind of digraphs. One example is graphical games on DAGs, for which pure equilibria always exist and can be computed efficiently. More generally, whenever there is a sink (a vertex with out-degree zero), the utilities for that sink player do not affect the existence of pure equilibria.
2. Given a digraph G, let its reduced graph be the graph obtained by iterated removal of sinks. We prove that, under reasonable complexity theoretic assumptions, for every recursively enumerable class C of directed graphs with bounded in-degree, PURE-GG(C, −) is in polynomial time if and only if the reduced graphs of C have bounded treewidth.
3. We consider colored hypergraphical games, a new game representation based on colored hypergraphs, which can express the additional structure that some of the players have identical local utility functions. For the pure equilibrium problem on this representation PURE-CHG(C, −), we show that a class of colored hypergraphs is tractable if and only if its reduced graphs have bounded treewidth modulo homomorphic equivalence. This is a wider family of tractable games com-pared to the graphical game representation. That is, by incorporating more information about the structure of the game into the graph, we are able to identify new tractable classes of games.
Our results for PURE-GG(C, −) follow as a corollary to our results for PURE-CHG(C, −). Another corollary is that if the graphical games are represented as undirected graphs, then the tractable classes of undirected graphs are precisely those with bounded treewidth. We prove these results by connecting PURE-GG(C, −) and PURE-CHG(C, −) to homomorphism problems, which given colored hypergraphs G and H, ask whether there exists a homomorphism from G to H. We then make use of Grohe's [12] breakthrough result that characterizes the tractable classes of HOM(C, −), homomorphism problems with restricted left-hand side. This is (as far as we know) a novel application of Grohe's result for homomorphism problems to computational problems in game theory. We prove our main tractability result by reducing an arbitrary instance of PURE-CHG(C, −) to an instance of the homomorphism problem. This reduction has a similar structure as [11]'s formulation of graphical games as constraint satisfaction problems. On the other hand, our proof for our hardness result is quite unlike the existing NP-hardness proof for graphical games [11]. At a high level, this is because the previous approach would construct graphical games on graphs with a certain specific structure. This is sufficient for proving NP-hardness, but not for our purposes, because we want to characterize the complexity for PURE-CHG(C, −) for arbitrary C, which implies that we had to instead construct our graphical/colored hypergraphical game on an arbitrarily given digraph/colored hypergraph. In other words, we only have control over the utility functions (but not the graph structure), and need to set the utilities such that there is a solution to the given homomorphism problem if and only if the game has a pure equilibrium. This makes our task more technically challenging. We think our proof techniques may have wider interest; for example, it might be possible to extend these techniques to prove similar results for action-graph games [1], another compact game representation.
These results increase our understanding of the power and limitations of the graphical game representation, and have immediate practical impact. Specifically, they imply that if the systems we are interested in have large-treewidth reduced graphs when modeled as graphical games, then the resulting graphical games are unlikely to admit an polynomial-time algorithm for pure Nash equilibria, even if the graphs have other types of structure. Nevertheless, if some of the players have identical utility functions, we might be able to get around this limitation of graphical games by representing the systems as colored graphical games instead. If the corresponding reduced graphs have bounded treewidth modulo homomorphism equivalence, pure Nash equilibria can be found efficiently by transforming to the corresponding homomorphism problems which have known polynomial-time algorithms [5,12].

Graphical Games
A (simultaneous-move) game is a tuple (N, {Si}i∈N , {ui}i∈N ) where N = {1, . . . , n} is the set of agents; for each agent i, Si is the set of i's actions. Si is nonempty. An action profile s ∈ i∈N Si is a tuple of actions of the n agents. ui : j∈N Sj → R is i's utility function, which specifies i's utility given any action profile.
For every action profile s, let si be the action of agent i under this action profile, and s−i be the (n − 1)-tuple of the actions of agents other than i under this action profile. For each action s ′ i ∈ Si, let (s ′ i , s−i) be the action profile where agent i plays s ′ i and all the other agents play according to s−i.
A game representation is a data structure that stores all information needed to specify a game.
• for each i ∈ N , a local utility function Ui : Each local utility function Ui is represented as a matrix of size Since the size of the local utility functions dominates the size of the graph G, the total size of the representation is O(nm (I+1) ) where I is the maximum in-degree of G and m = maxj∈N |Sj|.
A graphical game (G, {Ui}) specifies a game (N, {Si}, {ui}) where each Si is specified by the domain of agent i in Ui, and for all i ∈ N and all action profile

Colored Hypergraphical Games
We now consider graphical games with a certain additional structure. Specifically, some players may have identical local utility functions. 2 To represent this kind of structure, we not only need to specify which players have the same local utility function, we also need to specify an ordering of the vertices in each neighborhood. We express this kind of structure graphically using colored hypergraphs.
A colored hypergraph H = (V, E, C) consists of a set of vertices V , a set of edges E where every edge e ∈ E is an ordered tuple of vertices in V , 3 and a color function C : E → τ that maps each edge to its color. In other words, each edge e ∈ E is labeled with a color C(e). We denote as V (H), E(H) and CH the set of vertices, set of edges and the color function of colored hypergraph H, respectively.
We are now ready to define colored hypergraphical games. Intuitively, in a colored hypergraphical game, the players affecting player i's utility are represented as a colored hyperedge consisting of these players' vertices, with i being the first element. If two hyperedges have the same color, it means that their corresponding local utility functions are identical.
• the set of vertices V (G) = N corresponds to the set of players; • for each vertex v ∈ N , there exists exactly one edge e ∈ E that has v as the first element. Denote this edge as ev.
• for each color c ∈ τ , edges of color c have the same arity 4 Ic.
• for each color c, Uc : [m] Ic → R. Unlike graphical games, where given an arbitrary digraph G there is a graphical game on G, not all colored hypergraphs have corresponding colored hypergraph games. Let Σ be the set of colored hypergraphs of colored hypergraph games.
Given G ∈ Σ, we define its induced digraph D(G) to be a digraph on the same set of vertices; and for each hyperedge Graphical games can be thought of as special cases of colored hypergraph games where each neighborhood has a different local utility function, i.e. a different color. Given a directed graph G = (V, E), we define its induced colored hypergraph H(G) = (V, E , C) such that its set of colors is V and for each vertex v ∈ V , there is a hyperedge e ∈ E of color v, consisting of vertices in N (i), with v being the first element in the tuple e. The rest of the vertices in e is sorted in a pre-determined order over V . In particular, if the vertices correspond to the agents 1, . . . , n in a game, we require these vertices to be sorted in ascending order of the agents. For notational convenience, given a class of directed graphs C, let H(C) be the class of induced hypergraphs of the directed graphs in C.
There is one graph often associated with any hypergraph: the primal graph. Given a colored hypergraph H, its primal graph pri(H) is an undirected graph obtained by making a clique out of the vertices in every edge in H.
There are a couple of previous papers on the computational properties of graphical games with different notions of identical utility functions. Daskalakis et al. [6] analyzed the complexity of finding pure and mixed Nash equilibria of graphical games on highly regular graphs (namely the d-dimensional grid), in which all local payoff functions are identical. Brandt et al. [3] instead analyzed graphical games on arbitrary graphs, but with several stronger notions of symmetry. In contrast, the colored hypergraphical game formulation places the least amount of restrictions and is thus more likely to occur in practice. In fact, these previous formulations can be thought of as special cases of colored hypergraphical games.

Best Response and Pure Nash Equilibrium
Given a game (N, {Si}i∈N , {ui}i∈N ) and s−i, agent i's best response to s−i is BRi(s−i) = arg maxs i ∈S i ui(si, s−i). Since Si is nonempty, i has at least one best response given any s−i. Note that in a graphical game, the best response of i depends only on the actions of i's neighbors. DEFINITION 3. An action profile s ∈ i∈N Si is a pure Nash equilibrium of the game (N, {Si}i∈N , {ui}i∈N ) if each agent i ∈ N is playing a best response to s−i, i.e. si ∈ BRi(s−i).
We define PURE-GG to be the following decision problem: given a graphical game (G, {Ui}i∈N ), decide whether there exists a pure Nash equilibrium. Gottlob et al. [11] have shown that this problem is NP-complete in general. Given a class C of digraphs and class U of local utility functions, let PURE-GG(C, U) be the pure Nash equilibrium decision problem on graphical games when the graphs of the input game are taken only from class C and the local utility functions are taken only from class U. In this paper we are interested in problems of the form PURE-GG(C, −), which means that the local utility functions are unconstrained, other than the requirement that the input is a well-formed graphical game, i.e. that each Ui takes |N (i)| arguments.
Similarly, we define the problem PURE-CHG(C, −) to be the pure Nash equilibrium decision problem on colored hypergraphical games, with colored hypergraphs restricted to class C.

Treewidth
Due to space constraints we omit the standard definition of treewidth for undirected graphs (see, e.g., [17]). The treewidth of a digraph G is the treewidth of the undirected version of G. The treewidth of a colored hypergraph is the treewidth of its primal graph.

Homomorphism
Let G and H be two colored hypergraphs. A homomorphism from G to H is a mapping h from the vertex set of G to the vertex set of H that preserves both adjacency and color, i.e. for every edge e = (a1, a2, · · · , a k ) ∈ EG, h(e) = (h(a1), h(a2), · · · , h(a k )) ∈ EH and CG(e) = CH (h(e)). In a homomorphism problem, we are given G and H and have to decide whether there exists a homomorphism from G to H.
For two classes C and D of colored hypergraphs let HOM(C, D) be the homomorphism problem when the input colored hypergraphs are taken only from classes C and D. When an input class is the class of all colored hypergraphs, we use the notation '−' instead.
Two hypergraphs G and H are homomorphically equivalent if there is a homomorphism from G to H and vice versa. A class C has bounded treewidth modulo homomorphic equivalence if there exists some constant k such that every hypergraph in C is homomorphically equivalent to a hypergraph with treewidth at most k. For example the class of bipartite graphs have bounded treewidth modulo homomorphic equivalence as they are homomorphically equivalent to an edge. We use modulo-treewidth(G) to indicate the minimum k for which G is homomorphically equivalent to a hypergraph of treewidth k.

Parameterized Complexity Theory
Our results make use of certain concepts from he theory of parameterized complexity developed by Downey and Fellows [9]. They are not essential for understanding our reductions. We briefly mention the relevant concepts here and refer the reader to [9,10] for more details.
Given a decision problem P ⊆ Σ * , a parameterization of P is a mapping k : Σ * → N that defines the paramterized problem (P, k). A paramterized problem (P, k) is fixed parameter tractable if there is a computable function f : N → N and an algorithm that decides if a given instance x ∈ Σ * belongs to P in time f (k(x))|x| O(1) for some function f depending only on k. The class of all fixed parameter tractable problems is denoted by FPT.
Downey and Fellows [8] defined the paramterized complexity class W [1], which can be seen as an analogue of NP in parametrized complexity theory, and conjectured that FPT is a proper subset of W [1]. This conjecture is widely believed to be true.

Complexity of Homomorphism Problems
Grohe [12], in a breakthrough paper, characterizes the tractable instances of the homomorphism problem when we restrict the left input graphs. 5 THEOREM 5 (GROHE [12]). Assume FPT = W [1]. Then for every recursively enumerable class C of colored hypergraphs with bounded arity the following statements are equivalent. 1. HOM(C, −) is in polynomial time.

C has bounded modulo-treewidth.
Under a slightly stronger assumption of nonuniform-FPT = nonuniform-W [1], this result holds for arbitrary (not necessarily recursively enumerable) class C.

Digraphs with sinks
One's first intuition is to try and show a correspondence between PURE-GG(C, −) and HOM (H(C), −) for arbitrary classes of bounded-degree graphs. In fact such correspondence does not exist for arbitrary graphs. For example, a graphical game on a directed acyclic graph (DAG) always has a PSNE, which can be computed efficiently by a greedy algorithm that goes through vertices in the topological order, from sources to sinks. Consider the class D k of k-bounded in-degree DAGs. H(D k ) has unbounded modulotreewidth, however PURE-GG(D k , −) is in polynomial time. This is just an example of a more general phenomenon in graphical games. Let GG = (G, {Ui}i∈N ) be a graphical game. If G has a sink u (i.e. u has out-degree zero) then the action of u does not affect any other player. This means we can simply solve the game without player u and the resulting game has a pure Nash equilibrium if and only if GG has one. Intuitively, this is because in a graphical game (and any game in general) each player has at least one action, and as a result, whatever actions others chose, each player has at least one best response.
We formalize this intuition as the following classification of digraphs into reducible and irreducible graphs:

DEFINITION 6. A directed graph G is irreducible if it does not have a sink (a vertex with out-degree zero). Otherwise
It is often helpful to consider the strongly connected components (SCCs) of a directed graph. In particular, we can characterize irreducible graphs by their terminal SCCs.

LEMMA 8. If G is irreducible then all its terminal SCCs have size at least 2.
This is because otherwise, a vertex in a terminal SCC with only one vertex would have out-degree zero.
It turns out that for our purposes, given an arbitrary digraph we can focus on its subgraph resulting from iterative removal of sinks.  LEMMA 11. A graphical game GG has a pure Nash equilibrium if and only if its reduced game red(GG) has a pure Nash equilibrium.

LEMMA 12. Suppose C is a recursively enumerable class of graphs with bounded in-degree, such that PURE-GG(red(C), −) is in P. Then PURE-GG(C, −) is in P.
For the other direction, we would like to prove that if graphical games on a class of graphs C is tractable, then graphical games on red(C) is also tractable. This is not trivial, because although the reducible vertices of graphs in C do not affect the existence of pure equilibria, the subgraphs on these vertices could potentially carry information (similar to advice strings in complexity theory) such that PURE-GG(C, −) is easier than PURE-GG(red(C), −). It turns out that if we consider the parameterized version of the problem, then if p-PURE-GG(C, −) is in FPT then p-PURE-GG(red(C), −) is in FPT. This will be sufficient for our purposes. The proof of the following lemma is given in Appendix A.

LEMMA 13. Suppose C is a recursively enumerable class of graphs with bounded in-degree, such that p-PURE-GG(C, −) is in FPT. Then p-PURE-GG(red(C), −) is in FPT.
We can define analogous concepts for colored hypergraphs and colored hypergraphical games, by looking at their induced digraphs. A colored hypergraph G ∈ Σ is irreducible if and only if its induced digraph is irreducible. Given G ∈ Σ, its reduced colored hypergraph red(G) is obtained by removing all reducible vertices of the induced digraph of G and all hyperedges that include these reducible vertices. Reduced colored hypergraphical games can be defined similarly. Lemmas 12 and 13 can be straightforwardly extended to colored hypergraphical games.

Main Theorems
The above implies that for the complexity of PURE-GG(C, −) and PURE-CHG(C, −), it is sufficient to consider irreducible graphs. The complexity for a general class C then correspond to the complexity for red (C). It turns out that if we restrict to irreducible graphs, there exists a correspondence between PURE-CHG(C, −) and HOM (H(C), −). We are now ready to state our main result, which will be proved in the rest of Section 3: THEOREM 14. Assume FPT = W [1]. Then for every recursively enumerable class of bounded arity colored hypergraphs C ⊆ Σ, the following statements are equivalent.
We then obtain as a corollary the characterization for the complexity of PURE-GG(C, −). We make use of the following lemma on the modulo-treewidth of H(G).

LEMMA 15. Given a digraph G, the modulo-treewidth of H(G) equals the treewidth of H(G).
Furthermore, we can relate the treewidth of a digraph G to the treewidth of H(G). Daskalakis and Papadimitriou [7] showed that given an undirected graph H with bounded degree, the treewidth of its induced hypergraph H(H) and the treewidth of H are within a constant factor of each other. This result cannot be directly applied to digraphs, because the induced hypergraph of the undirected version of a digraph G can be different from H(G). Nevertheless, their proof can be relatively straightforwardly adapted to digraphs, yielding the following lemma. 3. for every G ∈ C, red(G) has bounded treewidth.
Comparing Theorem 14 and Corollary 17, CHGs gives a wider family of tractable games compared to graphical games. For example, the class of CHGs described in Example 4 has bounded modulo-treewidth but unbounded treewidth. Thus they would be intractable if represented as graphical games.
We also obtain as a corollary the characterization for the pure equilibrium problem for graphical games defined on undirected graphs. Define PURE-UGG(C, −) to be the problem of deciding existence of pure equilibrium on such undirected graphical games, restricted to the class of graphs C. Then under the same assumptions, C is tractable if and only if its graphs have bounded treewidth.

Proof of Tractability Result
We use the following lemma that reduces a colored hypergraphical game to a homomorphism problem instance. The tractability direction of Theorem 14 then follows straightforwardly. . For each color c, for each action tuple (a, a1, a2, · · · , ar) such that Uc(a ′ , a1, a2, · · · , ar) (i.e. a is a best response for a player with utility function Uc given neighbor actions (a1, a2, · · · , ar)), create an hyperedge (a, a1, a2, · · · , ar) of H ′ with color c.
If Γ has a pure Nash equilibrium then the mapping that maps each vertex u to the vertex a, where a is the action chosen by u in the pure Nash equilibrium, is a homomorphism. For the other direction, if H ′ is a homomorphism of G ′ and the corresponding mapping function is ℓ then ℓ(u) corresponds to an action of u, and for every edge e u = (u, u1, u2, · · · , ur) of color c in G ′ , ℓ(e u ) = (ℓ(u), ℓ(u1), ℓ(u2), · · · , ℓ(ur)) must be an edge of color c in H ′ . This implies that ℓ(u) is a best response action of player u against his neighbors' actions. Therefore, the mapping ℓ corresponds to a pure Nash equilibrium.
Since G ′ is identical to G, both maximum arity and modulotreewidth remain unchanged.

Hardness for graphical games
We first consider the hardness result for graphical games. In Section 3.5 we extend our approach to colored hypergraph games.
As mentioned in the introduction, applying the hardness proof approach of [11] to our setting would create graphical games with a particular structure, which is not sufficient for our purpose because we want to characterized the complexity of PURE-GG(C, −) given an arbitrary class C.We thus use a different construction in our proof of the hardness direction, which starts with an arbitrary class C of irreducible digraphs, constructs a bijective mapping to a class C ′ of colored hypergraphs, and then show that for any instance (G, H) of HOM (C ′ , −) we can construct an equivalent instance of PURE-GG(C, −). We can then apply Theorem 5 to get the hardness result.
The key step of the proof is the following lemma. Recall that given digraph G, H(G) is the colored hypergraph with hyperedge ei (the edge that corresponds to vertex i and its neighbors) being colored with color i.

LEMMA 19. Let G be an irreducible digraph. Then for any colored hypergraph H, there exists a graphical game GG = (G, {Ui}i∈N ) such that there is a homomorphism from H(G) to H if and only if GG has a PSNE.
The reduction is outlined as follows. (We give a detailed proof of the lemma in Appendix B.) Each player's action set consists of V (H) plus some "failure actions", in this case T and B. We define the utility for i, given a local strategy profile over N (i), such that if the local strategy profile correspond to a hyperedge in H of color i, then i gets a high payoff (say 100), such that if there exists a homomorphism from H(G) to H, then the corresponding strategy profile is a PSNE.
If the local strategy profile does not correspond to an edge of right color in H, we set the utilities so that player i is forced to play one of the failure actions. This implies that out-neighbors of i are forced to play failure actions, and so on. Now we just need to set utilities such that if at least one player plays failure actions, then no PSNE exists. Recall that if G was a DAG, then there always exists a PSNE; i.e. a game construction with no PSNE must contain a cycle. Fortunately G is assumed to be irreducible, which means that all of its terminal SCCs has a directed cycle of length at least 2. For each of the terminal SCCs, fix a cycle and set the utilities of players on that cycle (given failure actions of their neighbors) to be a generalization of the Matching Pennies game: one of the players is incentivized to play the opposite failure action as his predecessor in the cycle, while all other players on the cycle are incentivized to imitate their predecessors.
If there is no homomorphism, then for any strategy profile, there must be one player forced to play failure actions, which implies that at least one terminal SCC play failure actions, which implies that one of these cycles are playing the generalized Matching Pennies game, which does not have a PSNE.
Using Lemma 19, given an FPT algorithm for p-PURE-GG(C, −) we can construct an FPT algorithm for p-HOM(C ′ , −) where C ′ = {H(G)|G ∈ red(C)}. This implies the hardness direction for graphical games. We sketch a proof of the lemma in this section. At a high level, the main difficulty when extending our proof of Lemma 19 to colored hypergraphical games is that players with the same color must have the same utility function. Instead of being able to specify the utility function for each player in the graphical game case, now we need to define one utility function Uc for each color c. In fact, our generalized Matching Pennies construction for the graphical game case cannot be directly applied to colored hypergraphical game, and our proof of Lemma 20 instead uses a different construction involving 2n + 1 failure actions for each player.

Hardness for colored hypergraphical games
Part of the hardness proof for graphical games can be relatively easily adapted to colored hypergrahical games: each player's action set still consists of V (H) plus some failure actions (to be specified later). We set the utility function Uc so that if the input action tuple corresponds to a hyperedge of color c in H, then the utility is 100. This will ensure that if there exists a homomorphism, then the corresponding strategy profile is a PSNE. This concludes the proof of the "if" direction of Lemma 20.
The "only if" direction is more difficult. In particular, it is difficult to define the utilities for the failure actions in a way that respects the color constraints. For one, we would not be able to express the generalized Matching Pennies game now: in the worst case all players may have the same color. Also, we cannot specify a cycle and then define utility functions on that cycle in a way that ignore all edges not in the cycle: this would also require playerspecific utility functions.
Thus we want the utilities given failure actions to not depend on the player. For the simple case of a single cycle, the following construction is sufficient. (For notational convenience, we only specify the best response function BR, which maps a tuple of actions of the neighbors to a single action as the best response. Given the BR function the utilities can be defined straightforwardly.) LEMMA 21. Given a colored hypergraph G, whose induced digraph consists of just one cycle with length n, the following colored hypergraphical game on G does not have PSNE: • each player's actions are the integers 0, . . . , p − 1; • let BR(a) = (a + 1) mod p where p ≥ n + 1.
We omit the straightforward proof. If we think of BR as arcs from a to BR(a), then the digraph on actions form a p-cycle.
The intuition is that for each strategy profile, at least one neighbor is "activated" in the following sense: Given digraph G = (V, E), strat profile s, we say an edge (u, v) ∈ E is active if i.e. u's action under s is maximal among v's neighbors. Let G ′ be the subgraph of G where we only keep the active edges, i.e. for each player i, only keep the edge from the neighbor playing the highest action among neighbors. We claim that G ′ must contain a cycle, i.e. is not a DAG. This is because G is strongly connected, which means it has no source, i.e. all vertices of G have positive number of incoming edges. This implies that all vertices of G ′ have positive number of incoming edges, i.e. G ′ has no source. Therefore G ′ is not a DAG. Since G ′ must contain a cycle, on that cycle BR(a) = (a + 1) mod (n + 1), which implies that at least one player on that cycle is not playing a best response. Therefore s must not be a PSNE.
The above construction does not directly work for the general case of digraphs with no sinks: now G ′ could be a DAG. It turns out that we can indeed fix the construction to work for all digraphs with no sinks. At a high level, instead of forming a best-response cycle with the actions, we form a ρ shape with a cycle and a tail.
We now complete the specification of the utility functions for our construction for Lemma 20. The failure actions are 1, . . . , 2n + 1. If the input action tuple of Uc does not correspond to a hyperedge in H with the same color c, then: • if no neighbors are playing failure actions, then utility of playing failure action 1 is +1, all others -100; • otherwise, let fmax be the max failure action of neighbors. If fmax < 2n + 1, then BR = fmax + 1; otherwise (i.e. fmax = 2n + 1), let BR = n + 1.
We now sketch the "only if" direction of Lemma 20. If there is no homomorphism, then for any strategy profile, some player must play failure actions, which implies that some SCC (and all SCCs reachable form there) must play failure; the other SCCs must not play failure actions. Given a strategy profile, consider the "earliest reached" non-singleton SCC, as defined by the following process: go through SCCs in topological order, in the direction of the edges; return the first non-singleton SCC whose players choose failure actions. All earlier SCCs are either not playing failure actions, or a singleton SCC that is playing failure action a <= n.
Given strategy profile s, consider the graph G f , which is the subgraph of G restricted over the earliest non-singleton SCC and all earlier singleton SCCs playing failure actions: First, we claim that if one player j in the non-singleton SCC is playing an action less or equal to n, then s must not be a PSNE. This is because for such an action b ≤ n to be a best response, all incoming neighbors within the SCC must be playing even lesser failure actions. If we iteratively follow an incoming neighbor within the SCC, thus with decreasing actions, we either encounter j again, with action less than b, a contradiction, or a player k playing action 1. For 1 to be a BR, all neighbors must not play failure actions; but k is in a non-singleton SCC with all players playing failure actions, so there must be at least one neighbor playing failure actions, a contradiction.
Therefore, in order for s to be an PSNE, all players in the nonsingleton SCC must play failure actions greater than n. We claim that if this is the case, then each vertex in the non-trivial SCC must have an active neighbor in the same SCC. This is because if an edge from a singleton SCC in G f to a player i the non-singleton SCC in G f is active, then because the player in the singleton SCC is playing some action a <= n, the target player i in the non-singleton SCC must have an inactive neighbor in that SCC, i.e. some player j in the non-singleton SCC is playing b < a ≤ n. We have argued above that this would contradict with s being a PSNE. Therefore, each vertex in the non-trivial SCC must have an active neighbor in the same SCC. By the same argument as for the strongly connected digraph case, there must exist an active cycle in the SCC. Since every player on that active cycle is playing an action greater than n, they are playing a shifted version of the game in Lemma 22. This implies that s cannot be a PSNE.

DISCUSSION AND FUTURE WORK
Our results can be understood as establishing an equivalence between PSNE problems and homomorphism problems. Such a equivalence relation is closer than the kind of equivalence between two NP-complete problems: we are in fact showing a family of equivalences, between PURE-CHG(C, −) for an arbitrary class C and HOM(red(C), −). On the other hand, our results also show that there are certain differences between the two problems: because in a graphical/colored hypergraphical game each player has at least one best response regardless of her neighbors' actions, we can iteratively remove sinks without affecting the answer, whereas the same does not hold for homomorphism problems in general.
We have focused on the decision problem on the existence of pure Nash equilibria. Related problems include counting the number of pure Nash equilibria and finding one such equilibrium if one exists. On the homomorphism problem side, Dalmau and Jonsson [4] gave a characterization of the complexity of the counting version of HOM(C, −), while the characterization for the construction problem is still open. An interesting direction is to adapt our reductions to the counting and construction versions of these problems, as well as to cases with unbounded in-degree. Another direction is to use similar techniques to prove characterizations for other game representations such as action graph games [1,14].