PaperlayerView exact revision on arXiv

Source-linked AI summary

Settling the complexity of computing approximate two-player Nash equilibria

Aviad Rubinstein

arXiv:1606.04550v2cs.CCcs.GT

TL;DR

The paper asks how efficiently constant-approximate Nash equilibria can be computed in two-player games and develops PCP-inspired reductions within PPAD. It proves quasi-polynomial-time hardness under ETH for PPAD, while also establishing exponential query lower bounds and PPAD-hardness for the multiplayer (ε,δ)-WeakNash relaxation.

  • Problem

    Whether two-player Nash equilibrium admits a PTAS remains open, while the query complexity of approximate equilibria and weaker multiplayer relaxations also has unresolved hardness questions.

  • Method

    The paper chains reductions through LocalEndOfALine, approximate Brouwer fixed points, multiplayer games, and two-player games using error-correcting codes and PCP-style techniques inside PPAD.

  • Results

    Assuming ETH for PPAD, some constant-ε approximate Nash equilibrium in a two-player n × n game requires n^{log^{1-o(1)} n} time; multiplayer (ε,δ)-WeakNash requires 2^{Ω(n)} payoff-tensor queries.

  • Takeaways & Limitations

    The results match the known quasi-polynomial upper-bound scale for two-player approximation and extend strong hardness to the more lenient multiplayer WeakNash relaxation.

  • Takeaways & Limitations

    The paper notes that its analogy between PCPs and PPAD is loose, and no formal extension of PCP to function problems is known.

Abstract

from arXiv · show

We prove that there exists a constant $ε>0$ such that, assuming the Exponential Time Hypothesis for PPAD, computing an $ε$-approximate Nash equilibrium in a two-player (nXn) game requires quasi-polynomial time, $n^{\log^{1-o(1)} n}$. This matches (up to the o(1) term) the algorithm of Lipton, Markakis, and Mehta [LMM03]. Our proof relies on a variety of techniques from the study of probabilistically checkable proofs (PCP); this is the first time that such ideas are used for a reduction between problems inside PPAD. En route, we also prove new hardness results for computing Nash equilibria in games with many players. In particular, we show that computing an $ε$-approximate Nash equilibrium in a game with n players requires $2^{Ω(n)}$ oracle queries to the payoff tensors. This resolves an open problem posed by Hart and Nisan [HN13], Babichenko [Bab14], and Chen et al. [CCT15]. In fact, our results for n-player games are stronger: they hold with respect to the $(ε,δ)$-WeakNash relaxation recently introduced by Babichenko et al. [BPR16].

1 Introduction

The paper establishes quasi-polynomial hardness for constant-approximate Nash equilibrium in two-player games under ETH for PPAD, matching the known quasi-polynomial algorithm up to the o(1) term. Its reductions introduce PCP-style tools inside PPAD and yield stronger hardness results for multiplayer games and the (ε,δ)-WeakNash relaxation.

  • Motivation: The central question is whether two-player Nash equilibrium admits a PTAS, despite improved approximation ratios and schemes for special cases.The paper argues that quasi-polynomial hardness is the strongest result currently expected within PPAD.
  • Reduction strategy: The final reduction proceeds through LocalEndOfALine, approximate Brouwer fixed points, multiplayer games, and finally two-player games.Its main novelty is using error-correcting codes and PCP techniques inside PPAD reductions.
  • Reduction strategy: The construction addresses PPAD totality by assigning a default displacement to points too far from valid codewords, rather than rejecting them.This lets PCP-like local verification coexist with the requirement that every PPAD instance has a solution.
  • Holographic proof system: The holographic proof system supports local proof construction, tolerant verification, local decoding, and robustness against adaptive changes to queried bits.These properties support the locality required by the reduction.
  • Multiplayer results: For multiplayer games, (ε,δ)-WeakNash is PPAD-hard with two actions per player, and finding it requires 2^{Ω(n)} payoff-tensor queries.The WeakNash result applies to succinct multiplayer games and is stronger than hardness only for standard approximate Nash equilibrium.
  • Significance: The paper presents error-correcting codes and related PCP tools as previously unused building blocks for hardness reductions within PPAD.The authors explicitly hope these techniques will find further applications in this regime.

