# tight_inapproximability_for_graphical_games__ede4134d.pdf

Tight Inapproximability for Graphical Games

Argyrios Deligkas1, John Fearnley2, Alexandros Hollender3, Themistoklis Melissourgos4

1Royal Holloway, United Kingdom 2University of Liverpool, United Kingdom 3EPFL, Switzerland 4University of Essex, United Kingdom argyrios.deligkas@rhul.ac.uk, john.fearnley@liverpool.ac.uk, alexandros.hollender@epfl.ch, themistoklis.melissourgos@essex.ac.uk

We provide a complete characterization for the computational complexity of finding approximate equilibria in two-action graphical games. We consider the two most well-studied approximation notions: ε-Nash equilibria (ε-NE) and ε-wellsupported Nash equilibria (ε-WSNE), where ε [0, 1]. We prove that computing an ε-NE is PPAD-complete for any constant ε < 1/2, while a very simple algorithm (namely, letting all players mix uniformly between their two actions) yields a 1/2-NE. On the other hand, we show that computing an ε-WSNE is PPAD-complete for any constant ε < 1, while a 1-WSNE is trivial to achieve, because any strategy profile is a 1-WSNE. All of our lower bounds immediately also apply to graphical games with more than two actions per player.

Introduction

Graphical games were introduced more than twenty years ago by Kearns, Littman, and Singh (Kearns, Littman, and Singh 2001) as a succinct model of a multi-player game. These games have found a wide variety of applications. On the theoretical side, they have served as a fundamental tool for showing seminal PPAD-completeness results in algorithmic game theory (Daskalakis, Goldberg, and Papadimitriou 2009; Chen, Deng, and Teng 2009). Practically, graphical games have been used as a foundation for the game theoretic analysis of networks (Galeotti et al. 2010; Jackson and Zenou 2015), social networks, and multi-agent systems (Kearns 2007; Jackson 2011). A graphical game is specified by a directed graph with n vertices. Each vertex represents a player, and each player has m distinct actions. The edges of the graph specify the interactions between the players: the payoff to player i is determined entirely by the actions chosen by player i and the in-neighbours of player i. Formally, the payoffs for a player are given by a payoff tensor, which maps the actions chosen by that player and their in-neighbours to a payoff in [0, 1]. Graphical games are more succinct than standard normal form games when the maximum in-degree d is constant. An n-player m-action game requires n mn payoffs to be written down, which becomes infeasibly large as n grows. On the other hand, each tensor in a graphical game has md+1 payoff

Copyright 2023, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.

entries, giving n md+1 payoffs in total, which provides much more reasonable scaling as n grows when d is constant.

The complexity of finding equilibria. Unfortunately it is known that finding a Nash equilibrium in a graphical game is a PPAD-hard problem (Daskalakis, Goldberg, and Papadimitriou 2009) and thus considered to be intractable. This has left open the question of finding approximate Nash equilibria, and two notions of approximate equilibrium have been studied in the literature. An ε-Nash equilibrium (ε-NE) requires that no player can improve their payoff by more than ε by unilaterally changing their strategy, while an ε-well-supported Nash equilibrium (ε-WSNE) requires that all players only place positive probability on actions that are ε-best responses. Every ε-WSNE is also an ε-NE, but the reverse is not true. In this paper we make the standard assumption that all payoffs lie in the range [0, 1], which then gives us a scale on which we can measure the additive approximation factor ε. A 0-NE or 0-WSNE is an exact Nash equilibrium, while a 1-NE or 1-WSNE can be trivially obtained, since the requirements will be satisfied no matter what strategies the players use. For many years, the best known lower bounds for approximate equilibria in graphical games were given by Rubinstein (Rubinstein 2018), who proved that there is some unspecified small constant ε for which finding an ε-NE is PPAD-complete, and there is a different but still unknown small constant ε for which finding an ε -WSNE is PPADcomplete. In fact, Rubinstein s result applies to games that are simultaneously graphical games of constant degree and also polymatrix games, namely in which each edge represents a two-player game and a player s payoff is the sum of payoffs from these games against her in-neighbours. This was recently improved by a result of Deligkas et al. (Deligkas et al. 2022a). They showed that it is PPADcomplete to find a 1/48-NE of a two-action polymatrix game, and it is PPAD-complete to find an ε-WSNE of a two-action polymatrix game for all ε < 1/3 (the latter result being tight). Since these hardness results hold even for constant-degree polymatrix games, they also apply to graphical games.1 On the other hand, only trivial upper bounds are known for approximate equilibria in graphical games, even when the players only have two actions. For ε-WSNE the upper

1A polymatrix game of constant degree can be turned into its graphical game representation in polynomial time.

The Thirty-Seventh AAAI Conference on Artificial Intelligence (AAAI-23)

