Finding Approximate Nash Equilibria of Bimatrix Games via Payoff Queries

John Fearnley, Rahul Savani

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:

  1. 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.
  2. 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

Abstract

We study the deterministic and randomized query complexity of finding approximate equilibria in a k × k bimatrix game. We show that the deterministic query complexity of finding an ϵ-Nash equilibrium when ϵ < ½ is Ω(k2), even in zero-one constant-sum games. In combination with previous results [Fearnley et al. 2013], this provides a complete characterization of the deterministic query complexity of approximate Nash equilibria. We also study randomized querying algorithms. We give a randomized algorithm for finding a (3-√5/2 + ϵ)-Nash equilibrium using O(k.log k/ϵ2) payoff queries, which shows that the ½ barrier for deterministic algorithms can be broken by randomization. For well-supported Nash equilibria (WSNE), we first give a randomized algorithm for finding an ϵ-WSNE of a zero-sum bimatrix game using O(k.log k/ϵ4) payoff queries, and we then use this to obtain a randomized algorithm for finding a (⅔ + ϵ)-WSNE in a general bimatrix game using O(k.log k/ϵ4) payoff queries. Finally, we initiate the study of lower bounds against randomized algorithms in the context of bimatrix games, by showing that randomized algorithms require Ω(k2) payoff queries in order to find an ϵ-Nash equilibrium with ϵ < 1/4k, even in zero-one constant-sum games. In particular, this rules out query-efficient randomized algorithms for finding exact Nash equilibria.
BibTeX
@inproceedings{fearnley2014finding,
  author = {John Fearnley and Rahul Savani},
  title = {{Finding Approximate Nash Equilibria of Bimatrix Games via Payoff Queries}},
  booktitle = {EC},
  year = {2014},
  doi = {10.1145/2600057.2602847},
}
Figure