2 Preliminaries

This section defines the equilibrium, game, and Brouwer-fixing-point concepts used later, then states the constant-error PPAD-hardness result for 2-norm approximate Brouwer fixed points.

  • Equilibrium concepts: A mixed strategy is a distribution over a player’s actions, and a Nash equilibrium makes every player’s strategy a best response to the others.
  • Equilibrium concepts: An ϵ-Approximate Nash Equilibrium requires each mixed strategy to be an ϵ-best response, while an ϵ-Well-Supported Nash Equilibrium requires every supported action to be one.
  • Equilibrium concepts: An (ϵ, δ)-WeakNash relaxes the condition to a (1 −δ)-fraction of players, and its well-supported variant applies the support condition to that fraction.
  • Game representations: In a polymatrix game, each player participates in separate two-player subgames, uses the same strategy across them, and receives the sum of subgame utilities.
  • Brouwer hardness: Theorem 3.2 states that, for a constant ϵ, ϵ-SuccinctBrouwer2 is PPAD-hard and has a linear-time reduction from EndOfALine.
  • Brouwer hardness: The embedding represents EndOfALine vertices with error-correcting encodings and embeds graph edges as separated Brouwer line segments whose path endpoints correspond one-to-one with EndOfALine solutions.

4 Multiplayer games

The section establishes PPAD-hardness and exponential query lower bounds for approximate WeakNash in succinct multiplayer games, including games with only two actions per player.

  • Overview: The section proves PPAD-hardness for (ϵ, δ)-WeakNash in succinct multiplayer games and develops query-complexity analogues of these results.
  • Constant-action games: Corollary 4.1 proves PPAD-hardness for (ϵ, δ)-WeakNash in succinct multiplayer games with a constant number of actions per player.
  • Constant-action games: The imitation construction uses two player groups: one imitates the other, while the second imitates the Brouwer function applied to the first group’s actions.
  • Two-action games: Corollary 4.2 extends the hardness result to succinct multiplayer games in which every player has two actions.
  • Two-action games: The construction realizes continuous values through groups of binary-action players, defining each group’s realized value as the largest indexed player choosing action +.
  • Query complexity: Any randomized algorithm for multiplayer (ϵ, δ)-WeakNash with two actions per player requires 2^Ω(n) queries to the payoff tensors.

5 EndOfALine with local computation

LocalEndOfALine restricts EndOfALine to legal computation states whose successor and predecessor operations change only constantly many bits and depend locally on the input. A linear-time reduction preserves solutions while making membership verification AC0.

  • Definition: LocalEndOfALine uses a membership circuit for legal vertices and NC0 successor and predecessor circuits that alter only constantly many coordinates.Its solutions include end-of-line violations and boundary-condition violations.
  • Correctness: Theorem 5.2 gives a linear-time reduction from EndOfALine to LocalEndOfALine, and every solution to the new instance yields a valid original solution.The construction has no fixed points because every step activates or deactivates a line.
  • Construction: The construction simulates circuit computations using four circuits S1, P1, S2, and P2, with lines activated, copied, updated, erased, and reconstructed in sequence.Legal vertices encode partial computations through these phases.
  • Local verification: Each line participates in at most three local constraints, and each constraint depends on only constantly many bits, placing the membership circuit MV local in AC0.The membership circuit verifies the conjunction of these local conditions.
  • Local transitions: Each transition changes at most two bits, while the next changed line and its new value can be determined from constantly many bits.This gives the successor and predecessor operations their local-computation property.

6 Holographic Proof

