The query complexity of correlated equilibria

Sergiu Hart, Noam NisanGames Econ. Behav 2018 · DOI

Abstract

In game theory, the Correlated Equilibrium (CE) is a central solution concept that generalizes the Nash Equilibrium. While it has long been known that an approximate CE can be found in polynomial time using randomized regret-based dynamics, the fundamental limits of this efficiency remained unclear. This paper investigates whether the "crutches" of randomization and approximation are strictly necessary. Using a query complexity framework and reductions to combinatorial problems on high-dimensional Boolean hypercubes, the authors prove that finding an exact CE or finding an approximate CE deterministically requires an exponential number of queries. These results demonstrate that the tractability of correlated equilibria is a "perfect storm" requiring both randomization and approximation simultaneously.

Introduction: The "Perfect Storm" of Game Theory

Computer scientists have often viewed Correlated Equilibria as a computational success story. Unlike the Nash Equilibrium, which is notoriously hard to compute (PPAD-complete), an approximate CE can be reached efficiently. Simple randomized dynamics, where players minimize their regret over time, allow a system to converge to an approximate CE in time polynomial in the number of players ($n$).

However, this efficiency relies on two specific conditions: the algorithm must be allowed to use randomness, and the result only needs to be an approximation. Sergiu Hart and Noam Nisan set out to determine if these conditions are truly essential. Their findings reveal a sharp complexity cliff: removing either condition causes the problem to explode from polynomial to exponential difficulty.

Methodology: Query Complexity and the Boolean Hypercube

The authors employ a Query Complexity model to establish their lower bounds. Rather than measuring CPU cycles, they count the number of times an algorithm must query a "black box" containing the game's payoff matrix. To prove that no general-purpose algorithm can be efficient, they translate game-theoretic equilibrium conditions into geometric problems on an $n$-dimensional Boolean hypercube, where each vertex represents a strategy profile.

1. The Approximate Sink (AS) Problem

To address deterministic algorithms, the authors show that finding an equilibrium is analogous to finding a "sink" (a vertex with high in-degree) in a directed hypercube. By applying the edge-isoperimetric inequality, they demonstrate that an adversary can always construct a game that "tricks" any deterministic algorithm, forcing it to wander the hypercube for an exponential amount of time before locating an approximate equilibrium.

2. The Non-Positive Vertex (NPV) Problem

To address randomized algorithms for exact equilibria, the authors use a "needle in a haystack" construction. They hide a specific random walk (a path) within the hypercube. Because random walks on high-dimensional cubes mix extremely rapidly, a randomized algorithm gains negligible information about the path's destination (the exact equilibrium) unless it happens to query a vertex directly on that path—an event that is statistically impossible within polynomial time.

Theoretical Framework

As a theoretical work, this paper does not rely on empirical datasets. Instead, it utilizes mathematical constructions of $n$-player bi-strategy games (games where each player has exactly two choices). These games serve as the worst-case scenarios necessary to prove that no algorithm can be universally efficient across all possible game structures.

Key Results: The Complexity Landscape

The most striking insight of the paper is the "hardness table" it establishes for $n$-player games. The transition from polynomial to exponential complexity is immediate upon the removal of either randomization or the allowance for approximation.

Complexity of finding Correlated Equilibria across different algorithmic constraints.

Theorem A: Deterministic Hardness

Any deterministic algorithm seeking even a 1/2-approximate CE requires an exponential number of queries, specifically $2^{\Omega(n)}$. This proves that the "path" to an equilibrium cannot be found reliably without the exploratory power of randomness.

Theorem B: Exact Hardness

Any algorithm—whether randomized or deterministic—seeking an exact CE requires an exponential number of queries ($2^{\Omega(n)}$), provided the payoffs are represented with sufficient precision. This suggests that the "last mile" of reaching a perfect equilibrium is where the computational cost becomes prohibitive.

Discussion and Future Work

The paper highlights that the "geometry" of the payoff space is the ultimate source of hardness. In high-dimensional strategy spaces, there are simply too many directions for a deterministic agent to be led astray.

However, several open questions remain:

  • Payoff Precision: Theorem B currently requires payoffs to be specified with $\Omega(n)$ bits. It is currently unknown if this hardness persists for games with very simple payoffs (e.g., binary 0/1 payoffs).
  • Support Size: The cost in the exact case includes the size of the output's support. Future research may investigate if randomized algorithms could find exact equilibria with massive supports more efficiently if the output size itself isn't counted as a cost.
  • Mathematical Foundations: While the paper proves the existence of this "perfect storm," the authors pose an open problem regarding the deeper mathematical reason why the specific combination of randomization and approximation is the unique key to tractability in game theory.

Summary updated

BibTeX
@article{hart2018query,
  author = {Sergiu Hart and Noam Nisan},
  title = {{The query complexity of correlated equilibria}},
  journal = {Games Econ. Behav.},
  year = {2018},
  doi = {10.1016/j.geb.2016.11.003},
}
Figure