Abstract
Finding a Correlated Equilibrium (CE) is often considered computationally efficient because it can be formulated as a linear program. However, this efficiency typically assumes full access to the game's payoff matrix. This paper examines the query complexity of finding an exact CE in $n$-player games where payoffs are only accessible through a black-box oracle. We prove that any deterministic algorithm requires an exponential number of queries—at least $2^n / (n^2 + 1)$—to compute an exact CE. This result establishes a fundamental complexity gap between exact and approximate solutions in the black-box model.
Introduction
In game theory, the Correlated Equilibrium (CE) is a powerful solution concept that generalizes the Nash Equilibrium by allowing players to coordinate their actions via a shared signal. While computing a Nash Equilibrium is PPAD-complete, CE is generally viewed as "easy" when the game is represented succinctly or the full payoff matrix is known.
However, in many practical scenarios, the game is a "black box": we can only observe the utilities resulting from specific pure-action profiles. This paper addresses whether an exact CE can be found in polynomial time relative to the number of players ($n$) when only pure-action queries are permitted.
Methods: The Adversarial Hypercube
The authors employ a query complexity framework combined with an adversarial argument to establish the lower bound. The game is modeled as an $n$-dimensional hypercube where each vertex represents a strategy profile for $n$ players, each having two actions.
The Adversary and the Giant-Component Lemma
To prove the lower bound, the authors construct an "adversary" that adaptively assigns payoffs as the algorithm queries different profiles. The goal of the adversary is to ensure that no distribution over the queried profiles can constitute a CE.
The proof hinges on a "Giant-Component Lemma" derived from graph theory and Cheeger’s inequality. The lemma demonstrates that if an algorithm has queried only a sub-exponential number of vertices, there remains a massive, connected "unknown" region in the hypercube.
As shown in the figure, the adversary maintains a set of unqueried vertices ($W_{t+1}$) that form a large component. By manipulating incentives such that the sum of utility differences is negative for all queried points, the adversary forces any potential equilibrium to include unqueried (and thus unknown) parts of the game.
Key Results
The primary contribution of this work is the establishment of a rigorous exponential lower bound for deterministic algorithms.
- Exponential Query Bound: Theorem 1 states that any deterministic algorithm requires $q \ge \frac{2^n}{n^2+1}$ queries to find an exact CE. For a game with 100 players, this makes the computation practically impossible.
- Coarse Correlated Equilibrium: The authors demonstrate that this hardness extends to Coarse Correlated Equilibria (the Hannan set), indicating that even broader coordination concepts suffer from the same query complexity constraints.
- The Role of the Oracle: This work clarifies why previous "easy" results for CE exist: they often rely on "mixed-action" oracles that return expected utilities for probability distributions. Without this aggregation capability, the problem's complexity explodes.
Discussion and Conclusion
This research highlights a stark contrast between finding approximate and exact equilibria. While approximate CE can be found efficiently using simple learning rules like regret matching, the jump to an exact solution is computationally massive in the pure-action model.
While the focus here is on deterministic algorithms and binary action spaces, the results provide a foundational lower bound. Concurrent work by Hart and Nisan (2013) has since generalized these findings to randomized algorithms and certain approximate cases, further solidifying the understanding that exact equilibrium computation is fundamentally hard in black-box settings.
Summary updated