The holographic proof system encodes a LocalEndOfALine vertex and its computation counter using error-correcting codes and a proof over a finite-field domain. A quasi-polynomial-time verifier provides local access, soundness, completeness, decoding, and proof construction guarantees.

  • Proof representation: For each legal vertex u, Proposition 6.1 constructs in polynomial time a holographic proof Π(u) containing an encoded vertex, counter, and auxiliary proof.The encoded vertex uses a linear error-correcting code, and the counter uses a good error-correcting code.
  • Proof representation: The total length of Π(u) is n^1+o(1), and its encoded components can be represented as functions over the domain G^t.The counter is shorter and is read entirely by the verifier.
  • Verifier access: The verifier uses quasi-polynomial time, reads no^(1) axis-parallel subspaces, and uses (1/2 + o(1)) log2 n random bits to choose queries.The queried regions are decomposed into PCP, LTC, and critical subsets.
  • Verifier guarantees: The system combines soundness and completeness with robust versions that remain valid against adaptive corruption of specified proof regions.The stated guarantees include rejection for sound-far strings and acceptance for sufficiently close valid proofs.
  • Decoding: The verifier can decode sampled encoded entries, estimate proof distance within ±o(1), adaptively correct critical bits, and construct sampled proof values from the encoded vertex and counter.These decoding and construction guarantees also hold under bounded adaptive corruption.

7 Polymatrix WeakNash

The paper translates the holographic LocalEndOfALine construction into a subexponential polymatrix game whose approximate WeakNash equilibria encode solutions to the original problem. Theorem 7.1 gives the resulting reduction and game parameters.

  • Main result: The main technical result is a 2n^1/2+o(1)-time reduction from EndOfALine to an (εNash, εNash)-Well-Supported-WeakNash.The target is a complete bipartite polymatrix game with n^1/2+o(1) players and 2n^1/2+o(1) actions per player.
  • Construction: The constructed polymatrix game implements a variant of the hard Brouwer function using LocalEndOfALine vertices and holographic proofs Π(u).The construction also changes the auxiliary coordinate representation by assigning constant relative weights.
  • Construction: The first Brouwer line segment starts at z2 = (Π(u0), Π(u0), 0, 2) and ends at (Π(u0), Π(u0), 0, 0).
  • Proof organization: The proof organizes the reduction by defining strategy spaces, specifying payoffs, implementing an imitation gadget, translating PCP guarantees, and finally reducing to two-player games.

7.1 Players and strategies

The polymatrix game assigns players to verifier randomness and finite-field subspaces, with actions encoding proof samples, counters, critical bits, and auxiliary Brouwer coordinates. Strategy components are designed to intersect verifier-query subspaces at controlled points.

  • Players: For each PCP random string r there is an Alice player, while each q in G^t/2 indexes a Bob player on the opposite side.The two sides later control the corresponding vertices of the polymatrix game.
  • Strategies: Each player has (3/εPrecision + 1)n^1/2+o(1)+2 actions, including discretized vector pairs and two additional scalar variables.The vector coordinates use the discretized interval [-1, 2].
  • Strategies: Alice’s vector pair represents bits read from two holographic proofs, while Bob’s vectors represent counters and proof entries on a selected subspace.The two vectors correspond to consecutive or identical LocalEndOfALine vertices.
  • Critical bits: Alice’s additional actions encode affine subspaces used to decode the qcritical critical bits, identified through the counter portion of the proof.
  • Subspaces: Bob’s subspace G(B,q) is chosen linearly independently of the verifier’s query directions, so it intersects each Alice query subspace at exactly one point.The construction relies on random vectors completing the relevant basis with high probability.

7.2 Notation

This section introduces notation for partial and aggregate strategy vectors, coordinate partitions, weighted norms, and the players’ happiness condition.

  • A player is happy when every strategy in her support is εNash-optimal.
  • The coordinates M are partitioned into two proof blocks, a Compute-vs-Copy bit, and a special direction.The section also defines M1,2 and M3,4 as unions of these blocks.
  • Players’ actions induce partial vectors whose defined coordinates record assigned values and whose remaining coordinates are ⊥.Alice and Bob use separate coordinate sets determined by their player roles and sampled verifier data.
  • The notation supports distances and norms over selected coordinate subsets under an implicit distribution that weights major parts comparably.All norms are 2-norms, with subscripts indicating the coordinates included.
  • Aggregate vectors x(A) and x(B) are weighted coordinate-wise averages over the corresponding players’ partial vectors.For each coordinate, averaging uses only vectors that assign a real value there.

