Pure-Circuit: Tight Inapproximability for PPAD

Introduction

The complexity class PPAD has played a central role in determining the computational complexity of many problems arising in game theory and economics [Pap94]. The celebrated results of Daskalakis, Goldberg, and Papadimitriou [DGP09] and Chen, Deng, and Teng [CDT09] established that finding a Nash equilibrium in a strategic form game is PPAD-complete, and subsequent to this breakthrough many other PPAD-completeness results have been shown [CSVY08, CDDT09, VY11, DQS12, Das13, KPR+13, CDO15, CPY17, SSB17, Meh18, Rub18, DFS20, CKK21a, CKK21b, PP21, GH21, FRGH+23, DSZ21, CCPY22].

These celebrated results not only showed that it is PPAD-hard to find an exact equilibrium, but also that finding approximate solutions is PPAD-hard. The result of Daskalakis, Goldberg, and Papadimitriou [DGP09] showed that finding an $\varepsilon$-Nash equilibrium is PPAD-complete when $\varepsilon$ is exponentially small, while the result of Chen, Deng, and Teng [CDT09] improved this to show hardness for polynomially small $\varepsilon$. This lower bound is strong enough to rule out the existence of an FPTAS for the problem.

The main open question following these results was whether equilibrium computation problems in PPAD were hard for constant $\varepsilon$, which would also rule out the existence of a PTAS. Here one must be careful, because some problems do in fact admit approximation schemes. For example, in the case of two-player strategic-form games, a quasipolynomial-time approximation scheme is known [LMM03], meaning that the problem cannot be hard for a constant $\varepsilon$ unless every problem in PPAD can be solved in quasipolynomial time. But for other types of game such results are not known. This includes polymatrix games, which are $n$-player games with succinct representation [Jan68].

In another breakthrough result, Rubinstein [Rub18] developed techniques for showing constant inapproximability within PPAD, by proving that there exists a constant $\varepsilon$ such that finding an $\varepsilon$-well-supported Nash equilibrium in a polymatrix game is PPAD-complete. This lower bound is obtained by first showing constant inapproximability for the $\varepsilon$-Generalized-Circuit ($\varepsilon$-GCircuit) problem introduced by Chen, Deng, and Teng [CDT09], and then utilizing the known reduction from GCircuit to polymatrix games [DGP09].

Rubinstein’s lower bound has since been used to show constant inapproximability for other problems. Rubinstein himself showed constant inapproximability for finding Bayesian Nash equilibria, relative approximate Nash equilibria, and approximate Nash equilibria in non-monotone markets [Rub18]. Subsequent work has shown constant inapproximability for finding clearing payments in financial networks with credit default swaps [SSB17], finding equilibria in first-price auctions with subjective priors [FRGH+23], finding throttling equilibria in auction markets [CKK21b], finding equilibria in public goods games on directed networks [PP21], and finding consensus-halving solutions in fair division [FRFGZ18, GHI+22].

Rubinstein’s lower bound is an existential-constant result, meaning that it shows that there exists some constant $\varepsilon$ below which the problem becomes PPAD-hard. The fact that such a constant exists is important, since it rules out a PTAS. On the other hand, Rubinstein does not give any concrete lower bound on the size of the constant (understandably so, since this was not the purpose of his work). One could of course deduce such a lower bound by a careful examination of his reduction, but it is clear that this would yield an extremely small constant. Due to this, all of the other results that have utilized Rubinstein’s lower bound are likewise existential-constant results, which rule out PTASs but do not give any concrete lower bounds.

Ultimately, this means that existing work does not rule out an efficient algorithm that finds, say, a $0.001$-approximate solution for any of these problems, which would likely be more than enough for most practical needs. Arguably, a player would be more than happy to know that her strategy is an optimal best-response, up to a loss of at most $0.001$ in her utility value. Moreover, the existing work gives us no clue as to where the threshold for hardness may actually lie. To address these questions one would need to prove a large-constant inapproximability result, giving hardness for a known substantial constant.

Rubinstein’s lower bound is the ultimate source of all of the recent existential-constant lower bounds, so if one seeks a large-constant lower bound, then Rubinstein’s result is the bottleneck. Attempting to directly strengthen or optimize Rubinstein’s result does not seem like a promising direction. His proof, while ingenious, is very involved, and does not lend itself to easy optimization. Furthermore, it consists of many moving parts, so that even if one was able to optimize each module, the resulting constant would still be very small.

In this paper we introduce the techniques needed to show large-constant inapproximability results for problems in PPAD. Our key technical innovation is the introduction of a new intermediate problem, called Pure-Circuit, which we show to be PPAD-complete.

Then, by reducing onwards from Pure-Circuit, we show large-constant inapproximability results for a variety of problems in PPAD. In this sense, Pure-Circuit now takes on the role that $\varepsilon$-GCircuit has taken in the past, as an important intermediate problem from which all other results of this type are derived.

The Pure-Circuit problem itself can be thought of as a version of $\varepsilon$-GCircuit that is taken to its limits, and also dramatically simplified. In fact, the problem has only two gates (or, in a different formulation, three gates), which should be compared to $\varepsilon$-GCircuit, which has nine distinct gates. Perhaps more importantly, the gates in Pure-Circuit have very weak constraints on their outputs: the gates can be thought of as taking inputs in $$, and producing outputs in$$, but the gates themselves essentially only care about the values and $1$, with all other values being considered to be “bad” or “garbage” values (which we will later simply denote by “$\bot$”, instead of using values in $(0,1)$). This should be compared to $\varepsilon$-GCircuit gates, where, for example, one must output a value in $$that is within$\varepsilon$ of the sum of two inputs.

Combined, these properties make Pure-Circuit a very attractive problem to reduce from when showing a hardness result, since one only has to implement two (or three) gates, and the constraints that one must simulate are very loose, making them easy to implement. We formally introduce Pure-Circuit, and compare it to $\varepsilon$-GCircuit, in Section 2.

Our main result is to show that the Pure-Circuit problem is PPAD-complete. It is worth noting that there is no $\varepsilon$ in this result, and in fact the Pure-Circuit problem does not even take a parameter $\varepsilon$ in its definition. This is because, in some sense, the Pure-Circuit problem can be viewed as a variant of $\varepsilon$-GCircuit in which we have taken the limit $\varepsilon\to 1$. We give further justification of this idea in Section 2, but at a high level, this means that there is no loss of $\varepsilon$ in our main hardness result, with the only losses coming when one reduces onwards from Pure-Circuit. The proof of our main result is presented in Section 3, but we present a brief exposition of the main ideas in Section 1.1.