bound is 1, since any strategy profile is a 1-WSNE. For ε-NE, the upper bound is 1/2 in two-action games and is achieved when all players uniformly mix over their two actions; the upper bound simply follows from the fact that every player plays their best response with probability at least 0.5 and that the maximum payoff is bounded by 1.

Our Contribution. In this paper we show that the aforementioned trivial upper bounds are in fact the best possible, by providing matching lower bounds for finding approximate equilibria in graphical games. For the problem of finding an ε-WSNE, we show that it is PPAD-complete to find an ε-WSNE in a two-action graphical game for every constant ε < 1. Since finding a 1-WSNE is trivial, we obtain a striking characterization for constant ε: no polynomial-time algorithm can find a non-trivial WSNE of a graphical game unless PPAD = P. In fact, we present a more fine-grained analysis that provides a complete dichotomy of the complexity of finding a WSNE in a two-action graphical game of maximum in-degree d:

a 1 2 2d+1 -WSNE can be found in polynomial time;

for any ε < 1 2 2d+1, it is PPAD-complete to compute a ε-WSNE. Thus, for any constant ε < 1 there exists a sufficiently large constant in-degree d, such that the problem becomes intractable. For ε-NE we show that it is PPAD-complete to find an εNE of a two-action graphical game for any constant ε < 0.5; this complements the straightforward algorithm for finding a 0.5-NE in a two-action graphical game. We note that our lower bounds, both for ε-WSNE and ε-NE, also hold for graphical games with more than two actions.2 All of our lower bounds are shown via reductions from the PURE-CIRCUIT problem that was recently introduced by Deligkas et al. (Deligkas et al. 2022a). In that paper, PURECIRCUIT was used to show the aforementioned lower bounds for polymatrix games. We show that PURE-CIRCUIT can likewise be used to show stronger and tight lower bounds for graphical games. Due to space restrictions, some proofs are omitted and can be found in the full version (Deligkas et al. 2022b).

Further Related Work. The class PPAD was defined by Papadimitriou (Papadimitriou 1994). Many years later, Daskalakis, Goldberg, and Papadimitriou (Daskalakis, Goldberg, and Papadimitriou 2009) proved that finding an ε-NE in graphical games and 3-player normal form games is PPADcomplete for an exponentially small ε. These results were further extended to polynomially small ε for 2-player games and two-action polymatrix games with bipartite underlying graph by Chen, Deng, and Teng (Chen, Deng, and Teng 2009). On the positive side, Elkind, Goldberg, and Goldberg (Elkind, Goldberg, and Goldberg 2006) derived a polynomial-time algorithm on two-action graphical games

2We can simply add additional dummy actions that are just copies of the original two actions.

on paths and cycles, and Ortiz and Irfan (Ortiz and Irfan 2017) derived an approximation scheme for constant-action graphical games on trees. For polymatrix games, Barman, Ligett, and Piliouras (Barman, Ligett, and Piliouras 2015) derived a quasi-PTAS on trees, and Deligkas, Fearnley, and Savani (Deligkas, Fearnley, and Savani 2017) derived a quasi-PTAS for constant-action games on bounded treewidth graphs. These results where complemented by the same authors (Deligkas, Fearnley, and Savani 2020) who showed that finding an exact NE is PPAD-complete for polymatrix games on trees when every player has 20 actions.

Preliminaries

For every natural number k, let k denote the k-dimensional simplex, i.e., k := {x Rk+1 : x 0, Pk+1 i=1 xi = 1}, and let [k] := {1, 2, . . . , k}.

Graphical Games

An n-player m-action graphical game is defined by a directed graph G = (V, E), where |V | = n, each node of G corresponds to a player, and the maximum number of actions per player is m. We define the in-neigbourhood of node i to be N (i) := {j V : (j, i) E}, and similarly its out-neighbourhood to be N +(i) := {j V : (i, j) E}. We also define the neighbourhood of i as N(i) := N (i) N +(i) {i}. We include i in its own neighbourhood for notational convenience. In a graphical game, each player i participates in a normal form game Gi whose player set is N(i), but she affects only the payoffs of her out-neighbours. Player i has mi actions, or pure strategies, and her payoffs are represented by a function Ri : [mi] Q j N (i)[mj] 7 [0, 1] which will be referred to as the payoff tensor of i. If the codomain of Ri is {0, 1} for all i V , we have a win-lose graphical game. A mixed strategy si for player i specifies a probability distribution over player i s actions. Thus, the set of mixed strategies for player i corresponds to the (mi 1)- dimensional simplex mi 1. The support of a mixed strategy si = (si(1), si(2), . . . , si(mi)) mi 1 is given by supp(si) = {j [mi] : si(j) > 0}. In other words, it is the set of pure strategies that are played with non-zero probability in strategy si. An action profile a(H) := (ai)i H over a player set H is a tuple of actions, one for each player in H, and so the set of these action profiles is given by A(H) = Q i H[mi]. Similarly, a strategy profile s(H) over the same set is a tuple of mixed strategies, and so the set of these strategy profiles is given by Q i H mi 1. We define the partial action profile a i to be the tuple of all players actions except i s action, and similarly we define the partial strategy profile s i. The expected payoff of i when she plays action k [mi], and all other players play according to s i is