7.3 Alice’s imitation gadget

Alice’s imitation gadget incentivizes each Alice player to copy Bob’s assignments while encoding PCP-critical information determined by counters and verifier directions.

  • Alice’s utility is designed to incentivize imitation of Bob’s aggregate partial vector on her assigned coordinates.The construction decomposes utility across bimatrix subgames.
  • The subgames use bounded negative payoffs, with equivalent nonnegative payoffs obtainable by scaling and shifting.The displayed ranges are [−54/nB, 0] and [−36/nA, 0].
  • Critical-bit locations depend on Bob’s encoded counter, while their decoding directions depend on Alice’s PCP random string.This indirection prevents Alice from manipulating her counter encoding to increase critical-bit utility.
  • Ambiguous or non-codeword counter assignments are treated as cases likely far from every Brouwer line segment.The gadget therefore does not need to enforce a specific critical-bit assignment in those cases.
  • For every happy Alice player, every supported action satisfies the construction’s coordinate-wise imitation guarantee.The guarantee is stated in Claim 7.3 and is developed through Alice’s utility decomposition.

7.4 Bob’s imitation gadget

Bob’s imitation gadget defines a partial target from Alice’s actions and incentivizes Bob to match it; the resulting aggregate behavior approximates a fixed point.

  • Each Bob action induces a partial target vector f(a) that Bob is incentivized to imitate where both target and action vectors are defined.
  • The aggregate target f(A) is formed by weighted coordinate-wise averaging over Alice’s supported actions and relevant random strings.
  • For every happy Bob player, each supported action satisfies the gadget’s imitation guarantee.Claim 7.7 establishes the guarantee by an argument analogous to Claim 7.3.
  • The section’s goal is to show that f(A) is close to Bob’s aggregate vector, which would make x(B) an approximate fixed point of f.

7.5 Reading the holographic proofs

The game verifier uses approximate-equilibrium behavior to test, decode, and extrapolate holographic PCP proofs, with robust guarantees for soundness, completeness, and critical-bit recovery.

  • 7.5 Reading the holographic proofs: The verifier distinguishes assignments near Brouwer vertices, near Brouwer line segments, and far from both by examining the two proof restrictions.
  • 7.5 Reading the holographic proofs: The game verifier rounds assignments to binary vectors and feeds the resulting bits to the PCP verifier, accepting only when the prescribed conditions hold.If either condition fails, it rejects the assignment.
  • 7.5.1 Soundness: Robust soundness implies rejection for almost all happy Alice players when x(B) is sufficiently far from every valid proof encoding.Under the stated distance condition, rejection holds for every supported Alice strategy for a 1 − O(εNash) fraction of random strings.
  • 7.5.2 Completeness: Robust completeness implies acceptance for almost all relevant random strings when x(B) is sufficiently close to a valid proof encoding.The conclusion applies to every strategy in the support of the corresponding Alice player.
  • 7.5.3 Decoding: When x(B) is close enough to a valid proof, the verifier correctly decodes proof restrictions, critical bits, and extrapolated local encodings.These guarantees follow from error correction, critical-bit decoding, and local proof construction.
  • 7.5.3 Decoding: Correctly decoding the critical bits lets the verifier reconstruct the complete difference vector between a local vertex encoding and its successor encoding.

7.6 Default displacement

When local proof restrictions are far from valid proofs or do not match a valid Brouwer configuration, the construction applies the default displacement. Several boundary cases are handled with minor modifications.

  • Far from both valid proof sets, x(B) is far from every Brouwer line segment, so f(A) applies the default displacement.
  • The verifier rejects both proofs for most r’s, causing f(a) to implement the default displacement for every supported strategy a.
  • The same treatment extends, with minor modifications, to configurations outside the picture or with invalid proof matches.
  • If the decoded vertices are not consecutive in the LocalEndOfALine graph, the configuration is likewise handled as a nonmatching case.

7.7 Close to a line (1)

