In classical game theory, the analysis of $k \times k$ bimatrix games typically assumes that the payoff matrices for both players are known upfront. However, in many practical applications—ranging from online auctions to complex biological interactions—the underlying payoffs are hidden. In these scenarios, the payoffs must be discovered through "queries," where an algorithm proposes a pair of strategies and observes the resulting rewards.
This paper investigates the payoff query complexity of finding approximate Nash equilibria. The central question is: how many entries of the payoff matrix must be sampled to find a strategy profile where no player can significantly improve their outcome by deviating?
The Payoff Query Model
In the payoff query model, an algorithm can query any cell $(i, j)$ of the $k \times k$ payoff matrices $A$ and $B$ to receive the values $A_{i,j}$ and $B_{i,j}$. The goal is to find an $\epsilon$-Nash equilibrium—a pair of strategies where neither player can gain more than $\epsilon$ by changing their strategy—using as few queries as possible.
This research distinguishes between deterministic algorithms, which follow a fixed sequence of queries, and randomized algorithms, which can sample the matrix based on probability distributions. The findings reveal a significant gap between these two approaches, particularly regarding the "0.5 barrier."
Deterministic Complexity: The 0.5 Barrier
A major contribution of this work is the characterization of a "phase transition" in deterministic query complexity. The authors prove that for any $\epsilon < 1/2$, finding an $\epsilon$-Nash equilibrium requires $\Omega(k^2)$ queries. This implies that a deterministic algorithm must inspect nearly the entire matrix to guarantee a reasonably good approximation.
To prove this, the authors utilize an adversary argument. They design an adversary that strategically hides high-payoff entries in unqueried cells. If the algorithm stops too early, the adversary can reveal a payoff that makes the current strategy profile far from an equilibrium. Conversely, if $\epsilon \ge 1/2$, previous research has shown that an equilibrium can be found in $O(k)$ queries. Thus, $0.5$ represents a hard limit for deterministic efficiency.
Randomized Algorithms: Breaking the Barrier
The paper demonstrates that randomization is a "superpower" in the context of payoff queries. Unlike deterministic methods, randomized algorithms can break the 0.5 barrier, achieving better approximations with significantly fewer queries.
By adapting existing polynomial-time algorithms—specifically the BBM (Bosse, Byde, and Lavi) algorithm—the authors develop a randomized approach that finds a $(\frac{3-\sqrt{5}}{2} + \epsilon)$-Nash equilibrium (approximately $0.382 + \epsilon$) using only $O(\frac{k \log k}{\epsilon^2})$ queries. This near-linear complexity is a massive improvement over the quadratic requirement of deterministic algorithms.
The core technique involves using multiplicative weights and randomized sampling to estimate payoff vectors with high confidence. Instead of reading the whole matrix, the algorithm samples enough entries to build a statistical sketch of the game, which is sufficient to identify an approximate equilibrium.
Well-Supported Nash Equilibria (WSNE)
The study also extends to Well-Supported Nash Equilibria (WSNE), a stricter condition than the standard $\epsilon$-Nash equilibrium. In a WSNE, players are required to only play strategies that are nearly optimal; they cannot put any probability mass on "bad" strategies.
The authors provide the first query complexity results for this setting:
- Zero-Sum Games: They first establish a randomized algorithm for finding an $\epsilon$-WSNE in zero-sum games using $O(\frac{k \log k}{\epsilon^4})$ queries.
- General Games: Building on the zero-sum result and the KS (Kontogiannis and Spirakis) algorithm, they show that a $(2/3 + \epsilon)$-WSNE can be found in general bimatrix games using $O(\frac{k \log k}{\epsilon^4})$ queries.
Fundamental Limits of Randomization
While randomization allows us to find coarse approximations efficiently, it is not a panacea. The authors initiate the study of lower bounds for randomized algorithms, proving that finding a very precise equilibrium (where $\epsilon < 1/4k$) still requires $\Omega(k^2)$ queries. This result is significant because it rules out the possibility of query-efficient randomized algorithms for finding exact Nash equilibria. Even with the benefit of sampling, high-precision solutions require exhaustive search.
Conclusion and Future Directions
This research provides a complete picture of deterministic query complexity and establishes the first meaningful bounds for randomized query complexity in bimatrix games. The results show that while we can efficiently find "good enough" equilibria through sampling, finding highly accurate or exact equilibria remains fundamentally difficult.
Future work remains in narrowing the gap between the current randomized upper bound ($0.382$) and the lower bounds. Additionally, while this paper focuses on two-player games, extending these query complexity frameworks to $n$-player games presents a significant open challenge for the field.
Summary updated