ui(k, s i) := X

a A(N (i)) Ri(k; a) Y

j N (i) sj(aj).

Notice that this depends only on the in-neighbours of i.

The expected payoff to player i under s is therefore

k [mi] ui(k, s i) si(k).

A pure strategy k is a best response for player i against a partial strategy profile s i if it achieves the maximum payoff over all her pure strategies, that is,

ui(k, s i) = max ℓ [mi] ui(ℓ, s i).

Pure strategy k is an ε-best response if the payoff it yields is within ε of a best response, meaning that

ui(k, s i) max ℓ [mi] ui(ℓ, s i) ε.

Finally, the best response payoff for player i is

bri(s i) := max ℓ [mi] ui(ℓ, s i).

(Approximate) Nash equilibria. A strategy profile s is a Nash equilibrium if bri(s) = ui(s) for all players i, i.e., every player achieves their best response payoff. A strategy profile s is an ε-Nash equilibrium (ε-NE) if every player s payoff is within ε of their best response payoff, meaning that ui(s) bri(s) ε. A strategy profile s is an ε-well supported Nash equilibrium (ε-WSNE) if every player only plays strategies that are ε-best responses, that is, for all i we have that supp(si) contains only ε-best response strategies.

The PURE-CIRCUIT Problem An instance of the PURE-CIRCUIT problem is given by a node set V = [n] and a set G of gate-constraints (or just gates). Each gate g G is of the form g = (T, u, v, w) where u, v, w V are distinct nodes, and T {NOT, AND, PURIFY} is the type of the gate, with the following interpretation. If T = NOT, then u is the input of the gate, and v is its output. (w is unused) If T = AND, then u and v are the inputs of the gate, and w is its output. If T = PURIFY, then u is the input of the gate, and v and w are its outputs. We require that each node is the output of exactly one gate. A solution to instance (V, G) is an assignment x : V {0, 1, } that satisfies all the gates (see Fig. 1), i.e., for each gate g = (T, u, v, w) G we have the following. If T = NOT in g = (T, u, v), then x satisfies

x[u] = 0 = x[v] = 1 x[u] = 1 = x[v] = 0.

If T = AND in g = (T, u, v, w), then x satisfies

x[u] = x[v] = 1 = x[w] = 1 x[u] = 0 x[v] = 0 = x[w] = 0.

If T = PURIFY, then x satisfies

{x[v], x[w]} {0, 1} = x[u] {0, 1} = x[v] = x[w] = x[u].

The structure of a PURE-CIRCUIT instance is captured by its interaction graph. This graph is constructed on the vertex set V = [n] by adding a directed edge from node u to node v whenever v is the output of a gate with input u. The total degree of a node is the sum of its inand out-degrees.

Theorem 1 ((Deligkas et al. 2022a)). PURE-CIRCUIT is PPAD-complete, even when every node of the interaction graph has in-degree at most 2 and total degree at most 3.

Well-Supported Nash Equilibria An easy upper bound. We present a polynomial time algorithm to compute a 1 2 2d+1 -WSNE in any two-action graphical game with maximum in-degree d 2. The algorithm relies on a simple and natural approach that has been used for similar problems by Liu et al. (Liu, Li, and Deng 2021) and Deligkas et al. (Deligkas et al. 2022a). The algorithm proceeds in two steps. In the first step, it iteratively checks for a player that has an action that is εdominant; an action which, if played with probability 1, will satisfy the ε-WSNE conditions no matter what strategies the in-neighbours play. Here, we will set ε = 1 2 2d+1, where d is the maximum in-degree of the graph. If such a player with an ε-dominant action exists, the algorithm fixes the strategy of that player, updates the game accordingly, and iterates until there is no such player left. In the second step, the algorithm lets all remaining players mix uniformly, i.e., every player without an ε-dominant action plays each of its two actions with probability 1/2.

Theorem 2. There is a polynomial-time algorithm that finds a 1 2 2d+1 -WSNE in a two-action graphical game with maximum in-degree d.