Finally, in Section 4 we present a number of new large-constant hardness results for problems in PPAD, all of which are shown via reductions from Pure-Circuit. We begin by showing that $\varepsilon$-GCircuit is PPAD-hard for all $\varepsilon<0.1$, giving a direct strengthening of Rubinstein’s lower bound. This also implies large-constant inapproximability results for all of the problems that currently have existential-constant lower bounds proved via GCircuit. However, to determine the constant, one would need to determine the amount of $\varepsilon$ that is lost in each of the onward reductions, and these reductions often did not optimize this, since they were proving existential-constant lower bounds.

We argue that the way forward now is providing direct reductions from Pure-Circuit in order to get the best possible hardness results. As evidence of this, we present the first tight inapproximability result for additive approximate equilibria in polymatrix games. Via a direct reduction from Pure-Circuit, we show that finding an $\varepsilon$-well-supported Nash equilibrium in a polymatrix game (PolymatrixWSNE) is PPAD-hard for all $\varepsilon<1/3$, even when every player only has two actions. This is much stronger than the lower bound of $0.05$ that we would have obtained by a reduction from our lower bound for GCircuit. It is also a tight result for two-action games: we give a polynomial-time algorithm for finding a $1/3$-well-supported Nash equilibrium, and so our lower bound completely characterizes the computational complexity of approximate well-supported equilibria in two-action polymatrix games. Similarly, we also provide a tight inapproximability result for computing approximate equilibria in threshold games, a problem introduced by Papadimitriou and Peng [PP21].

We summarize the hardness results obtained through a direct reduction from Pure-Circuit in the table below.

We note that PolymatrixWSNE and ThresholdGameNE have themselves both been used as intermediate problems for showing other constant inapproximability results in PPAD [Rub18, PP21, CKK21b, CCPY22], and thus our lower bounds potentially strengthen those results too. We provide an example in Appendix C, where we show that computing a relative $\varepsilon$-WSNE in a bimatrix game with non-negative payoffs is PPAD-complete for any $\varepsilon\leq 1/57$, by using an improved version of a reduction from PolymatrixWSNE due to Rubinstein [Rub18].

What is the intractability threshold for $\varepsilon$-NE and $\varepsilon$-WSNE in polymatrix games? For $\varepsilon$-NE our understanding is far from complete, even in the two-action case, since there is a substantial gap between the $0.088$ lower bound and the $1/3$ upper bound. For $\varepsilon$-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 lower bound of $1/3$, or the trivial upper bound of $1$, would require significantly new ideas.

1 Proof Overview for Our Main Result

We begin this proof overview by defining a very weak version of Pure-Circuit. An instance of the problem consists of a Boolean circuit using the standard gates NOT, AND, and OR, but with the following tweak: the circuit is allowed to have cycles. A solution to the problem is an assignment of values to each node of the circuit, so that all gates are satisfied. If we are only allowed to assign values in $\{0,1\}$ to the nodes, then it is easy to see that the problem is not a total search problem, i.e., some instances do not have a solution. For example, there is no way to assign consistent values to a cycle of three consecutive NOT gates.

In order to ensure that the problem is total (and can thus be used to prove PPAD-hardness results), we make the value space continuous by extending it to $$. We extend the definition of the logical gates NOT, AND, and OR to non-Boolean inputs in the most permissive way: if at least one input to the gate is not a pure bit (i.e., not in$\{0,1\}$), then the gate is allowed to output any value in$$. The attentive reader might observe that this problem is now trivial to solve: just assign arbitrary values in$(0,1)$ to all the gates.

It is thus clear that the definition of the problem needs to be extended, by adding extra gates or by strengthening existing gates, so that the problem becomes PPAD-hard. However, in order to discover the least amount of additional structure needed to make the problem hard, it is instructive to proceed with this definition for now, and attempt to prove hardness.

In order to prove the PPAD-hardness of the problem, we cannot follow Rubinstein’s approach, which goes through the construction of a continuous Brouwer function, because Pure-Circuit only offers very weak gates. Instead, we proceed via a direct reduction from the StrongSperner problem, a discrete problem that is a computational version of Sperner’s Lemma. The problem was shown to be PPAD-hard by Daskalakis, Skoulakis, and Zampetakis [DSZ21] (who called it the HighD-BiSperner problem), and is the “PPAD-analogue” of the StrongTucker problem which was recently used to prove PPA-hardness results [DFHM22]. This approach completely bypasses the continuous aspect of all such existing hardness reductions and enables us to work with the very weak gates that Pure-Circuit offers.

At a high level, our hardness construction works as follows: the Pure-Circuit instance implements the evaluation of the StrongSperner labeling on some input point $x$ (represented in unary by multiple nodes) and then uses a feedback mechanism to ensure that the circuit is only satisfied if $x$ is a solution to the StrongSperner instance. The full reduction is presented in Section 3, but we mention here the two main obstacles when trying to implement this idea, and how to overcome them.

The input point $\boldsymbol{x}$ might not be represented by a valid bitstring. Indeed, since the gates take values in $$(and values in$(0,1)$essentially do not carry any information), there is no guarantee that the input$x$will be represented by bits$\{0,1\}$. But then the implementation of the StrongSperner labeling (which is given as a Boolean circuit) will also fail. To resolve this issue, we introduce a new gate, the PURIFY gate, which, on any input, outputs two values, with the guarantee that at least one of them is a “pure” bit, i.e., or$1$. If the input is already a pure bit, then both outputs are guaranteed to be copies of the input. Using a binary tree of PURIFY gates, we can now create many copies of$x$, such that most of them consist only of pure bits, and then use the logical gates to compute the StrongSperner labeling correctly on these good copies.

How to implement the feedback mechanism? Given the outputs of the StrongSperner labeling at all the copies of $x$, we now need to provide some kind of feedback to $x$, so that $x$ is forced to change if it is not a solution of StrongSperner. It turns out that this step can be performed if we have access to sorting: given a list of values in $$, sort them from smallest to largest. Unfortunately, this is impossible to achieve with the gates at our disposal, namely standard logical gates and the PURIFY gate. We circumvent this obstacle by observing that: (i) it is sufficient to be able to perform some kind of “weak sorting” (essentially, we only care about pure bits being sorted correctly), and (ii) this weak sorting can be achieved if we make our logical gates robust. For example, the robust version of the AND gate outputs , whenever at least one of its inputs is , irrespective of whether the other input is a pure bit or not.