Near a Brouwer line segment, the verifier locally reconstructs endpoint proofs and estimates the closest point using sampled coordinates. Good-sample guarantees and Lipschitz continuity then yield an approximately correct displacement.

  • The verifier locally decodes Π(u) and Π(v) for consecutive LocalEndOfALine vertices and reconstructs their restrictions on sampled coordinates.
  • The partial vectors s(a), t(a), and x(a) determine z(a), the point closest to x(a) on the reconstructed line segment.
  • For most sampled players, the locally computed displacement correctly implements the default displacement when the verifier’s tests reject the relevant proofs.
  • Good-sample guarantees make the restricted dot product a good approximation, while constant relative distance gives ∥s − t∥_M = Θ(1).
  • Lipschitz continuity transfers approximate local computations into an approximately correct displacement for ϵNash-optimal strategies.

7.8 Close to a line (2)

The verifier distinguishes configurations near Brouwer line segments from those far from every segment or near special segments and vertices. For line cases, it locally decodes the relevant consecutive proofs and reconstructs the displacement.

  • Configurations far from every Brouwer line segment receive the default displacement, including cases with nonneighboring vertices or mismatched M3,4 values.
  • Near the first Brouwer line segment, the verifier recognizes the case by estimating the first 2m + 1 coordinates and uses the known endpoint distance ∥t − s∥_M = 1.
  • Other special cases include segments where only the Compute-vs-Copy bit M3 or special direction M4 changes.
  • Near a segment between consecutive LocalEndOfALine vertices, the verifier locally decodes both proofs and constructs partial endpoint vectors matching the true restrictions for most sampled players.

7.9 Close to a vertex

Near a Brouwer vertex, the verifier locally reconstructs the vertex and its incoming and outgoing line segments, then combines line- and vertex-displacement computations. Approximation remains controlled even near their interface, while a numerical instability is handled by reverting to the default displacement.

  • For a vertex y = (Π(u), Π(v), 1, 0), local decoding reconstructs y and the adjacent segments when v is the LocalEndOfALine successor of u.
  • The verifier can also reconstruct endpoint data for vertices of the form (Π(v), Π(v), 1, 0), using error correction and extrapolation guarantees.
  • It estimates the vertex displacement from locally computed partial vectors and the distances along the incoming and outgoing segments.
  • Because f is O(1)-Lipschitz, switching between line and vertex displacement near their interface preserves approximate correctness.
  • When the huge dimension makes Δ(y→t) + Δ(s→y) too small, α(a) can be inaccurate, so the construction uses the default displacement instead.
  • Under the stated sampling and dimension conditions, the default displacement is correctly implemented for most sampled players.

8 From polymatrix to bimatrix

The section completes the reduction from multiplayer polymatrix games to bimatrix games by combining a main game with Althofer gadgets that enforce near-uniform vertex selection.

  • WeakNash conversion: An (ϵ, δ)-WeakNash can be converted into a well-supported relaxation by retaining strategies sufficiently close to optimality and controlling the resulting payoff changes.The construction removes low-quality actions, bounds the removed probability mass, and transfers the change through neighboring players’ strategies.
  • Reduction: The reduction constructs a bimatrix game from a complete bipartite polymatrix game with approximately 2^n^(1/2+o(1)) actions.The source polymatrix game has n^(1/2+o(1)) vertices and 2^n^(1/2+o(1)) actions per vertex.
  • Construction: The bimatrix construction combines a main game with primal and dual Althofer games played simultaneously.The main game encodes vertex and local-action choices, while the auxiliary games impose structural constraints on the players’ mixtures.
  • Construction: Althofer gadgets force both players to distribute probability approximately evenly across almost all vertices in any approximate Nash equilibrium.This near-uniformity supports interpreting each player’s conditional actions as a polymatrix strategy profile.
  • Analysis: The induced conditional strategies on vertices are shown to form a (δ, ϵ_polymatrix)-WeakNash of the original polymatrix game.The analysis defines each vertex’s strategy by conditioning on that vertex being selected and aims to establish the WeakNash guarantee.
Loading 1606.04550v2…