Proof. It is easy to see that the algorithm described above runs in polynomial time. In particular, we can check if a player has an ε-dominant action by simply going over all possible action profiles of its in-neighbours. We will prove it computes an ε-WSNE for ε = 1 2 2d+1. By definition of ε-dominance, the players whose actions were fixed in the first step satisfy the constraints of ε-WSNE. Notice that after fixing any such player to play an ε-dominant action, we get a smaller graphical game. Thus, it suffices to consider the graphical game we obtain after the end of the first step, and to show that if all (remaining) players mix uniformly, this is an ε-WSNE. So, consider a player i in the graphical game we obtain after the end of the first step, and denote its in-degree by k := |N (i)| d. Since all in-neighbours of player i are mixing uniformly, the expected payoff of player i for playing action 0 is P a A(N (i)) Ri(0; a)/2k, and for playing action 1, it is P a A(N (i)) Ri(1; a)/2k. The constraints of ε-WSNE for player i are satisfied if both actions are ε-best responses, i.e., if

a A(N (i)) Ri(0; a)/2k X

a A(N (i)) Ri(1; a)/2k

u v 0 1 1 0 {0, 1, }

u v w 1 1 1 0 {0, 1, } 0 {0, 1, } 0 0 Else {0, 1, }

u v w 0 0 0 1 1 1

At least one output in {0, 1}

PURIFY gate

Figure 1: The truth tables of the three gates of PURE-CIRCUIT.

This can be rewritten as 1

2k P a A(N (i)) fi(a) ε, where,

for any action profile a A(N (i)), we let fi(a) := Ri(0; a) Ri(1; a). Note that since all payoffs lie in [0, 1], we always have fi(a) [ 1, 1]. Let M := P a A(N (i)) fi(a). To prove the correctness of the algorithm, it suffices to prove that |M| 2k 1 ε; since then 1 2k |M| 1 1+ε

2d = ε. To see why this is indeed the case, observe the following. Since player i does not have an ε-dominant action (otherwise, it would have been removed in the first step), it means that there exist a, a A(N (i)) such that fi(a) > ε and fi(a ) < ε. (1)

Given that M is the sum of 2k terms, each of them upper bounded by 1, and at least one of them upper bounded by ε by (1), it follows that M 2k 1 ε. Similarly, since each term is also lower bounded by 1, and one of them is lower bounded by ε, we also obtain that M 2k 1 + ε. Thus, |M| 2k 1 ε, as desired.

The lower bound. In this section we prove a matching lower bound for Theorem 2, which essentially proves that computing an ε-WSNE in two-action graphical games is PPAD-complete for every constant ε (0, 1). We will prove our result by a reduction from PURECIRCUIT. For the remainder of this section, we fix ε < 1 2 2d+1. Given a PURE-CIRCUIT instance with in-degree 2, we build a two-action graphical game, where the two actions will be named zero and one. For any given d 2, the game will have in-degree at most d. Each node v of the PURE-CIRCUIT instance will correspond to a player in the game the game will have some additional auxiliary players too whose strategy in any ε-WSNE will encode a solution to the PURE-CIRCUIT problem as follows. Given a strategy sv for the player that corresponds to node v, we define the assignment x for PURE-CIRCUIT such that: if sv(zero) = 1, then x[v] = 0; if sv(one) = 1, then x[v] = 1; otherwise, x[v] = . We now give implementations for NOT, AND, and PURIFY gates. We note that, in all three cases, the payoff received by player v is only affected by the actions chosen by the players representing the inputs to the (unique) gate g that outputs to v. Thus, we can argue about the equilibrium condition at v by only considering the players involved in gate g, and we can ignore all other gates while doing this.

NOT gates. For a gate g = (NOT, u, v) where recall that u is the input variable and v is the output variable we create a gadget involving players u and v, where player v has a unique incoming edge from u. The payoffs of v are defined as follows.

If u plays zero, then v gets payoff 0 from playing zero and payoff 1 from playing one. If u plays one, then v gets 1 from zero and 0 from one.

This gadget appeared in (Deligkas et al. 2022a), but we include it here for completeness. We claim that this gadget works correctly.

- If su(zero) = 1, i.e., u encodes 0, observe that for player v action zero yields payoff 0, while action one yields payoff 1. Hence, by the constraints imposed by ε-WSNE it must hold that sv(one) = 1, and thus v encodes 1. - Using identical reasoning, we can prove that if su(one) = 1, then sv(one) = 0 in any ε-WSNE.

AND gates. For a gate g = (AND, u, v, w) we create the following gadget with players u, v and w, where u and v are the in-neighbors of w. The payoffs of w are as follows.

If su(one) = 1 and sv(one) = 1, then w gets payoff 0 from playing zero and payoff 1 from playing one. For any other action profile of u and v, player w gets 1 from zero and 0 from one.

Next we argue that this gadget works correctly.

