Inapproximability of Nash Equilibrium

Our results

• Finding a constant-ε approximate Nash equilibrium is PPAD-complete even in degree 3 bipartite polymatrix games where each player has two actions.Source: Our results · p. 2
• Constant-ε approximate Bayesian Nash equilibrium is PPAD-complete for two-player incomplete-information games with a constant number of actions per player.Source: Our results · p. 3
• Relative ε-Well Supported Nash Equilibrium remains PPAD-complete in two-player games even when all payoffs are positive.Source: Our results · p. 3
• For non-monotone utility families, finding a constant-ε-tight approximate market equilibrium is PPAD-hard when each trader has linear utility or utility from that family.Source: Our results · pp. 3–4
• Constant-ε-tight market equilibrium is PPAD-complete for additively separable, concave piecewise-linear utilities.Source: Our results · p. 4
• Constant-ε approximate solutions to generalized circuits with fan-out 2 remain PPAD-complete.Source: Our results · p. 4
• A constant-β approximate competitive equilibrium from equal incomes is PPAD-complete to find, with market-clearing error and endowment inequality as its two approximation parameters.Source: Our results · p. 5

1.1 Related works

• Compared with prior work, the results extend small-error hardness to simpler games and approximate Nash equilibrium, while establishing membership in PPAD for bounded-degree graphical games.Source: §1.1 · p. 5

• The proof chain reduces EndOfTheLine to an approximate fixed point, then to a generalized circuit, then to approximate Nash equilibrium.Source: §2 · p. 7
• The final reduction uses game gadgets for well-supported equilibrium and converts that guarantee to approximate Nash equilibrium in bounded-degree graphical games.Source: §2 · p. 7
• The main technical step reduces approximate fixed points of a particular continuous function to approximate solutions of generalized circuits.Source: §2 · p. 7

Obtaining a constant hardness of ϵ-Gcircuit

• The circuit-simulation challenge is deciding which subcube contains inputs near a facet when approximate gates and brittle comparators are used.The gadget comparison marks facet-near points as triangles, sufficiently distant points as circles, and a corner safe zone where subcube parsing is unnecessary.Source: Obtaining a constant hardness of… · pp. 8–9
• Earlier approaches averaged over a ball or polynomially many nearby translations; the former scales poorly with dimension, while the latter requires translations to remain close.Ball discretization has exponentially many points in polynomial dimensions; equiangle sampling uses polynomially many translations that must be polynomially close.Source: Obtaining a constant hardness of… · p. 8
• When an input lies near multiple facets, its displacement is approximately the same across subcubes, so only a constant number of samples are needed.At most one sampled point can then be too close to a facet.Source: Obtaining a constant hardness of… · pp. 8–9
• Approximate logical gates can be concatenated without accumulating errors when their inputs are unambiguous bits.To bound fan-out, the construction copies logical outputs through binary trees and converts arithmetic outputs to unary representation before copying.Source: Obtaining a constant hardness of… · pp. 9–10, A richer set of gates · p. 10

No averaging gadget

• A no-averaging alternative would identify proximity to a facet without choosing its side, then stitch together corner, facet, and interior gadgets.Near corners, the displacement is the same regardless of the subcube, so parsing the subcube is unnecessary there.Source: No averaging gadget · p. 10

A richer set of gates

• A simpler, somewhat weaker reduction gives PPAD-completeness for degree-3 graphical games with a constant number of actions per player.Source: A richer set of gates · p. 10
• The hardest proof step is implementing the Brouwer function with the restricted generalized-circuit gate set; more expressive gates could simplify it.Source: A richer set of gates · p. 11
• In the sketched circuit-to-game reduction, each circuit line becomes a player, and an O(ϵ^2)-WSNE makes the output player choose the strategy nearest the expected gate output.The sketched generalization allows bounded-fan-in and bounded-fan-out gates computing c-Lipschitz functions for constant c.Source: A richer set of gates · p. 11

3 Preliminaries

