Hardness Amplification for Approximate Nash Equilibrium with Constantly Many Players

arXiv:2610.25608 · cs.GT, cs.CC · Submitted 2026-10-19 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.

Tom: I'm Tom.

Jane: And I'm Jane, here with Lu, Meng and our in-house large language model, Lalam.

Tom: We're looking at the paper: "Hardness Amplification for Approximate Nash Equilibrium with Constantly Many Players".

Jane: Here's the gist of the paper. For every fixed ε ∈ (0, 1) and η ∈

0, 1), we prove that computing an (ε, η)-weak approximate Nash equilibrium requires quasipolynomial time assuming deterministic PPAD-ETH, even in symmetric binary-payoff games with a constant number of players The main technical result is an unconditional error-amplification reduction from bimatrix games This hardness consequence follows from Rubinstein’s bimatrix theorem and deterministic PPAD-ETH Hardness Result The paper establishes a deterministic worst-case running-time lower bound of N(log N)−o(1) for computing an approximate equilibrium in symmetric binary-payoff games under deterministic PPAD-ETH This lower bound extends the obstruction established by Rubinstein [Rub16, Theorem 1.2: for bimatrix games at a sufficiently small constant error The hardness persists when only a fixed positive fraction of players must satisfy the approximate Nash condition Amplification Construction The technical contribution is an unconditional amplification theorem that transforms a rational bimatrix game into a symmetric binary-payoff game with polynomial-size complete table This construction uses constantly many players and a polynomial-size complete table The construction time and the table length of H are polynomial in the encoding length of G Equilibrium Recovery Mechanism The paper details an algorithm, Algorithm 1, which uses a filtering procedure to reduce total auxiliary player weight by a fixed factor in each round The recovery condition involves checking if the distribution Q satisfies Q(a: V∗Q − VQ(a) ≤ ∆) ≥ 1 − β If this condition is met, the product of the marginals yields a δ-ANE of G Complexity Analysis and Bounds The analysis shows that the number of players C can be chosen to satisfy C ≤ exp Oδ (1 + log 1/((1 − η)(1 − ε))2) This sufficient bound is compared against a necessary condition for hardness, which states that p > ((1 − ε)−1 / (1 − η)) The quantitative gap suggests that player counts supporting hardness must grow at least linearly in 1/ρ Under deterministic PPAD-ETH, every player count supporting the hardness conclusion must satisfy (4.2) This implies that for fixed starting accuracy δ, the sufficient count grows at least quasipolynomially in 1/ρ The comparison between necessary and sufficient bounds leaves a gap between a necessary linear scale and a sufficient quasipolynomial scale in 1/ρ References

AB17: I.

Tom: Arieli and Y.

Jane: Babichenko.

Tom: Simple approximate equilibria in games with many players

BBP17: Y.

Paper summary: Tom: Let's wrap up with a quick look at what this paper means overall, considering the title and authors. Xiaotie Deng, Ningyuan Li, Zihe Wang, and Jie Zhang are the people who did this work on "Hardness Amplification for Approximate Nash Equilibrium with Constantly Many Players."

Jane: They essentially proved that computing an epsilon weak approximate Nash equilibrium in symmetric binary-payoff games requires quasipolynomial time assuming deterministic PPAD-ETH.

Lu: The authors established this by creating an unconditional error amplification reduction from bimatrix games, which links the hardness of one type of game to another.

Meng: So, for someone trying to build a production system that needs to find these approximate equilibria, this paper tells you that you can't just rely on simple polynomial-time algorithms anymore if you want a good approximation guarantee.

Tom: It sets a very high bar for any algorithm trying to solve these games in practice because the running time lower bound is N log N minus little one, which nearly matches the quasipolynomial running time of some small-support enumeration algorithms.

Jane: The main point is that this difficulty persists even when you only require a fixed positive fraction of players to satisfy the approximate Nash condition, which means those constraints aren't easy to bypass with more players.

Lalam: What this result really changes for people is showing that the player count itself can be chosen based on these tolerances epsilon and eta, and the action counts grow with the input.

Meng: It means we have to be careful about how we scale things up, because scaling up players doesn't automatically make finding these equilibria easier in this setting.

Tom: So, it’s not just a theoretical complexity result; it tells us about the fundamental difficulty of approximation in these types of games under the assumption of deterministic PPAD-ETH.

Conclusion: Tom: So we're wrapping up on this paper about "Hardness Amplification for Approximate Nash Equilibrium with Constantly Many Players." It’s pretty dense, but the core idea is that finding a good approximate equilibrium in these games is actually hard under certain assumptions.

Jane: Right, so we talked about how they use this error amplification thing to show that if you want a strong approximation guarantee, you have to deal with some serious computational cost related to the number of players.

Lu: Exactly. The authors proved that for every fixed error tolerance epsilon and eta, computing an epsilon weak approximate Nash equilibrium needs quasipolynomial time under deterministic PPAD-ETH. That’s the big takeaway there on complexity.

Meng: From a production standpoint, what this means is that if you're building a system for these games, you can't just expect it to run in polynomial time if you want that level of accuracy; the scaling of the player count matters significantly.

Tom: The authors achieved this by doing an unconditional error amplification reduction from bimatrix games. It’s showing that their hard problem isn't isolated; it connects back to known obstructions for two-player games like Rubinstein’s work.

Jane: And the technical magic they used was this transformation into a symmetric binary-payoff game with a polynomial size complete table, which is then recovered using this clever filtering procedure involving marginals and expected scores.

Lu: That recovery mechanism is key. It involves checking if the distribution Q on actions satisfies a specific condition relating its score to the best possible score, and if it does, you get a good approximate equilibrium for the original bimatrix game.

Meng: But they also showed that this construction works even when you only require a fixed fraction of players to satisfy that approximate Nash condition, which is important because real-world games often have many players.

Tom: So what's the implication for us? It suggests that trying to solve these problems efficiently is really about balancing how much accuracy you need against the complexity of dealing with more and more players.

Jane: It’s a strong warning for anyone designing an algorithm for finding approximate equilibria in multi-player settings—the required player count can grow quite fast if you want to keep those error tolerances fixed.

Lalam: I'm pretty sure this result is solid because they handled the technical details of the amplification and recovery very precisely, and it shows a fundamental gap between what’s necessary for hardness and what’s sufficient for finding an answer.

Meng: It's not just a theoretical result; it sets a boundary on what we can expect from current approximation algorithms in this specific complexity class.

Tom: Next up, we're going to look at how this player count scales against the error tolerances epsilon and eta.

Center on Frontiers of Computing Studies, School of Computer Science, Peking University · Department of Computer Science, City University of Hong Kong · Gaoling School of Artificial Intelligence, Renmin University of China · Department of Computer Science, University of Bath

cs.GT, cs.CC

Submitted: 2026-10-19

Updated: 2026-11-05

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Importance score: 97/100

The gist: For every fixed ε ∈ (0, 1) and η ∈ [0, 1), we prove that computing an (ε, η)-weak approximate Nash equilibrium requires quasipolynomial time assuming deterministic PPAD-ETH…

Key concepts

Weak Approximate Nash Equilibrium (WANE)
This is a state where at most an η fraction of players gain more than ε by unilaterally deviating. The goal is to find a strategy profile that satisfies this condition, allowing for some players to be slightly unhappy.
Error Amplification Reduction
This is the core technical tool. It transforms a complex rational bimatrix game into a simpler symmetric binary-payoff game while preserving the quality of the equilibrium found. This allows researchers to use known hardness results from bimatrix games to prove hardness for approximate Nash equilibria.
PPAD-ETH
This is a complexity class assumption related to deterministic polynomial-time algorithms that can query an oracle for problems in PPAD. Assuming this class implies certain limitations on the computational power available for solving these equilibrium problems.

Terminology

Summary

For every fixed ε ∈ (0, 1) and η ∈ [0, 1), we prove that computing an (ε, η)-weak approximate Nash equilibrium requires quasipolynomial time assuming deterministic PPAD-ETH, even in symmetric binary-payoff games with a constant number of players The main technical result is an unconditional error-amplification reduction from bimatrix games This hardness consequence follows from Rubinstein’s bimatrix theorem and deterministic PPAD-ETH

Hardness Result

The paper establishes a deterministic worst-case running-time lower bound of N(log N)−o(1) for computing an approximate equilibrium in symmetric binary-payoff games under deterministic PPAD-ETH This lower bound extends the obstruction established by Rubinstein [Rub16, Theorem 1.2] for bimatrix games at a sufficiently small constant error The hardness persists when only a fixed positive fraction of players must satisfy the approximate Nash condition

Amplification Construction

The technical contribution is an unconditional amplification theorem that transforms a rational bimatrix game into a symmetric binary-payoff game with polynomial-size complete table This construction uses constantly many players and a polynomial-size complete table The construction time and the table length of H are polynomial in the encoding length of G

Equilibrium Recovery Mechanism

The paper details an algorithm, Algorithm 1, which uses a filtering procedure to reduce total auxiliary player weight by a fixed factor in each round The recovery condition involves checking if the distribution Q satisfies Q(a: V∗Q − VQ(a) ≤ ∆) ≥ 1 − β If this condition is met, the product of the marginals yields a δ-ANE of G

Complexity Analysis and Bounds

The analysis shows that the number of players C can be chosen to satisfy C ≤ exp Oδ (1 + log 1/((1 − η)(1 − ε))2) This sufficient bound is compared against a necessary condition for hardness, which states that p > ((1 − ε)−1 / (1 − η)) The quantitative gap suggests that player counts supporting hardness must grow at least linearly in 1/ρ

Conclusion on Hardness

Under deterministic PPAD-ETH, every player count supporting the hardness conclusion must satisfy (4.2) This implies that for fixed starting accuracy δ, the sufficient count grows at least quasipolynomially in 1/ρ The comparison between necessary and sufficient bounds leaves a gap between a necessary linear scale and a sufficient quasipolynomial scale in 1/ρ

References

[AB17] I. Arieli and Y. p. 5 Babichenko. p. 5 Simple approximate equilibria in games with many players

[BBP17] Y. Babichenko, S. p. 5 Barman, and R. Peretz. Empirical distribution of equilibrium play and its testing application

[BPR16] Y. Babichenko, C. p. 5 H. Papadimitriou, and A. p. 5 Rubinstein. p. 0 p. 0 p. 0 Can almost everybody be almost happy? In Proceedings of the 7th Innovations in Theoretical Computer Science Conference (ITCS 2016)

[BGR08] P. Briest, P. W. Goldberg, and H. p. 5 Röglin. Approximate equilibria in games with few players

[CCT17] X. Chen, Y. Cheng, and B. p. 5 Tang. Well-supported vs approximate Nash equilibria: Query complexity of large games

[CDT09] X. Chen, X. Deng, and S. p. 4-H. Teng. Settling the complexity of computing two-player Nash equilibria

[CTV07] X. Chen, S.-H. Teng, and P. Valiant. The approximation complexity of win-lose games

[DGP09] C. Daskalakis, P. W. Goldberg, and C. p. 5 H. Papadimitriou. p. 5 The complexity of computing a Nash equilibrium

[DFM22] A. Deligkas, M. p. 4 Fasoulakis, and E. p. 4 Markakis. A polynomial-time algorithm for 1/3-approximate Nash equilibria in bimatrix games

[DFHM23] A. Deligkas, J. p. 4 p. 4 p. 4 Fearnley, A. p. 5 p. 5 Hollender, and T. p. 5 p. 5 Melissourgos. p. 5 p. 5 Tight inapproximability for graphical games

[DFHM24] A. Deligkas, J. Fearnley, A. Hollender, and T. Melissourgos. Pure-Circuit: Tight inapproximability for PPAD

[DFSS17] A. Deligkas, J. Fearnley, R. p. 5 Savani, and P. p. 5 Spirakis. Computing approximate Nash equilibria in polymatrix games

[FNS07] T. Feder, H. Nazerzadeh, and A. p. 5 Saberi. Approximating Nash equilibria using small-support strategies

[Gol26] N. Golowich. The fine-grained complexity of approximate Nash equilibrium and free games

[HRS08] S. Hémon, M. de Rougemont, and M. p. 4 Santha. Approximate Nash equilibria for multi-player games

[LL26] D. Li and H. Li. A simple algorithm breaking the 1/3 barrier for approximate Nash equilibria in bimatrix games

[LLD26] H. Li, D. Li, and X. Deng. Discovering expert-level Nash equilibrium algorithms with large language models

[LMM03] R. J. Lipton, E. Markakis, and A. p. 1 Mehta. Playing large games using simple strategies

[OAI26] OpenAI. The PCP-for-PPAD conjecture: a quasilinear reduction

[Rub16] A. Rubinstein. Settling the complexity of computing approximate two-player Nash equilibria

[Rub18] A. Rubinstein. Inapproximability of Nash equilibrium

--- Page 1 ---

Hardness Amplification for Approximate Nash Equilibrium with Constantly Many Players Xiaotie Deng, Ningyuan Li, Zihe Wang, and Jie Zhang

Abstract For every fixed ε ∈ (0, 1) and η ∈ [0, 1), we prove that computing an (ε, η)-weak approximate Nash equilibrium requires quasipolynomial time assuming deterministic PPAD-ETH The games are given by complete payoff tables, and the player count depends only on the tolerances The weak approximate Nash equilibrium allows at most an η fraction of players to gain more than ε by deviating unilaterally

--- Page 2 ---

For every fixed error below one, there is a constant player count for which computing an approximate equilibrium requires deterministic worst-case time N(log N)−o(1) This holds even for symmetric games with payoffs in [0, 1] The lower bound extends the obstruction established by Rubinstein [Rub16, Theorem 1. p. 12] for bimatrix games at a sufficiently small constant error It nearly matches the quasipolynomial running time of the small-support enumeration algorithm of Lipton, Markakis, and Mehta [LMM03]

--- Page 3 ---

The hardness persists when only a fixed positive fraction of players must satisfy the approximate Nash condition An (ε, η)-weak approximate Nash equilibrium allows at most an η fraction of players to gain more than ε by a unilateral deviation [BPR16, Definition 4] Our result holds for every fixed ε ∈ (0, 1) and η ∈ [0, 1) The player count is chosen after these tolerances are fixed, and the action counts grow with the input Thus the permitted payoff gain can be arbitrarily close to one, and the required fraction 1 − η can be arbitrarily small, provided both tolerances remain fixed

--- Page 4 ---

The technical contribution is an unconditional amplification theorem Given a rational bimatrix game with payoffs in [0, 1] and a fixed target accuracy δ ∈ (0, 1), we construct a symmetric binarypayoff game H with a common action set and payoffs in [0, 1] Every rational (ε, η)-weak ANE of H yields a rational δ-ANE of G Construction time and the table length of H are polynomial in the encoding length of G Recovery is polynomial in that length and the actual encoding length of the given profile

--- Page 5 ---

The main technical result is an unconditional error-amplification reduction from bimatrix games For every fixed δ ∈ (0, 1), it transforms a rational bimatrix game with payoffs in [0, 1] into a symmetric binary-payoff game with a polynomial-size complete table and a player count depending only on δ, ε, η Every (ε, η)-weak approximate equilibrium of the constructed game yields a δ-approximate Nash equilibrium of the bimatrix game Construction and recovery take polynomial time in their explicit inputs Combining this reduction with the bimatrix hardness result of Rubinstein [Rub16] gives a deterministic worst-case running-time lower bound of N(log N)−o(1)

--- Page 6 ---

Each player in the constructed game chooses a sequence of action pairs from the bimatrix game A filtering procedure uses scores derived from the input-game payoffs to reduce total auxiliary player weight by a fixed factor in each round A player receives payoff one exactly when its weight never decreases, so average payoff is small at every profile An analogous filter applied to a mixed profile produces distributions on action pairs whose marginals give recovery candidates If every candidate fails the recovery condition, each player has a pure deviation yielding payoff one with high probability, contradicting the average-payoff bound at a weak approximate equilibrium Sampling estimates independent of the number of action pairs keep the player count constant

--- Page 7 ---

We study additive approximate Nash equilibrium in finite normal-form games given by complete payoff tables With payoffs in [0, 1], an ε-approximate equilibrium allows each player to gain at most ε by deviating unilaterally, so error one imposes no restriction For each fixed player count p ≥ 2, polynomial-time algorithms achieve error 1 − 1/p [BGR08, HRS08] Can a single constant error below one be achieved in polynomial time for every fixed number of players?

--- Page 8 ---

Under deterministic PPAD-ETH, we answer this question negatively. For every fixed error below one, there is a constant player count for which computing an approximate equilibrium requires deterministic worst-case time N(log N)−o(1) This holds even for symmetric games with payoffs in [0, 1] The lower bound extends the obstruction established by Rubinstein [Rub16, Theorem 1.2] for bimatrix games at a sufficiently small constant error It nearly matches the quasipolynomial running time of the small-support enumeration algorithm of Lipton, Markakis, and Mehta [LMM03]

--- Page 9 ---

The hardness persists when only a fixed positive fraction of players must satisfy the approximate Nash condition An (ε, η)-weak approximate Nash equilibrium allows at most an η fraction of players to gain more than ε by a unilateral deviation [BPR16, Definition 4] Our result holds for every fixed ε ∈ (0, 1) and η ∈ [0, 1) The player count is chosen after these tolerances are fixed, and the action counts grow with the input Thus the permitted payoff gain can be arbitrarily close to one, and the required fraction 1 − η can be arbitrarily small, provided both tolerances remain fixed

--- Page 10 ---

The technical contribution is an unconditional amplification theorem Given a rational bimatrix game with payoffs in [0, 1] and a fixed target accuracy δ ∈ (0, 1), we construct a symmetric binary-payoff game H with a common action set and payoffs in [0, 1] Every rational (ε, η)-weak ANE of H yields a rational δ-ANE of G Construction time and the table length of H are polynomial in the encoding length of G Recovery is polynomial in that length and the actual encoding length of the given profile

--- Page 11 ---

For an integer p ≥ 1, let player i ∈ (1,..., p) have a finite nonempty action set Ai and a payoff function u i: Qp j=1 Aj → [0, 1] A mixed profile σ = Np i=1 σi specifies independent draws from the players’ distributions σi on Ai Write u i(σ) for player i’s expected payoff and u i(ai, σ−i) for its expected payoff when it chooses the pure action ai ∈ Ai and the other players keep their strategies

--- Page 12 ---

For ε ≥ 0, an additive ε-approximate Nash equilibrium (ε-ANE) satisfies max a i∈Ai u i(ai, σ−i) ≤ u i(σ) + ε (i = 1,..., p). (1.1) For η ∈ [1], an (ε, η)-weak approximate Nash equilibrium requires this inequality for all but at most ⌊ηp⌋ players [BPR16, Definition 4]

--- Page 13 ---

The complete-table representation lists the action sets and each player’s rational payoff at every pure action profile An equilibrium algorithm outputs a rational mixed profile by listing each player’s probability for every action

--- Page 14 ---

Theorem 1.1 (Error amplification). p. 0 Fix 0 < δ < 1, 0 < ε < 1, and 0 ≤ η < 1. p. 1 There is an integer C = C(δ, ε, η) and a deterministic transformation from every rational bimatrix game G with payoffs in [0, 1] to a symmetric C-player game H with a common action set and payoffs in [0, 1] Every rational (ε, η)-weak ANE of H yields a rational δ-ANE of G Construction time and the table length of H are polynomial in the encoding length of G Recovery is polynomial in that length and the actual encoding length of the given profile

--- Page 15 ---

For a distribution Q on A, define a scoring function k(a, b) = u i(a i, b j) + u j(b i, a j) For a probability distribution Q on A, define the expected score and its maximum by VQ(a) = 1/2 u1(a1, Q(2)) + u2(Q(1), a2)

--- Page 16 ---

Taking the expectation in (2.1) gives VQ(a) = 1/2 u i(a i, Q(j)) + u j(Q(1), a j) For fixed Q, each summand depends on only one coordinate of a This separation gives the following recovery condition

--- Page 17 ---

Lemma 2.1 (Marginal recovery). p. 6 Let 0 < β, ∆ < 1. p. 1 If a probability distribution Q on A satisfies Q(a: V∗Q − VQ(a) ≤ ∆) ≥ 1 − β, (2. p. 64) then Q(1) × Q(2) is a (β + 2∆)-ANE of G

--- Page 18 ---

Both shortfalls lie in [0, 1]. Because A = A1 × A 2, the two summands in (2. p. 73) can be maximized independently Hence d1 (a1) + d 2 (a2) = 2(V∗Q − VQ(a))

--- Page 19 ---

The gap 2(V∗Q − VQ(a)) is the sum of the two actions’ payoff shortfalls from best responses to the opposite marginals Our recovery test requires Q to give sufficiently high probability to reports whose scores are sufficiently close to V∗Q, with both tolerances fixed in terms of δ

--- Page 20 ---

If any Qs passes the test, a δ-ANE of G is found by returning the product of its marginals Suppose instead that every test fails. In each round, a probability bounded below by a fixed positive constant lies on reports separated from the maximum by a fixed positive score gap Call these reports low-scoring Choose a maximizer a∗s ∈ arg maxa VQs(a) in every round, then any player can deviate to the complete sequence z∗ = (a∗1,. p. 3.., a∗t) as a legal pure action This deviation sequence depends only on the original mixed profile and is fixed before opponents are sampled

--- Page 21 ---

Why the deviator’s weight can remain one The fraction 1−q removed per round is chosen below the probability guaranteed by a failed test, and the transition width h below the guaranteed score gap Both choices leave fixed margins for sampling errors Suppose that, after opponents are sampled, players whose empirical scores are more than h below the deviator’s account for more than a 1 − q fraction of total prior weight. A multiplier below one for the deviator would put the threshold above all those lower scores, making their multipliers zero The deviator’s multiplier must therefore be one If this holds in every round, its weight never decreases and it receives payoff one

--- Page 12 ---

The construction and recovery use exact rational arithmetic We verify polynomial bit cost, including the exact test for a payoff of one Enumerating all profiles produces exactly CAtC binary entries and hence a table of polynomial size Implementing Algorithm 1 Given a rational profile, Algorithm 1 forms P and computes the reference weights and scores In round s, solve Bs(θ) = q s where Bs(θ) = X z∈At P(z)Ws−1(z)ϕ(Vs(zs), θ)

Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.

Improvements for AI systems

  1. Quasipolynomial time computation for approximate Nash equilibria in symmetric binary-payoff games can be achieved under deterministic PPAD-ETH for a constant number of players, as proven by Theorem 1.2 (Hardness below one).

  2. The amplification construction allows transforming any rational bimatrix game with payoffs in [0, 1] into a symmetric binary-payoff game where every weak approximate Nash equilibrium yields a delta approximate Nash equilibrium of the original game (Theorem 1.1).

  3. The filtering procedure, which uses scores derived from the input-game payoffs to reduce total auxiliary player weight by a fixed factor in each round, enables the recovery of candidate strategies for mixed profiles while maintaining constant player count (Section 2).

  4. The system can deterministically recover a delta approximate Nash equilibrium of a bimatrix game G by computing a distribution Q such that Q(1) tensor Q(2) is a delta-ANE of G, using the recovery condition defined in Lemma 2.1 (Marginal recovery).

  5. The AI system can perform exact rational arithmetic with polynomial bit cost to implement the filtering game and payoff evaluation, ensuring that the construction and recovery take time polynomial in input encoding lengths (Section 3.3).

  6. The system can guarantee that at least one candidate strategy satisfies the recovery condition (2.4) for every weak approximate Nash equilibrium of a constructed game H, thereby ensuring successful equilibrium recovery (Theorem 2.2).

  7. The system can detect if an approximate Nash equilibrium is violated by showing that if all recovery tests fail, each player has a pure deviation yielding payoff one with high probability, contradicting the average-payoff bound (Section 3).

  8. The AI system can estimate the score at a fixed maximizing report and the average score error over sampled reports to bound total prior player weight on low-scoring reports using Lemma 3.12, which is crucial for forcing a deviator's multiplier to equal one.

Sources

Related papers