- If su(one) = 1 and sv(one) = 1, i.e. both u and v encode 1, observe that for player w action zero yields payoff 0, while action one yields payoff 1. Hence, by the constraints imposed by ε-WSNE it must hold that sw(one) = 1, and thus w encodes 1. - If at least one of u or v encodes 0, then for player w action zero yields expected payoff 1 while action one yields expected payoff 0. Hence, by the constraints imposed by ε-WSNE it must hold that sw(zero) = 1, and thus w encodes 0.

PURIFY gates. For a gate g = (PURIFY, u, v, w) we create the following gadget with d + 3 players. We introduce auxiliary players u1, u2, . . . , ud. Each player ui has a unique incoming edge from u. The idea is that in any ε-WSNE, every player ui copies the strategy of player u.

If u plays zero, then ui gets 1 from zero and 0 from one. If u plays one, then ui gets 0 from zero and 1 from one.

Lemma 3. At any ε-WSNE the following hold for every i [d]: if su(zero) = 1, then sui(zero) = 1; if su(one) = 1, then sui(one) = 1.

Proof. If su(zero) = 1, then for player ui action zero yields payoff 1, while action one yields payoff 0. Thus, the constraints of ε-WSNE dictate that sui(zero) = 1. If su(one) = 1, then for player ui action zero yields payoff 0, while action one yields payoff 1. Thus, the constraints of ε-WSNE dictate that sui(one) = 1.

Next, we describe the payoff tensors of players v and w; each one of them has in-degree d with edges from all u1, u2, . . . , ud. In what follows, fix λ := 1 2 2d+1. The payoffs of player v are as follows.

If v plays zero and at least one of u1, . . . , uk plays zero, then the payoff for v is 1. If v plays zero and every one of u1, . . . , uk plays one, then the payoff for v is 0. If v plays one and at least one of u1, . . . , uk plays zero, then the payoff for v is 0. If v plays one and every one of u1, . . . , uk plays one, then the payoff for v is λ.

The payoffs of player w are as follows.

If w plays zero and every one of u1, . . . , uk plays zero, then the payoff for w is λ. If w plays zero and at least one of u1, . . . , uk plays one, then the payoff for w is 0. If w plays one and every one of u1, . . . , uk plays zero, then the payoff for w is 0. If w plays one and at least one of u1, . . . , uk plays one, then the payoff for w is 1.

We are now ready to prove that this construction correctly simulates a PURIFY gate. We consider the different cases that arise depending on the value encoded by u.

su(zero) = 1, i.e., u encodes 0. From Lemma 3 we know that sui(zero) = 1 for every i [d]. Then, we have the following for players v and w.

- Player v gets payoff 1 from action zero and payoff 0 from action one. Hence, in an ε-WSNE we get that sv(zero) = 1, and thus v encodes 0. - Player w gets payoff λ from action zero and payoff 0 from action one. Hence, since ε < λ, in an ε-WSNE we get that sw(zero) = 1, and thus w encodes 0.

su(one) = 1, i.e., u encodes 1. From Lemma 3 we know that sui(one) = 1 for every i [d]. Then, we have the following for players v and w.

- Player v gets payoff 0 from action zero and payoff λ from action one. Hence, since ε < λ, in an ε-WSNE we get that sv(one) = 1, and thus v encodes 1. - Player w gets payoff 0 from action zero and payoff 1 from action one. Hence, in an ε-WSNE we get that sw(one) = 1, and thus w encodes 1.

su(one) (0, 1), i.e., u encodes . Then each one of the auxiliary players u1, . . . , ud can play a different strategy. For each i [d], denote sui(one) = pi, i.e., pi [0, 1] is the probability player ui assigns on action one. Let P := Q i [d] pi and Q := Q i [d](1 pi). Then, we have the following two cases. - P 2 d. Then we focus on player v: action zero yields expected payoff 1 P 1 2 d, while action one yields expected payoff P λ 2 d λ. Then, since ε < λ, we get that in an ε-WSNE it must hold that sv(zero) = 1, i.e., v encodes 0. - P > 2 d. Then, it holds that Q < 2 d; this is because P Q = Q i [d] pi (1 pi) (1/4)d. In this case we focus on player w: action zero yields payoff λ Q < λ 2 d, while action one yields payoff 1 Q > 1 2 d. Then, again since ε < λ, in any ε-WSNE it must hold that sw(one) = 1, i.e., w encodes 1. From the arguments given above, we have that in any εWSNE of the graphical game, with ε < 1 2 2d+1, the players correctly encode a solution to the PURE-CIRCUIT instance. Theorem 4. Computing an ε-WSNE in two-action graphical games with maximum in-degree d 2 is PPAD-complete for any ε < 1 2 2d+1.