• EndOfTheLine is PPAD-complete: its circuits define incoming and outgoing edges on vertices, and the task is to find another odd-degree vertex or expose an inconsistency.The problem was implicit in and explicitly defined in.Source: The EndOfTheLine problem · p. 12
• Every ϵ-WSNE is an ϵ-ANE, but not conversely; in a graphical game with incoming degree d_in, an ϵ-ANE yields a Θ(√(ϵd_in))-WSNE.The passage also cautions that this conversion is unlikely to establish a query-complexity lower bound.Source: §3.1 · p. 13

3.2 The ϵ-Gcircuit problem

• Generalized circuits use cycles to represent fixed points, and ϵ-Gcircuit asks for an assignment approximately satisfying every gate; brittle comparators are undefined near equality, a difficulty addressed by an averaging gadget.When gates compute continuous functions on [0, 1], a satisfying assignment exists by Brouwer’s fixed point theorem.Source: §3.2 · pp. 13–15

3.3 Max-norm Geometry

• An ϵ-fixed point of an M-Lipschitz function on [0, 1]^n is PPAD-hard to find for some constant ϵ, though the paper notes its main theorem needs additional construction-specific properties.The proof embeds EndOfTheLine as vertex-disjoint paths and constructs a continuous function whose fixed points correspond to path endpoints.Source: §4 · p. 16

4.1 Embedding the EndOfTheLine graph as paths in {0, 1}2n+1

• The embedding maps each EndOfTheLine edge to a path in a (2n + 1)-dimensional hypercube, preserving path endpoints and making it PPAD-hard to find another path endpoint.The construction stores the current and next vertices in separate n-bit coordinate blocks, with a final bit controlling whether the path computes or copies the next vertex.Source: §4.1 · pp. 16–17

4.2 Continuous mapping on [0, 1]2n+2

• The mapping g is O(1)-Lipschitz, has infinity norm Ω(1) at every point not corresponding to a path endpoint, and is computable in polynomial time using S and P.Source: §4.2 · p. 17

4.2.2 Default displacement; 4.2.4 Outside the picture

• The default displacement points upward at corners, outer facets of tube subcubes, and non-tube subcubes; it also points upward in the frame and below the slice, while the top-facet displacement outside the picture stays O(1)-Lipschitz and Ω(1) in magnitude.Source: §4.2.2 · p. 18, §4.2.4 · p. 22

4.2.3 Displacement at a tube

• Inside a tube, the displacement flows along the path at its center, toward the center nearby, and against the path farther out, while interpolation preserves O(1)-Lipschitzness and Ω(1) magnitude.Radial and angular interpolation avoid cancellation in the displacement.Source: §4.2.3 · pp. 19–20

4.2.4 Outside the picture

• On the slice’s top facet, all points except the top of the home subcube point upward; the construction uses radial interpolation and then Cartesian interpolation to reach the hypercube.Radial interpolation is used for r in (0, h/8) and (h/8, h/4).Source: §4.2.4 · p. 22

5 From Brouwer to ϵ-Gcircuit

• ϵ-Gcircuit is PPAD-complete, with the construction organized around sampling, displacement computation, summation, and loop-closing.The construction uses constant-size sampling; its latter two parts are essentially identical to.Source: §5 · pp. 22, 24

5.1.1 If-Else

• The If-Else subroutine uses generalized-circuit gates to implement a simple conditional selection.The paper introduces it as a building block for implementing more involved cases.Source: §5.1.1 · p. 24

5.1.2 Multiply

• Multiply uses unary threshold representations and summation to approximate a · b with O(√ϵ) error.Its threshold gates contribute an aggregate error of O(√ϵ).Source: §5.1.2 · pp. 25–27

5.1.3 Divide

• Divide approximates a / b with error O(√ϵ) / b when b and ϵ are bounded away from zero.The stated error is a constant-factor increase under that condition.Source: §5.1.3 · p. 27

5.1.4 Max

• Max uses unary representations and threshold tests to approximate the maximum of its inputs.The threshold output is 1 ± ϵ when max_i x[ai] > k√ϵ + O(ϵ).Source: §5.1.4 · pp. 29–30

