Computational Complexity of Approximate Nash Equilibrium in Large Games

Aviad RubinsteinarXiv 2014 · OpenReview

Abstract

We prove that finding an epsilon-Nash equilibrium in a succinctly representable game with many players is PPAD-hard for constant epsilon. Our proof uses succinct games, i.e. games whose payoff function is represented by a circuit. Our techniques build on a recent query complexity lower bound by Babichenko.

Introduction

Nash’s Theorem is a fundamental pillar of game theory, guaranteeing that every finite game possesses at least one equilibrium point. However, from a computational perspective, the mere existence of a solution does not imply its accessibility. For decades, the computer science community has grappled with a critical question: Can we actually find a Nash equilibrium efficiently?

While finding an exact Nash equilibrium is known to be PPAD-complete—suggesting it is likely intractable for general cases—researchers shifted their focus toward approximation. The hope was that finding an $\epsilon$-Nash equilibrium (where players have no incentive to deviate by more than a small margin $\epsilon$) might be computationally feasible. While hardness was established for very small values of $\epsilon$, the "holy grail" of this field remained the status of constant error $\epsilon > 0$. This paper addresses this gap, demonstrating that even with a constant error margin, the search for an equilibrium remains PPAD-hard in the context of large, succinctly represented games.

The Problem: Succinctness and Approximation

In games with a large number of players, representing the game via a traditional payoff matrix is impossible, as the table size grows exponentially with the number of players. Instead, researchers use "succinct games," where the payoff function is represented by a polynomial-sized circuit. This allows for the description of complex interactions among many agents without an exponential explosion in the input size.

The central challenge explored here is the existence of a Polynomial Time Approximation Scheme (PTAS). If such a scheme existed, we could find an $\epsilon$-Nash equilibrium for any constant $\epsilon$ in polynomial time. By proving PPAD-hardness for constant $\epsilon$, this work suggests that such a general-purpose efficient algorithm likely does not exist for succinct games.

Methodology: A Chain of Reductions

The paper establishes its hardness result through a sophisticated chain of mathematical reductions, building upon recent advances in query complexity.

  1. From EndOfTheLine to Brouwer: The proof begins with "EndOfTheLine," the canonical PPAD-complete problem involving finding the sink of a directed path in a large, implicitly defined graph. The author reduces this to the problem of finding an approximate fixed point of a continuous function, as described by Brouwer’s Fixed Point Theorem. This step utilizes a technique by Hirsch, Papadimitriou, and Vavasis to embed discrete paths into a high-dimensional continuous hypercube.
  2. From Brouwer to Nash: The fixed-point problem is then reduced to a Nash equilibrium problem. The construction involves dividing players into two primary groups: one group tasked with imitating the actions of the other, while the second group attempts to move toward the value defined by the Brouwer function.
  3. Succinct Representation: By using circuits to compute payoffs, the author ensures that the resulting game remains "small" (polynomial in the description of the Brouwer function) even though it involves many players and an exponential strategy space.

Key Insights

The Universality Paradox

The paper highlights a conceptual tension in game theory. If a Nash equilibrium always exists but is computationally impossible to find, its predictive power is diminished. If rational agents cannot compute their equilibrium strategies, it is unlikely they will converge to them in real-world scenarios.

The Role of Representation

The hardness result is intrinsically linked to how the game is described. In succinct games, even determining a "best response" can be a hard problem (specifically PP-hard). Interestingly, the author notes that the hard instances constructed in this proof actually contain pure strategy equilibria. Typically, pure equilibria are easier to find than mixed ones, but the succinct circuit representation makes them equally elusive.

Bridging Complexity Domains

A significant contribution of this work is the bridge it builds between query complexity (the number of payoff evaluations required) and computational complexity (the total number of operations required). By leveraging Babichenko’s query complexity lower bounds, the author provides a robust foundation for the computational hardness of the problem.

Results

The primary findings are formalized in two major theorems:

  • Theorem 1: Finding an $\epsilon$-Nash equilibrium in a succinct game with $m$ players is PPAD-hard for a constant $\epsilon$. The proof specifically demonstrates this for a game structure involving $4n+4$ players.
  • Theorem 2: Finding an $\epsilon$-approximate fixed point for an $M$-Lipschitz, poly-time computable function is PPAD-hard for constant $\epsilon$ and $M$.

Limitations and Future Directions

While this work provides a definitive hardness result for succinct games, several questions remain. The proof focuses on "well-supported" Nash equilibria—where players only play strategies that are approximate best responses. Whether the same hardness applies to the standard additive $\epsilon$-approximate Nash equilibrium ($\epsilon$-ANE) remains an open question.

Furthermore, the results apply to games with arbitrary circuit-based payoffs. Future research is needed to determine if this hardness persists in more restricted or "natural" game classes, such as graphical games with bounded degree. Finally, the author points out the lack of a non-trivial upper bound; it is currently unclear if the problem even belongs to PPAD, as calculating approximate best responses without randomness is itself a significant hurdle.

Summary updated

Abstract

We prove that finding an epsilon-Nash equilibrium in a succinctly representable game with many players is PPAD-hard for constant epsilon. Our proof uses succinct games, i.e. games whose payoff function is represented by a circuit. Our techniques build on a recent query complexity lower bound by Babichenko.
BibTeX
@misc{rubinstein2014computational,
  author = {Aviad Rubinstein},
  title = {{Computational Complexity of Approximate Nash Equilibrium in Large Games}},
  year = {2014},
  eprint = {1405.0524},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1405.0524},
}
Figure