With these two extensions in hand—namely, the PURIFY gate and the robustness of the logical gates— it is now possible to prove PPAD-hardness of the problem. A very natural question to ask is: Is it really necessary to add both extensions for the problem to be hard? In Appendix A we show that any attempt to weaken the gate-constraints makes the problem polynomial-time solvable. In particular, the introduction of the PURIFY gate is not enough by itself to make the problem PPAD-hard; the robustness of the logical gates is also needed.

The robustness of, say, the AND gate seems like a very natural constraint to impose. It is consistent with the meaning of the logical AND operation, but we also observe in our applications that this “robustness” seems to always be automatically satisfied in all simulations of the AND gate. On the other hand, the PURIFY gate, which might look a bit unnatural or artificial at first, actually corresponds to the simplest possible version of a bit decoder, a crucial tool in all prior works. As mentioned above, we show in Appendix A that these are the minimal gate-constraints that are needed for the problem to be PPAD-hard. In that sense, we argue that Pure-Circuit captures the essence of PPAD-hardness: it consists of the minimal set of ingredients that are needed for a problem to be PPAD-hard.

The attentive reader might have noticed that our gates do not distinguish between different values in $(0,1)$. For this reason, it will be more convenient to use a single symbol to denote such values in the definition of Pure-Circuit (Section 2) and in the rest of this paper. As explained in more detail in Section 2, the symbol “$\bot$” will be used to denote these “garbage” values. In other words, the nodes of the circuit will take values in $\{0,1,\bot\}$ instead of $$.

The Pure-Circuit Problem

In this section we define our new problem Pure-Circuit and state our main result, namely its PPAD-completeness. Before defining Pure-Circuit, we begin by explaining the intuition behind its definition, and how it relates to the Generalized-Circuit (GCircuit) problem.

In the Generalized-Circuit (GCircuit) problem (formally defined in Section 4.1) we are given a circuit and the goal is to assign a value to each node of the circuit so that each gate is computed correctly. Importantly, the circuit is a generalized circuit, meaning that cycles are allowed. If cycles were not allowed, then it would be easy to find values satisfying all gates: just pick arbitrary values for the input gates, and then evaluate the circuit on those inputs.

Every node of GCircuit must be assigned a value in $$, and the gates are arithmetic gates, such as addition, subtraction, multiplication by a constant (with output truncated to lie in$$), and suitably defined logical gates. Reducing from GCircuit is very useful for obtaining hardness of approximation results, because the problem remains PPAD-hard, even when we allow some error at every gate. In the $\varepsilon$-GCircuit problem, the goal is to assign a value in $$to each node of the circuit, so that each gate is computed correctly, up to an additive error of$\pm\varepsilon$.

The problem was first defined by Chen et al. [CDT09], who proved that it is PPAD-hard for inverse polynomial $\varepsilon$, and who used it to prove PPAD-hardness of finding Nash equilibria in bimatrix games. Prior to that, Daskalakis et al. [DGP09] had implicitly proved that it is PPAD-hard for inverse exponential $\varepsilon$. Rubinstein’s [Rub18] breakthrough result proved that there exists some constant $\varepsilon>0$ such that $\varepsilon$-GCircuit remains PPAD-hard.

In order to get strong inapproximability results, it seems necessary to prove hardness of $\varepsilon$-GCircuit for large, explicit, values of $\varepsilon$. Ideally, we would like to obtain hardness for the largest possible $\varepsilon$. While it is unclear what that value is for GCircuit, in theory, as long as $\varepsilon<1$ the output of a gate still carries some information. Namely a gate whose actual output should be cannot take the value $1$.

This observation leads us to define a problem to essentially capture the setting $\varepsilon\to 1$. In that case, a node carries information only if its value is or $1$. Otherwise, its value is irrelevant. As a result, the natural operations to consider in this setting are simple Boolean operations, such as NOT, AND, OR, NAND, and NOR. We only require these gates to output the correct result when their input is relevant, i.e., or $1$. For example, the NOT gate should output $1$ on input , and output on input $1$, but there is no constraint on its output when the input lies in $(0,1)$.

Since values in $(0,1)$ do not carry any information, and are as such interchangeable (e.g., a value $1/2$ can be replaced by $1/3$ without impacting any of the gates), we will instead use the symbol “$\bot$” to denote any and all values in $(0,1)$. In other words, instead of assigning a value in $$to each gate, we will assign a value in$\{0,1,\bot\}$, where$\bot$is interpreted as a “garbage” value, i.e., not corresponding to a pure bit value or$1$. With this new notation, the updated description of the NOT gate would be that it must output$1$on input , it must output on input$1$, and it can output anything (namely, ,$1$, or$\bot$) on input$\bot$.

Unfortunately, if we only allow these logical gates, then the problem is trivial to solve: assigning the “garbage” value $\bot$ (or any value in $(0,1)$ if we use the old notation) to every node will satisfy all gates. Thus, we need a gate that makes this impossible.

To achieve this, we introduce the PURIFY gate: a gate with one input and two outputs, which, intuitively, “purifies” its input. When fed with an actual pure bit, the PURIFY gate outputs two copies of the input bit. However, when the input is not a pure bit, the gate still ensures that at least one of its two outputs is a pure bit. In more detail:

If the input is , then both outputs are .

If the input is $1$, then both outputs are $1$.

If the input is $\bot$, then at least one of the outputs is a pure bit, i.e., or $1$.

Note that the gate is quite “under-defined”. For example, we do not specify which pure bit the gate should output when the input is $\bot$, nor do we specify the output on which this bit appears. This is actually an advantage, because it makes it easier to reduce from the problem, since the less constrained the gates are, the easier it is to simulate them in the target application problem.

The introduction of the PURIFY gate makes the problem non-trivial: if a PURIFY gate appears in the circuit, then assigning the “garbage” value $\bot$ to all nodes is no longer a solution. However, it turns out that one more modification is needed to make the problem PPAD-hard: we have to make the logical gates robust. For the AND gate, this means the following: if one of its two inputs is , then the output is , no matter what the other input is (even if it is not a pure bit, i.e., if it is $\bot$). Similarly, for the OR gate we require that the output be $1$ when at least one of the two inputs is $1$. Robustness is defined analogously for NAND and NOR.