5.1.5 Interpolate

• Interpolate combines a and b according to their weights, with x[c](x[wa] + x[wb]) = x[wa]x[a] + x[wb]x[b] ± O(…).The relation is stated for any ϵ-approximate solution to the Interpolate subroutine.Source: §5.1.5 · p. 31

5.2 Equiangle sampling segment

• Equiangle averaging limits boundary-related error: if any sample is not a corner point, at most one sample is a boundary point, yielding error at most √ϵ.The displacement is computed separately for each sample and averaged; the circuit constructs the sample set using (1/√ϵ) auxiliary nodes.Source: §5.2 · pp. 33–34

5.3 Computing the displacement

• The displacement circuit O(√ϵ)-approximately simulates the Hirsch et al. displacement by extracting the subcube and path information, then computing the local displacement.Its stages include finding the subcube’s previous and next path vertices, the entrance and exit facets, and the relevant local coordinates.Source: §5.3 · p. 34, Extract b ∈{0, 1}2n+2 · p. 35, Neighbors in H · p. 35
• An ϵ-approximate binary encoding represents the previous and next vertices of H up to ϵ error.The last input bit is ignored, while the last output bit distinguishes starting and ending points; the zero starting point follows a special convention.Source: Neighbors in H · p. 35

Entrance and exit facets

• The constructed entrance and exit centers approximate the corresponding facet centers when the encoded values are ϵ-approximate binary vectors.Knowing the path’s entrance coordinate determines its direction in the encoded hypercube; non-trivial starting points and endpoints use the subcube center for the corresponding facet center.Source: Entrance and exit facets · p. 36

Max-norm polar coordinates

• For interior points, the computed max-norm radii approximate distances to the entrance and exit centers within O(√ϵ), while the direction vectors have errors scaling as O(√ϵ/r).Division introduces O(√ϵ/r_in) error, which suffices because the direction is multiplied by r_in when interpolating near the facet.Source: Max-norm polar coordinates · pp. 36–37

The final displacement

• For non-corner interior points, interpolation approximates the Hirsch et al. displacement; corner points are specially detected and assigned a corner displacement.When a point is close to both facets, interpolation may be inaccurate, requiring a larger corner threshold and final error than Θ(√ϵ); the authors note this may be avoidable with more careful algorithms.Source: The final displacement · pp. 37–38

5.4 Summing the displacement vectors

• The summed displacement vectors approximate the target displacement with O(√ϵ) error contributions from exceptional points, summation, and the λ-Lipschitz variation of g.The proof notes that at most one point is neither interior nor a corner point; the distance between the sampled points also contributes O(√ϵ).Source: §5.4 · p. 39

6 ϵ-Gcircuit with fan-out 2

• Constant-ϵ generalized circuits with fan-out 2 are PPAD-complete.The reduction converts a general ϵ′-Gcircuit instance to fan-out 2 with ϵ′ = Θ(√ϵ).Source: §6 · p. 39
• Binary trees of equality gates accumulate Θ(ϵ · log n) error, so the earlier fan-out reduction fails for this setting.The construction instead distributes logical-gate outputs, whose error does not amplify under concatenation.Source: §6 · pp. 39–40
• For constant ϵ and ϵ′, the fan-out reduction increases circuit size by a factor of Θ(1/ϵ′).The unary representation has constant size, and the number of new gates is proportional to the original fan-out.Source: §6 · p. 40

7 From ϵ-Gcircuit to ϵ²-ANE

• The reduction takes an ϵ-approximate generalized-circuit solution to a Θ(ϵ²)-approximate Nash equilibrium through a degree-3 polymatrix ϵ-WSNE.The cited construction is implicit in Daskalakis et al..Source: §7 · p. 41
• The G×ζ gadget enforces p[v2] = min(ζp[v1], 1) ± ϵ in every ϵ-WSNE.Here p[u] is the probability player u assigns to strategy 1.Source: §7 · p. 42

7.1 From √ϵ-WSNE to Θ (ϵ)-ANE