We can see that the constructed game is not win-lose since there is a payoff λ / {0, 1} in the gadget that simulates PURIFY gates. However, if we set λ = 1, and use verbatim the analysis from above, we will get PPAD-hardness for ε-WSNE with ε < 1 1 2d 1 . Theorem 5. Computing an ε-WSNE in two-action win-lose graphical games with maximum in-degree d 2 is PPADcomplete for any ε < 1 1 2d 1 . Since for every constant ε < 1 we can find a constant d such that Theorem 5 holds, we get the following corollary. Corollary 6. For any constant ε < 1, computing an ε-WSNE in two-action win-lose graphical games is PPAD-complete.

Approximate Nash Equilibria A straightforward upper bound. We first show that a 0.5NE can easily be found in any two-action graphical game. Theorem 7. There is a polynomial-time algorithm that finds a 0.5-NE in a two-action graphical game.

Proof. Let s be the strategy profile in which all players mix uniformly over their two actions. Then, for each player i we have

ui(s) 0.5 bri(s i) bri(s i) 0.5,

where the final inequality used the fact that bri(s i) [0, 1]. Thus, s is a 0.5-NE.

The lower bound. We will show that computing a (0.5 ε)- NE of a graphical game is PPAD-hard for any constant ε > 0 by a reduction from PURE-CIRCUIT. Given a PURE-CIRCUIT instance, we build a two-action graphical game, where the two actions will be named zero

and one. Each node v of the PURE-CIRCUIT instance will be represented by a set of k players in the game, named v1, v2, . . . , vk, where we fix k to be an odd number satisfying k ln(12/ε) 18/ε2. Therefore, since ε is constant, k is also constant. The strategies of these players will encode a solution to the PURE-CIRCUIT problem in the following way. Given a strategy profile s, we define the assignment x such that If svi(zero) 0.5 + ε/3 for all i, then x[v] = 0. If svi(one) 0.5 + ε/3 for all i, then x[v] = 1. In all other cases, x[v] = . We now give implementations for NOT, AND, and PURIFY gates. We note that, in all three cases, the payoff received by player vi is only affected by the actions chosen by the players representing the inputs to the (unique) gate g that outputs to v. Thus, we can argue about the equilibrium condition at vi by only considering the players involved in gate g, and we can ignore all other gates while doing this.

NOT gates. For a gate g = (NOT, u, v), we use the following construction, which specifies the games that will be played between the set of players that represent u and the set of players that represent v. Each player vi has incoming edges from all players u1, u2, . . . , uk, and vi s payoff tensor is set as follows. If strictly more than3 k/2 of the players u1 through uk play zero, then vi receives payoff 0 for strategy zero and payoff 1 for strategy one. If strictly less than k/2 of the players u1 through uk play zero, then vi receives payoff 1 for strategy zero and payoff 0 for strategy one. We now show the correctness of this construction. We start with a technical lemma that we will use repeatedly throughout the construction. Lemma 8. Suppose that player p has two actions a and b. In any (0.5 ε)-NE, if the payoff of action a is at most ε/3, and the payoff of action b is at least 1 ε/3, then player p must play action b with probability at least 0.5 + ε/3. We can now prove that the NOT gadget operates correctly. Lemma 9. In every (0.5 ε)-NE, the following properties hold. If the players representing u encode 0, then the players representing v encode 1. If the players representing u encode 1, then the players representing v encode 0.

Proof. Let s be a (0.5 ε)-NE. We begin with the first claim. Since the players representing u encode a 0, we have that suj(zero) 0.5 + ε/3 for all j [k]. We start by proving an upper bound on the payoff of action zero for player vi. The payoff of this action increases as the players uj place less probability on action zero, so we can assume suj(zero) = 0.5 + ε/3, since this minimizes the payoff of zero to vi.

3Since k is odd, it is not possible for exactly k/2 players to play zero.

Under this assumption, the number N of players uj that play action zero is distributed binomially according to N B(k, 0.5 + ε/3). Applying the standard Hoeffding bound (Hoeffding 1994) for the binomial distribution, and using the fact that k ln(6/ε) 9/2ε2 yields the following

Pr(N k/2) 2 exp

2k 0.5 + ε/3 k/2

= 2 exp 2k ε2/9

exp ( ln(3/ε)) = ε/3.

Hence the payoff of action zero to player vi is at most ε/3, and therefore the payoff of action one to vi is at least 1 ε/3. So we can apply Lemma 8 to argue that svi(one) 0.5 + ε/3. Since this holds for all i, we have that the players representing v encode the value 1 in the PURE-CIRCUIT instance, as required. The second case can be proved in an entirely symmetric manner.

AND gates. For a gate g = (AND, u, v, w) we use the following construction. Each player wi has in-degree 2k and has incoming edges from all of the players u1, u2, . . . , uk, and all of the players v1, v2, . . . , vk. The payoff tensor of wi is as follows.

If strictly more than k/2 of the players u1 through uk play one, and strictly more than k/2 of the players v1 through vk play one, then wi receives payoff 0 from action zero and payoff 1 from action one.