We show that introducing the PURIFY gate and making the logical gates robust is enough to make the problem PPAD-complete. Next, we define the problem formally and state our main result.

In the definition below, we use the PURIFY and NOR gates, because these two gates are enough for the problem to already be PPAD-complete. However, the problem remains hard for various other combinations of gates and restrictions on the interactions between nodes, as we detail in Corollaries 2.2 and 2.3. In Appendix A we discuss the definition in more detail, and explain why any attempt at relaxing the definition (in particular, removing the robustness) makes the problem polynomial-time solvable.

An instance of Pure-Circuit is given by a vertex set $V=[n]$ and a set $G$ of gate-constraints (or just gates). Each gate $g\in G$ is of the form $g=(T,u,v,w)$ where $u,v,w\in V$ are distinct nodes and $T\in\{\textup{{NOR}},\textup{{PURIFY}}\}$ is the type of the gate, with the following interpretation.

If $T=\textup{{NOR}}$, then $u$ and $v$ are the inputs of the gate, and $w$ is its output.

If $T=\textup{{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.

The following theorem is our main technical result and is proved in Section 3.

The Pure-Circuit problem is PPAD-complete.

The most important part of this statement is of course the PPAD-hardness of Pure-Circuit, but let us briefly discuss the other part, namely the PPAD-membership. This is obtained as a byproduct of our results in Section 4, where we reduce Pure-Circuit to various problems that are known to lie in PPAD. However, there is also a more direct way to prove membership in PPAD, and in particular to establish the existence of a solution, and we briefly sketch it here. Indeed, the Pure-Circuit problem can be reduced to the problem of finding a Brouwer fixed point of a continuous function $F$, a problem known to lie in PPAD [Pap94, EY10]. Given an instance of Pure-Circuit with $n$ nodes, the function $F:^{n}\to^{n}$ is constructed by letting $x\in^{n}$ represent an assignment of values to the $n$ nodes, and by defining $F_{i}(x)\in$ as a continuous function that outputs a valid value for the $i$th node, given that the other nodes have values according to assignment $x$ (where any value in $(0,1)$ is interpreted as “$\bot$”). For every type of gate, it is not hard to construct a continuous piecewise-linear function $F_{i}$ (or, in the case of PURIFY, two such functions $F_{i}$ and $F_{j}$) that satisfies the constraints of that type of gate.

Note that the definition of our logical gates essentially follows Kleene’s strong logic of indeterminacy [Kle52], except that undetermined outputs are not required to take value $\bot$, but instead any value in $\{0,1,\bot\}$ can be used. This makes it easier to argue about reductions from Pure-Circuit, since the gadgets implementing the gates have to enforce fewer constraints. As a result of this connection to Kleene’s logic, these gates can in particular be used to implement hazard-free circuits [IKL+19].

1 Alternative Gates and Further Restrictions

In this section, we present various versions of the problem that remain PPAD-complete, in particular versions that use alternative gates and have additional restrictions.

We define the following additional gates.

The Pure-Circuit problem is PPAD-complete, for any of the following choices of gate types:

PURIFY and at least one of $\{\textup{{NOR}},\textup{{NAND}}\}$;

PURIFY, NOT, and at least one of $\{\textup{{OR}},\textup{{AND}}\}$.

This follows from Theorem 2.1 by observing that a NOR gate can always be simulated with the given set of gates. Clearly, NOR can be simulated by first using an OR gate and then a NOT gate. Furthermore, OR can be simulated by NOT and AND by applying De Morgan’s laws. Finally, AND can easily be obtained from NOT and NAND, and NOT can be obtained from NAND and PURIFY as follows: first apply a PURIFY gate, and then use its two outputs as the two inputs to a NAND gate. ∎

The hardness result is also robust with respect to restrictions applied to the 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$. For example, a NOR gate with inputs $u,v$ and output $w$ yields the two edges $(u,w)$ and $(v,w)$. On the other hand, a PURIFY gate with input $u$ and outputs $v,w$ gives the edges $(u,v)$ and $(u,w)$. Since any given node is the output of at most one gate, it immediately follows that the in-degree of every node is at most $2$. However, the out-degree of a node can a priori be arbitrarily large. It is quite easy to show that the problem remains PPAD-complete, even if we severely restrict the interaction graph.

The Pure-Circuit problem remains PPAD-complete, for any choice of gates $\{\textup{{PURIFY}},\textup{{X}},\textup{{Y}}\}$, where $(\textup{{X}},\textup{{Y}})\in\{\textup{{NOT}}\}\times\{\textup{{OR}},\textup{{AND}},\textup{{NOR}},\textup{{NAND}}\}$ or $(\textup{{X}},\textup{{Y}})\in\{\textup{{COPY}}\}\times\{\textup{{NOR}},\textup{{NAND}}\}$ and even if we also simultaneously have all of the following restrictions.

Every node is the input of exactly one gate.

In the interaction graph, the total degree of every node is at most 3. More specifically, for every node, the in- and out-degrees, $d_{in}$ and $d_{out}$, satisfy $(d_{in},d_{out})\in\{(1,1),(2,1),(1,2)\}$.

The proof of this corollary is again quite simple, but a bit tedious, so it is relegated to Appendix B.

Using Corollary 2.3, it is also possible to show that Pure-Circuit with only two gates (namely, PURIFY and one of $\{\textup{{NOR}},\textup{{NAND}}\}$) remains PPAD-complete even if the total degree of every node is at most 4 in the interaction graph. Indeed, NOT gates can be implemented by first using a PURIFY gate and then a NOR/NAND gate. The structural properties of Corollary 2.3 ensure that this yields an interaction graph where the total degree is at most 4 for each node. This can be further reduced to degree 3, if one modifies the definition of Pure-Circuit (Definition 1) so that the two inputs to a NOR/NAND gate are no longer required to be two distinct nodes $u$ and $v$, but can possibly be the same node $u=v$. However, if the definition is modified in that way, then one must be careful when reducing from Pure-Circuit to make sure to take into account the possibility that $u=v$ when constructing the gadget for a NOR/NAND gate.

PPAD-completeness of Pure-Circuit

This section proves our main technical result, namely that Pure-Circuit is PPAD-complete (Theorem 2.1). We note that membership in PPAD follows immediately from the reduction of the problem to GCircuit in Section 4.1. In order to establish the PPAD-hardness, we present a polynomial-time reduction from a PPAD-complete problem to Pure-Circuit. The canonical PPAD-complete problem is the End-of-Line problem, but, as is usually the case, we do not reduce directly from End-of-Line, but from a problem with topological structure instead, which we introduce next.

We will reduce from the StrongSperner problem, which is based on a variant of Sperner’s lemma [Spe28]. This problem is in essence the same as the HighD-BiSperner problem defined by Daskalakis et al. [DSZ21] and used to prove PPAD-hardness of a problem related to constrained min-max optimization. Furthermore, the corresponding “strong” variant of Tucker’s lemma was used by Deligkas et al. [DFHM22] to provide improved PPA-hardness results for the consensus-halving problem in fair division.

A Boolean circuit computing a labeling $\lambda:[M]^{N}\to\{-1,+1\}^{N}$ satisfying the following boundary conditions for every $i\in[N]$:

if $x_{i}=1$, then $[\lambda(x)]_{i}=+1$;

if $x_{i}=M$, then $[\lambda(x)]_{i}=-1$.

Note that the requirement that a solution should consist of exactly $N$ points is without loss of generality. If we find less than $N$ points that cover all labels, then we can simply re-use the same points multiple times to obtain a list of $N$ points that cover all labels (there is no requirement on them being distinct). If we find more than $N$ points that cover all labels, then it is easy to see that we can extract a subset of $N$ points that still cover all labels in polynomial time [DFHM22, Lemma 3.1].

StrongSperner is PPAD-hard, even when $M$ is only polynomially large (i.e., given in unary in the input).

This was proven by Daskalakis et al. [DSZ21] by reducing from the SuccinctBrouwer problem, which had been proven PPAD-hard by Rubinstein [Rub16]. The PPAD-hardness can also be proved by a more direct reduction from End-of-Line. Indeed, End-of-Line can be reduced to StrongSperner with $N=2$ and exponentially large $M$ by using the techniques of Chen and Deng [CD09]. Then, a snake embedding technique [CDT09, DFHM22] can be used to obtain hardness for the high-dimensional version with small $M$, in fact, even for constant $M$. For our purposes, the hardness for polynomially large $M$ is sufficient.

2 Reduction from StrongSperner to Pure-Circuit

Consider an instance $\lambda:[M]^{N}\to\{-1,+1\}^{N}$ of StrongSperner, where $\lambda$ is given as a Boolean circuit and $M$ is only polynomially large (i.e., given in unary). We will now show how to construct an instance of Pure-Circuit in polynomial time such that from any correct assignment to the nodes, we can extract a solution to the StrongSperner instance in polynomial time. We will make use of the gates PURIFY, AND, OR, NOT, COPY. All these gates can easily be simulated using the two gates PURIFY and NOR, by the arguments in the proof of Corollary 2.2.

We begin the construction of the Pure-Circuit instance by creating nodes $u_{i,1},\dots,u_{i,M}$ for each $i\in[N]$. We call these nodes the original inputs, and we think of $u_{i,1},\dots,u_{i,M}$ as being the unary representation of an element in $[M]$. Of course, this only makes sense when all these nodes are assigned pure bit values, i.e., or $1$. In general, this will not be the case. The rest of the instance can be divided into four parts: the purification stage, the circuit stage, the sorting stage, and the selection stage.

For each $(i,j)\in[N]\times[M]$, we construct a binary tree of PURIFY gates that is rooted at $u_{i,j}$ and has leaves $u_{i,j}^{(1)},\dots,u_{i,j}^{(K)}$.

There are at least $K-NM$ good copies, i.e., $|G|\geq K-NM$.

Observe that in a binary tree of PURIFY gates, if some node has some pure value $b\in\{0,1\}$, then all nodes in the subtree rooted at this node also have value $b$. Applying this observation at the root of the tree rooted at $u_{i,j}$, we immediately obtain part 2 of the statement.

We assume, without loss of generality, that $\lambda$ is given as a Boolean circuit $C:(\{0,1\}^{M})^{N}\to\{0,1\}^{N}$ using gates AND, OR, NOT, and, on input $z\in(\{0,1\}^{M})^{N}$:

The circuit $C$ outputs $\lambda(\overline{z_{1}},\dots,\overline{z_{N}})\in\{-1,+1\}^{N}$, where a $-1$ output is represented by a , and a $+1$ output by a $1$. To keep things simple, in the rest of this exposition we will abuse notation and think of $\lambda$ as outputting labels in $\{0,1\}^{N}$.

If the circuit is not originally in this form, then it can be brought in this form in polynomial time.

In the circuit stage, we construct $K$ separate copies of the circuit $C$, using the AND, OR, and NOT gates. For each $k\in[K]$, the $k$th copy $C_{k}$ takes as input the nodes $(u_{i,j}^{(k)})_{(i,j)\in[N]\times[M]}$ and we denote its output nodes by $v_{1}^{(k)},\dots,v_{N}^{(k)}$. Since the gates always have correct output when the inputs are pure bits, we immediately obtain the following.

In this stage, for each $i\in[N]$, we would like to have a gadget that takes as input the list of nodes $v_{i}^{(1)},\dots,v_{i}^{(K)}$ (namely, the list of $i$th outputs of the circuits $C_{1},\dots,C_{K}$) and outputs the nodes $w_{i}^{(1)},\dots,w_{i}^{(K)}$, such that these output nodes are a sorted list of the values of the input nodes (where we think of the values as being ordered $0<\bot<1$). Unfortunately, this is not possible given the gates we have at our disposal. However, it turns out that we can do some kind of “weak” sorting by using the robustness of the AND and OR gates (i.e., the fact that AND on input and $s$, always outputs , no matter what $s\in\{0,1,\bot\}$ is).

For now assume that we consider values in $$(instead of$\{0,1,\bot\}$) and that we have access to a comparator gate that takes two inputs$s_{1}$and$s_{2}$and outputs$t_{1}$and$t_{2}$, such that$t_{1},t_{2}$is the sorted list$s_{1},s_{2}$. Formally, we can write this as$t_{1}:=\min\{s_{1},s_{2}\}$and$t_{2}:=\max\{s_{1},s_{2}\}$. Using comparator gates, it is easy to construct a circuit that takes$K$inputs and outputs them in sorted order. Indeed, we can directly implement a sorting network [Knu98], for example. Even a very naive approach will yield such a circuit of polynomial size, which is all we need. We implement this circuit with inputs$v_{i}^{(1)},\dots,v_{i}^{(K)}$and outputs$w_{i}^{(1)},\dots,w_{i}^{(K)}$in our Pure-Circuit instance, by replacing every comparator gate by AND and OR gates. Namely, to implement a comparator gate with inputs$s_{1},s_{2}$and outputs$t_{1},t_{2}$, we use an AND gate with inputs$s_{1},s_{2}$and output$t_{1}$, and an OR gate with inputs$s_{1},s_{2}$and output$t_{2}$. The robustness of the AND and OR gates allows us to prove that this sorting gadget sorts the pure bit values correctly, in the following sense.

We prove the claim by induction. Clearly, all input nodes satisfy the claim. Now consider some node $t_{1}$ that is the $\min$-output of a comparator gate with inputs $s_{1}$ and $s_{2}$, that both satisfy the claim. Recall that this gate will be implemented in the Pure-Circuit by an AND gate with inputs $s_{1},s_{2}$ and output $t_{1}$. If the ideal circuit assigns value $1/2$ to $t_{1}$, then the claim trivially holds for $t_{1}$. If the ideal circuit assigns value $1$ to $t_{1}$, then both $s_{1}$ and $s_{2}$ must have value $1$ in the ideal circuit. Since the claim holds for $s_{1}$ and $s_{2}$, they also have value $1$ in Pure-Circuit, and so the AND gate will ensure that $t_{1}$ also has value $1$, thus satisfying the claim. Finally, if the ideal circuit assigns value to $t_{1}$, then it must also have assigned value to at least one of $s_{1}$ or $s_{2}$. But then, by the claim, Pure-Circuit also assigns value to at least one of $s_{1}$ or $s_{2}$, and the robustness of the AND gate ensures that $t_{1}$ also has value . The same argument also works with $\max$ and OR instead. ∎

Note that Lemma 3.4 only guarantees a “weak” type of sorting: some parts of the output list might not be correctly ordered, and the list of output values might not be a permutation of the input values (namely, it can happen that there are more ’s and/or $1$’s in the output list than in the input list). However, this “weak” sorting will be enough for our needs as we will see below.

Since the list $w_{i}^{(1)},\dots,w_{i}^{(K)}$, is now “sorted”, we can select $M$ nodes from it in such a way that at most one node does not have a pure value. Indeed, this can be achieved by selecting nodes that are sufficiently far apart from each other. We thus select the nodes $(w_{i}^{(j\cdot 2NM)})_{j\in[M]}$ and copy their values onto the original input nodes $(u_{i,j})_{j\in[M]}$. Namely, for each $j\in[M]$ we introduce a COPY gate with input $w_{i}^{(j\cdot 2NM)}$ and output $u_{i,j}$. Recall that $K=3NM^{2}\geq M\cdot 2NM$, so this is well defined.

This selection procedure ensures that two nice properties hold. First, as mentioned above, at most one of the selected nodes does not have a pure value. This is due to the fact that we select nodes that are far apart from each other in the “sorted” list, and all nodes with non-pure values lie close together in that list. Second, if all good copies agree that the $i$th output is, say, $1$, then all of the selected nodes will have value $1$. This is due to the fact that the “sorted” list will contain very few values that are not $1$, and these values will lie at the very beginning of the list. Since we do not select any nodes from the beginning of the list (the first node that is selected is at index $2NM$), we will thus only select nodes with value $1$. A similar argument also applies to the case where all good copies agree that the $i$th output is . In that case, we use the fact that we do not select any nodes that lie close to the end of the list. We formalize these arguments in the proof of the following lemma.

All good copies are close to each other: $\|u^{(k)}-u^{(k^{\prime})}\|_{\infty}\leq 1$ for all $k,k^{\prime}\in G$.

The description of the reduction is now complete. We have constructed a valid instance of Pure-Circuit in polynomial time. In particular, note that every node is the output of exactly one gate. To complete the proof, it remains to prove that from any solution of the Pure-Circuit instance we can extract a solution to StrongSperner in polynomial time. We do this in the following final lemma.

The points $\{u^{(k)}:k\in G\}\subseteq[M]^{N}$ yield a solution to the StrongSperner instance $\lambda$.

Applications

In this section, we derive strong inapproximability lower bounds for PPAD-complete problems, by reducing from Pure-Circuit.

The $\varepsilon$-GCircuit problem was introduced by Chen, Deng, and Teng [CDT09]. In this section, we show that $\varepsilon$-GCircuit is PPAD-hard for all $\varepsilon<0.1$.

A generalized circuit is a tuple $(V,T)$, where $V$ is a set of nodes, and $T$ is a set of gates. Each gate $t\in T$ is a five-tuple $(G,u,v,w,c)$, where $G$ is a gate type from the set $\{G_{c},G_{\times c},G_{=},G_{+},G_{-},G_{<},G_{\lor},G_{\land},G_{\lnot}\}$, $u,v\in V\cup\{\textsf{nil}\}$ are input variables, $w\in V$ is an output variable, and $c\in\cup\{\textsf{nil}\}$ is a rational constant.

The following requirements must be satisfied for each gate $(G,u,v,w,c)\in T$.

$G_{c}$ gates take no input variables and use a constant in $$. So$u=v=\textsf{nil}$and$c\in$whenever$G=G_{c}$.

$G_{\times c}$ gates take one input variable and a constant. So $u\in V$, $v=\textsf{nil}$, and $c\in$ whenever $G=G_{\times c}$.

$G_{=}$ and $G_{\lnot}$ gates take one input variable and do not use a constant. So $u\in V$, $v=c=\textsf{nil}$, whenever $G\in\{G_{=},G_{\lnot}\}$.

All other gates take two input variables and do not use a constant. So $u\in V$, $v\in V$, and $c=\textsf{nil}$ whenever $G\notin\{G_{c},G_{\times c},G_{=},G_{\lnot}\}$.

Every variable in $V$ is the output variable for exactly one gate. More formally, for each variable $w\in V$, there is exactly one gate $t\in T$ such that $t=(G,u,v,w,c)$.

Here the notation $a=b\pm\varepsilon$ is used as a shorthand for $a\in[b-\varepsilon,b+\varepsilon]$. We will also make use of gates of type $(G_{>},u,v,w,\textsf{nil})$ which enforce the constraint

Gates of type $G_{>}$ can be easily built by using a $G_{\lnot}$ gate to negate the output of a $G_{<}$ gate.

In the remainder of this section, we prove the following result.

$\varepsilon$-GCircuit is PPAD-hard for every $\varepsilon<0.1$.

We will reduce from the Pure-Circuit problem that uses the gates NOR and PURIFY, which we showed to be PPAD-hard in Theorem 2.1. We will encode 0 values in the Pure-Circuit problem as values in the range $[0,\varepsilon]$ in GCircuit, while 1 values will be encoded as values in the range $[1-\varepsilon,1]$. Then, each gate from Pure-Circuit will be simulated by a combination of gates in the GCircuit instance.

A NOR gate $(\textup{{NOR}},u,v,w)$ will be simulated by GCircuit gates that compute

which requires us to use $G_{+}$, $G_{<}$ and $G_{c}$. We claim that this gate works for any $\varepsilon<1/9$.

2 Polymatrix Games

In this section, we show a number of results for polymatrix games. After defining this class of games and the equilibrium notions of interest, we provide a simple algorithm that computes a $1/3$-well-supported Nash equilibrium (WSNE) in polynomial time (Theorem 4.2). We then show that this algorithm is in fact optimal, by proving hardness of finding $\varepsilon$-WSNE for all $\varepsilon<1/3$ (Theorem 4.3). Next, we also prove hardness of computing $\varepsilon$-Nash equilibria for all $\varepsilon<2\sqrt{73}-17\approx 0.088$ (Theorem 4.4). Both of these hardness results hold for degree 3 bipartite games with at most two strategies per player. Finally, we show that the hardness result for $\varepsilon$-WSNE also holds for win-lose polymatrix games in degree 7 bipartite games with at most two strategies per player (Theorem 4.6).

A polymatrix game is defined by an undirected graph $(V,E)$, where each vertex represents a player, and we use $n=|V|$ to denote the number of players in the game. Each player $i\in V$ has a fixed number of actions (also called pure strategies) given by $m_{i}$. For each edge $(i,j)\in E$, there is an $m_{i}\times m_{j}$ matrix $A_{ij}$ giving the payoffs that player $i$ obtains from their interaction with player $j$, and likewise there is an $m_{j}\times m_{i}$ matrix $A_{ji}$ giving payoffs for player $j$’s interaction with player $i$.

A strategy profile specifies a mixed strategy for each of the players, and so the set of strategy profiles is given by $\Sigma=\Delta^{m_{1}-1}\times\dots\times\Delta^{m_{n}-1}$. For each strategy profile $\mathbf{s}=(s_{1},s_{2},\dots,s_{n})\in\Sigma$, the payoff to player $i$ is

In other words, the payoff obtained by player $i$ is the sum of the payoffs obtained from the interaction of $i$ with every neighbouring player $j$. We denote by $\mathbf{s}_{-i}$ (resp. $\mathbf{a}_{-i}$) the partial strategy profile (resp. partial action profile) consisting of the strategies (resp. actions) of all players except $i$. For any particular pure strategy $k\in[m_{i}]$, the payoff when player $i$ plays $k$, and all other players play according to $\mathbf{s}$ is denoted by

where $e_{k}$ is the $m_{i}$-dimensional vector with all entries set to , except for the $k$-th that is set to $1$.

A pure strategy $k$ is a best response for player $i$ in strategy profile $\mathbf{s}$ if it achieves the maximum payoff over all the pure strategies available to player $i$, meaning that

Strategy $k$ is an $\varepsilon$-best response if it is within $\varepsilon$ of being a best response, meaning that

The best response payoff for player $i$ is the payoff associated with the best response strategies, which we denote as

A strategy profile $\mathbf{s}$ is a Nash equilibrium if every player achieves their best response payoff, meaning that $\text{br}_{i}(\mathbf{s}_{-i})=u_{i}(\mathbf{s})$ for all players $i$. The approximation notions that will be of interest to us in this section are the following.

A strategy profile $\mathbf{s}$ is an $\varepsilon$-Nash equilibrium ($\varepsilon$-NE) if every player’s payoff is within $\varepsilon$ of their best response payoff. Formally,

A strategy profile $\mathbf{s}$ is an $\varepsilon$-well-supported Nash equilibrium ($\varepsilon$-WSNE) if every player only plays strategies that are $\varepsilon$-best responses, meaning that for all $i$ we have that $\textup{{supp}}(s_{i})$ contains only $\varepsilon$-best response strategies. Formally,

Note that $\varepsilon$-NE and $\varepsilon$-WSNE are both additive notions of approximation, and so values of $\varepsilon$ cannot normally be compared across games, since doubling all payoffs in the game would double the value of $\varepsilon$, for example. To deal with this, it is common to normalize the payoffs of the game so that the maximum possible payoff is 1 and the minimum possible payoff is 0, which allows us to meaningfully compare values of $\varepsilon$ across games.

We adopt the normalization scheme for polymatrix games given by Deligkas et al. [DFSS17], which is a particularly restrictive scheme, but doing so will allow our lower bounds to be compared to the $0.5+\delta$ upper bound for finding $\varepsilon$-NEs given in that paper.

Then, if $d(i)$ denotes the degree of player $i$ in $(V,E)$, we apply the following transformation to each payoff $z$ in each payoff matrix $A_{ij}$

If $U_{i}=L_{i}$, then we simply set $T(z)=0$. This ensures that each player’s maximum possible payoff is $1$, and their minimum possible payoff is .

In our hardness reductions, we will directly build games that are already normalized, meaning that $U_{i}=1$ and $L_{i}=0$ for all players $i$, so no extra normalization step is required.

2.1 A Simple Algorithm for 𝟏/𝟑13\boldsymbol{1/3}-WSNE in Two-Action Polymatrix Games

In this section we present a simple polynomial-time algorithm for computing a $1/3$-WSNE in a two-action polymatrix game. We begin with a description of the algorithm. The algorithm proceeds in two steps:

In the first step of the algorithm, we check if there exists some player $i$ such that one of its two actions is always a $1/3$-best response, no matter what actions the other players pick. More formally, we check if there exists a player $i$ and an action $k\in\{0,1\}$ such that $u_{i}(k,\mathbf{s}_{-i})\geq\max\{u_{i}(0,\mathbf{s}_{-i}),u_{i}(1,\mathbf{s}_{-i})\}-1/3$ for all strategy profiles $\mathbf{s}$. If we find such a player $i$, then we fix their strategy to always play action $k$, and we remove them from the game, while also updating the payoffs of the other players to reflect the fact that player $i$ always plays action $k$. Note that no matter how we fix the strategies of the remaining players later in the algorithm, player $i$ is guaranteed to play a $1/3$-best response action in the original game.

After removing player $i$ from the game, and updating the payoffs, we again check if there exists some player $j$ with a $1/3$-best response action, and if so, fix their strategy and remove them from the game, as above. After at most $n$ iterations, we are left with a game where none of the remaining players has an action that is always a $1/3$-best response.

In the second step of the algorithm, we simply fix the strategies of the remaining players so that they mix uniformly between their two actions, i.e., they play action with probability $1/2$, and action $1$ with probability $1/2$.

We note that the simple approach used by the algorithm is essentially the same as an algorithm given by Liu et al. [LLD21] for computation of exact equilibria in very sparse win-lose polymatrix games. We now prove the following.

The algorithm computes a $1/3$-WSNE in polynomial time in two-action polymatrix games.

The algorithm clearly runs in polynomial time. To prove its correctness, it suffices to show that for the remaining players (i.e., those that were not removed during Step 1) both their actions are $1/3$-best-responses, when all the other remaining players mix uniformly.

2.2 Hardness for 𝜺𝜺\boldsymbol{\varepsilon}-WSNE

In this section we prove that computing an $\varepsilon$-WSNE is PPAD-hard for any $\varepsilon<1/3$, even in two-action polymatrix games. In particular, this shows that the simple algorithm presented in the previous section is optimal.

It is PPAD-hard to find an $\varepsilon$-WSNE in a polymatrix game for all $\varepsilon<1/3$, even in degree 3 bipartite games with two strategies per player.

We reduce from the variant of Pure-Circuit that uses NOT, AND, and PURIFY gates, and we will specifically reduce from the hardness result given in Corollary 2.3, since it will give us extra properties for the hard polymatrix games.

Given an instance $(V,G)$ of Pure-Circuit, we will build a polymatrix game with vertex set $V$, meaning each player in the game will simulate a variable from Pure-Circuit. Each player $i$ will have exactly two strategies, which we will denote as zero and one. The strategy $s_{i}$ of player $i$ will encode the value of the variable in the following way.

If $s_{i}$ places all probability on zero, then this corresponds to setting variable $i$ to 0.

If $s_{i}$ places all probability on one, then this corresponds to setting variable $i$ to 1.

If $s_{i}$ is a strictly mixed strategy, then this corresponds to setting variable $i$ to $\bot$.

The edges of the game will simulate the gates. The definition of Pure-Circuit requires that each variable $v$ is the output of exactly one gate $g$. An important property of our reduction is that the player representing $v$ only receives non-zero payoffs from the inputs to the gate $g$, and receives zero payoffs from any other gates that use $v$ as an input. This means that we can reason about the equilibrium condition of each of the gates independently, without worrying about where the values computed by those gates are used.

For a gate $g=(\textup{{NOT}},u,v)$, the player $v$, who represents the output variable, will play the following bimatrix game against $u$, who represents the input variable.

$v$$u$zeroonezeroone$1$$1$ This depiction of a bimatrix game shows the matrices $A_{vu}$ and $A_{uv}$, with the payoffs for $v$ being shown in the bottom-left of each cell, and the payoffs for $u$ being shown in the top-right.

We claim that this gate will work for all $\varepsilon<1$.

If $u$ plays zero as a pure strategy, then one gives payoff $1$ to $v$ and zero gives payoff to $v$. So in any $\varepsilon$-WSNE with $\varepsilon<1$, only one can be an $\varepsilon$-best response for $v$, meaning that $v$ must play one as a pure strategy, as required by the constraints of the NOT gate.

Using identical reasoning, if $u$ plays one as a pure strategy, then $v$ must play zero as a pure strategy in any $\varepsilon$-WSNE.

If $u$ plays a strictly mixed strategy, then the NOT gate places no constraints on the output, so we need not prove anything about $v$’s strategy.

For a gate $g=(\textup{{AND}},u,v,w)$, the player $w$, who represents the output variable, will play the following matrix games against $u$ and $v$, who represent the input variables.

$w$$u$zeroonezeroone$\frac{1}{2}<span class="katex-display"><span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML" display="block"><semantics><mrow><mfrac><mn>1</mn><mn>6</mn></mfrac></mrow><annotation encoding="application/x-tex">\frac{1}{6}</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:2.0074em;vertical-align:-0.686em;"></span><span class="mord"><span class="mopen nulldelimiter"></span><span class="mfrac"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:1.3214em;"><span style="top:-2.314em;"><span class="pstrut" style="height:3em;"></span><span class="mord"><span class="mord">6</span></span></span><span style="top:-3.23em;"><span class="pstrut" style="height:3em;"></span><span class="frac-line" style="border-bottom-width:0.04em;"></span></span><span style="top:-3.677em;"><span class="pstrut" style="height:3em;"></span><span class="mord"><span class="mord">1</span></span></span></span><span class="vlist-s">​</span></span><span class="vlist-r"><span class="vlist" style="height:0.686em;"><span></span></span></span></span></span><span class="mclose nulldelimiter"></span></span></span></span></span></span>w$$v$zeroonezeroone$\frac{1}{2}$$\frac{1}{6}$ We claim that this gate will work for all $\varepsilon<\frac{1}{3}$.

If both $u$ and $v$ play one as a pure strategy, then the payoff to $w$ for playing zero is , and the payoff to $w$ for playing one is $1/6+1/6=1/3$. So, if $\varepsilon<\frac{1}{3}$, then in all $\varepsilon$-WSNEs the only $\varepsilon$-best response for $w$ is one, as required by the constraints of the AND gate.

If at least one of $u$ and $v$ play zero as a pure strategy, then the payoff to $w$ for playing zero is at least $1/2$, while the payoff to $w$ for playing one is at most $1/6$. So, if $\varepsilon<\frac{1}{3}$, then in all $\varepsilon$-WSNEs the only $\varepsilon$-best response for $w$ is zero, as required by the constraints of the AND gate.

The AND gate places no other constraints on the variable $w$, so we can ignore all other cases, e.g., the case where both $u$ and $v$ play strictly mixed strategies.