• An ϵ-ANE in a graphical game with payoffs in [0, 1] and incoming degree d_in yields a √ϵ · (√ϵ + 1 + 4d_in)-WSNE in polynomial time.The section also states that the √ϵ-WSNE to Θ(ϵ)-ANE conversion extends to constant-degree graphical games.Source: §7.1 · p. 42

8 ϵ-approximate Bayesian Nash equilibrium

• The reduction encodes vertices on each graph side as player types and uses strategies to encode vertices and local actions; mismatched-vertex play pays zero.The types and strategies thus represent the identities and choices in the bipartite polymatrix game.Source: §8 · pp. 44–45
• A 7-coloring of the squared degree-3 graph lets each player encode a color and one of two local strategies using 14 actions.Vertices at distance exactly two receive different colors.Source: §8 · p. 45
• Finding a constant-ϵ approximate Bayesian Nash equilibrium is PPAD-complete for two-player incomplete-information games with 14 actions per player.The construction reduces the action count to 14 while preserving the hardness result.Source: §8 · p. 45

9 Relative ϵ-Well Supported Nash equilibrium

• Finding a relative ϵ-WSNE in a positive-payoff bimatrix game is PPAD-complete for a constant ϵ.The reduction starts from a degree-3 bipartite polymatrix game.Source: §9 · p. 46
• The imitation game makes each player imitate the other’s node choice, with the column player targeting the next node in the ordering.The row player’s payoff is 1 when both choose the same node; the column player’s payoff is 1 when the row player chooses node i and she chooses node i+1.Source: §9 · pp. 46–47
• In every relative ϵ-WSNE, each player assigns every node probability between (1 − 4η)/n and (1 + 5η)/n.Thus play is approximately uniform across the nodes.Source: Structure and value of a relative ϵ-WSNE · p. 47
• In every (x, y) relative ϵ-WSNE, the expected utilities of both players for playing any strategy are in the interval [(1 − 4η)/n, (1 + 9η)/n].Source: Structure and value of a relative ϵ-WSNE · p. 48

Completing the proof of Corollary 2

• Conditioning each node’s action probabilities on that node yields an ϵ′-approximate polymatrix equilibrium for some small constant ϵ′ = Θ(ϵ).A profitable polymatrix deviation would imply a relative payoff improvement contradicting the assumed relative ϵ-WSNE.Source: Completing the proof of Corollary 2 · p. 48

10 Non-monotone markets

• For any non-monotone utility family U, finding a constant-ϵU-tight approximate equilibrium is PPAD-hard when traders’ utilities are linear or from U.Tightness bounds each good’s excess demand relative to its total endowment.Source: §10 · p. 49

10.1 Why are non-monotone markets hard?

• A small demand increase can trigger larger price and income changes that amplify demand for other goods—the construction’s “butterfly effect.”The paper describes this as the underlying mechanism exploited by Chen et al.’s construction [CPY13].Source: §10.1 · p. 50

10.2 High-level structure of the proof

• The reduction encodes strategy probabilities as prices and uses traders’ endowed goods to transmit payoff-dependent demand between players.Chains of non-monotone-market gadgets amplify a small price gap between strategy goods into a larger gap; a price-regulating gadget controls relative prices.Source: §10.2 · pp. 50–51

10 Non-monotone markets

• The result is weaker than Chen et al.’s [CPY13] because it applies only to tight approximate market equilibrium.The paper’s definition of tightness bounds each good’s excess demand by ϵ times its total endowment.Source: §10 · p. 49, §10.3 · p. 51

10.3 Adaptations for constant factor inapproximability

• The proof requires ϵ-tight equilibrium to obtain two-sided price bounds, then uses repeated neighbor comparisons and random walks to relate prices across the graph.For a constant-degree expander, the walk mixes in O(log n) steps, giving a (1/log n)-inapproximability result.Source: §10.3 · pp. 51–52

Achieving constant hardness

• To obtain constant hardness, the construction uses a graph with constant mixing time and degree O(√n), built from n copies of the original n-player game.Added trivial edges form only a constant fraction of the new graph’s edges.Source: Achieving constant hardness · p. 53