If this is not the case, then wi receives payoff 1 from action zero and payoff 0 from action one.

Correctness of this construction is shown in the following pair of lemmas.

Lemma 10. In every (0.5 ε)-NE of the game, if the players representing u encode value 1, and the players representing v encode value 1, then the players representing w will encode value 1.

Proof. Let s be a (0.5 ε)-NE. From the assumptions about u and v, we have that suj(one) 0.5 + ε/3 for all j, and svj(one) 0.5 + ε/3 for all j [k]. We start by proving an upper bound on the payoff of zero to wi. Since this payoff decreases as the players uj and vj place more probability on one, we can assume that suj(one) = 0.5 + ε/3 for all j, and svj(one) = 0.5 + ε/3 for all j, since this maximizes the payoff of zero to wi. The number N of players uj that play one is distributed binomially according to N B(k, 0.5+ε/3). Similarly, the number of players vj that play one, are distributed according to the same distribution, that is why we focus only in the former. The standard Hoeffding bound for the binomial

distribution, and the fact that k ln(12/ε) 9/2ε2, give

Pr(N k/2) 2 exp

2k 0.5 + ε/3 k/2

= 2 exp 2k ε2/9

exp ( ln(6/ε)) = ε/6.

We can then use the union bound to prove that the probability that strictly less than k/2 of the players u1 through uk play one, or strictly less than k/2 of the players v1 through vk play one is at most ε/3. Hence, the payoff of zero to player wi is at most ε/3, and so the payoff of one to player wi is at least 1 ε/3. Thus we can apply Lemma 8 to argue that wi must play one with probability at least 0.5 + ε/3. Since this holds for all i, we have that w1, w2, . . . wk correctly encode value 1.

Lemma 11. In every (0.5 ε)-NE of the game, if the players representing u encode value 0, or the players representing v encode value 0, then the players representing w will encode value 0.

PURIFY gates. For a gate g = (PURIFY, u, v, w), we use the following construction. Each player vi will have incoming edges from all players u1, u2, . . . , uk, with their payoff tensor set as follows. If strictly more than (0.5 ε/6) k of the players u1 through uk play one, then vi receives payoff 0 from action zero and payoff 1 from action one. If this is not the case, then vi receives payoff 1 from action zero and payoff 0 from action one. Each player wi will have incoming edges from all players u1, u2, . . . , uk, with their payoff tensor set as follows. If strictly more than (0.5 + ε/6) k of the players u1 through uk play one, then wi receives payoff 0 from action zero and payoff 1 from action one. If this is not the case, then wi receives payoff 1 from action zero and payoff 0 from action one. The following lemma shows that v is correctly simulated. Lemma 12. Let s be a (0.5 ε)-NE, and let E[X] denote the expected number of players ui playing strategy one under s. If E[X] (0.5 ε/3) k, then the players representing v will encode value 0. If E[X] 0.5 k, then the players representing v will encode value 1. The next lemma shows that w is also correctly simulated. Lemma 13. Let s be a (0.5 ε)-NE, and let E[X] denote the expected number of players ui playing strategy one under s. If E[X] 0.5 k, then the players representing w will encode value 0. If E[X] (0.5 + ε/3) k, then the players representing w will encode value 1. Combining the two previous lemmas, we can see that the construction correctly simulates a PURIFY gate.

If the players representing u encode value 0, then E[X] 0.5 ε/3, and so both the players representing v and those representing w encode value 0. If the players representing u encode value 1, then E[X] 0.5+ε/3, and so both the players representing v and those representing w encode value 1. In all other cases we can verify that either the players representing v or the players representing w encode a 0 or a 1. Specifically, if E[X] 0.5 k then the players representing w encode value 0, while if E[X] 0.5 k, then the players representing v encode value 1.

The hardness result. From the arguments given above, we have that in an (0.5 ε)-NE of the graphical game, the players correctly encode a solution to the PURE-CIRCUIT instance. Note also that, since Theorem 1 gives hardness for PURE-CIRCUIT even when the total degree of each node is 3, the graphical game that we have built has total degree at most 3k. Thus, the game can be built in polynomial time.

Theorem 14. It is PPAD-hard to find a (0.5 ε)-NE in a two-action graphical game for any constant ε > 0.

In fact, the payoff entries in all gadgets are 0 or 1. Thus, our PPAD-hardness result holds for win-lose games too.

Corollary 15. For any constant ε > 0, it is PPAD-hard to find a (0.5 ε)-NE in a two-action win-lose graphical game.

Conclusions We have resolved the computational complexity of finding approximate Nash equilibria in two-action graphical games, by providing complete characterizations for both ε-NE and ε-WSNE. Our results show that finding approximate Nash equilibria in graphical games is much harder when compared to the special case of (constant-degree) polymatrix games: for two-action polymatrix games the tractability threshold for ε-WSNE is 1/3 (Deligkas et al. 2022a). Below we identify two research questions that deserve more research.