A Non-monotone markets: proof of inapproximability

• The section's main result is an inapproximability theorem for non-monotone markets.Source: A Non-monotone markets: proof of… · p. 56
• For any non-monotone utility family U, some constant ϵU makes finding an ϵU-tight approximate market equilibrium PPAD-hard.The result applies when each trader's utility is either linear or belongs to U.Source: A Non-monotone markets: proof of… · p. 56
• The hardness result covers markets whose traders have linear utilities or utilities drawn from U.Source: A Non-monotone markets: proof of… · p. 56

A.1 Normalized polymatrix games

• An n-player, 2-strategy polymatrix game is represented by a 2n×2n matrix whose (i, j) block is player j's payoff matrix in the game with player i.Source: §A.1 · p. 56
• The induced payoff matrix P′ is normalized using the graphical game's edge set and maximum degree ∆.Source: §A.1 · p. 57
• P and P′ have the same ϵ-WSNE up to normalization by ∆, so finding an (ϵ/∆)-WSNE in P remains PPAD-complete.Source: §A.1 · p. 57
• Finding an ϵ-WSNE is formulated as finding x in [0, 1]^(2n) with x_(2i−1) + x_(2i) = 1.Source: §A.1 · p. 57

A.2 Games on graphs with a constant mixing time

• Duplicating each player across copies and adding trivial within-copy edges yields the graph used to obtain constant mixing without a complete-graph degree blowup.The resulting graph has degree Δ = 4n − 3.Source: §A.2 · pp. 57–58
• An ϵ-WSNE in the constructed game yields a (4ϵ/3)-WSNE in the original game by averaging strategies across copies.The factor accounts for the change in degree.Source: §A.2 · p. 58
• The random walk mixes in constant time because a cross-copy step and a within-copy step each occur with constant probability, yielding a uniform distribution.The proof gives probabilities greater than 3/4 and greater than 1/4, respectively.Source: §A.2 · p. 58

A.3 Construction

• The reduction targets an η-tight approximate market-clearing equilibrium with η = N^-8ϵ, where ϵ is the game inapproximability factor.N is a sufficiently large constant depending on the non-monotone market parameters, not the construction size.Source: §A.3 · p. 58
• For each vertex, 4t + 1 gadgets use pairs of main goods to encode strategy weights, while an auxiliary good separates their prices from effects on other players.The construction also includes non-monotone gadgets for j ∈ [4t].Source: §A.3 · pp. 58–60
• The non-monotone market gadget is scaled so that, when prices are approximately equal, excess demand for one main good increases linearly with its price.Its excess-demand function is defined near equal prices, with bounded deviation from its value at zero.Source: §A.3 · p. 59
• Price-regulating gadgets constrain the ratio of each pair of main-good prices and make the prices of the other goods in each gadget equal.The passage states that the ratio stays within a specified range, without giving that range here.Source: §A.3 · p. 60

Single-minded traders graph

• Single-minded traders propagate price discrepancies between successive gadgets and connect goods according to normalized game-payoff weights to enforce approximate Nash equilibrium.The economy graph is strongly connected, and its goods’ supplies and demands are summarized in Table 1.Source: Single-minded traders graph · pp. 60–61

A.4 Structure of a market equilibrium

• In an η-tight market equilibrium, each base price is approximately the average of its neighbors, and the graph’s mixing property makes prices converge toward a uniform distribution.The neighbor-averaging error is O(η · Nt); the argument iterates it over a random walk.Source: §A.4 · p. 64
• Within each gadget, the non-monotone gadget’s excess demand is balanced by price-regulating traders, producing the stated relation between the two main-good prices.The other goods’ prices in the gadget are equal.Source: §A.4 · pp. 61, 65, 66

A.5 From market equilibrium to Nash equilibrium

• The market-to-game argument constructs an ϵ-WSNE from an η-tight approximate market equilibrium and derives x1 = 1 and x2 = 0 in its concluding step.The text states that this implies x is an ϵ-WSNE.Source: §A.5 · pp. 66–67