What is the intractability threshold for ε-NE in graphical games with more than two actions? We have shown that 0.5 is the threshold for two-action games, and we conjecture that 0.5 is the correct answer for the multi-action case as well. Hence, we view the main open problem as finding a polynomial-time algorithm that finds a 0.5-NE in any graphical game. We note that such an algorithm is already known for the special case of polymatrix games (Deligkas et al. 2017). What is the intractability threshold for ε-NE and ε-WSNE in polymatrix games? For ε-NE our understanding is far from complete, even in the two-action case, since there is a substantial gap between the 1/48 lower bound and the 1/3 upper bound (where the latter actually comes from the tractability of 1/3-WSNE) given in (Deligkas et al. 2022a). For ε-WSNE, although the problem is completely resolved for the two-action case, the gap in multi-action polymatrix games is still large, and it seems that improving either the known lower bound of 1/3, or the trivial upper bound of 1, would require significantly new ideas.

Acknowledgements

The second author was supported by EPSRC grant EP/W014750/1 New Techniques for Resolving Boundary Problems in Total Search . The third author was supported by the Swiss State Secretariat for Education, Research and Innovation (SERI) under contract number MB22.00026.

References Barman, S.; Ligett, K.; and Piliouras, G. 2015. Approximating Nash Equilibria in Tree Polymatrix Games. In Proc. of SAGT, 285 296. Chen, X.; Deng, X.; and Teng, S.-H. 2009. Settling the complexity of computing two-player Nash equilibria. Journal of the ACM, 56(3): 14:1 14:57. Daskalakis, C.; Goldberg, P. W.; and Papadimitriou, C. H. 2009. The complexity of computing a Nash equilibrium. SIAM Journal on Computing, 39(1): 195 259. Deligkas, A.; Fearnley, J.; Hollender, A.; and Melissourgos, T. 2022a. Pure-Circuit: Strong Inapproximability for PPAD. In Proc. of FOCS, 159 170. Deligkas, A.; Fearnley, J.; Hollender, A.; and Melissourgos, T. 2022b. Tight Inapproximability for Graphical Games. ar Xiv preprint, abs/2209.15151. Deligkas, A.; Fearnley, J.; and Savani, R. 2017. Computing Constrained Approximate Equilibria in Polymatrix Games. In Proc. of SAGT, 93 105. Deligkas, A.; Fearnley, J.; and Savani, R. 2020. Tree Polymatrix Games Are PPAD-Hard. In Proc. of ICALP, volume 168, 38:1 38:14. Deligkas, A.; Fearnley, J.; Savani, R.; and Spirakis, P. G. 2017. Computing Approximate Nash Equilibria in Polymatrix Games. Algorithmica, 77(2): 487 514. Elkind, E.; Goldberg, L. A.; and Goldberg, P. W. 2006. Nash equilibria in graphical games on trees revisited. In Proc. of EC, 100 109. Galeotti, A.; Goyal, S.; Jackson, M. O.; Vega-Redondo, F.; and Yariv, L. 2010. Network games. The review of economic studies, 77(1): 218 244. Hoeffding, W. 1994. Probability inequalities for sums of bounded random variables. In The collected works of Wassily Hoeffding, 409 426. Springer. Jackson, M. O. 2011. An overview of social networks and economic applications. Handbook of social economics, 1: 511 585. Jackson, M. O.; and Zenou, Y. 2015. Games on networks. In Handbook of game theory with economic applications, volume 4, 95 163. Elsevier. Kearns, M. 2007. Graphical Games. In Nisan, N.; Roughgarden, T.; Tardos, E.; and Vazirani, V. V., eds., Algorithmic Game Theory, 159 180. Cambridge University Press. Kearns, M.; Littman, M. L.; and Singh, S. 2001. Graphical Models for Game Theory. In Proceedings of the 17th Conference on Uncertainty in Artificial Intelligence (UAI), 253 260.

Liu, Z.; Li, J.; and Deng, X. 2021. On the Approximation of Nash Equilibria in Sparse Win-Lose Multi-player Games. In Proceedings of the 35th AAAI Conference on Artificial Intelligence (AAAI), 5557 5565. Ortiz, L. E.; and Irfan, M. T. 2017. Tractable Algorithms for Approximate Nash Equilibria in Generalized Graphical Games with Tree Structure. In Proc. of AAAI, 635 641. Papadimitriou, C. H. 1994. On the complexity of the parity argument and other inefficient proofs of existence. Journal of Computer and System Sciences, 48(3): 498 532. Rubinstein, A. 2018. Inapproximability of Nash equilibrium. SIAM Journal on Computing, 47(3): 917 959.