Finding approximate Nash equilibria of bimatrix games via payoff queries

John Fearnley, Rahul Savani

TL;DR

This paper investigates the efficiency of finding approximate Nash equilibria in bimatrix games using a "payoff query" model. The authors establish a fundamental limit for deterministic algorithms, showing they require a quadratic number of queries ($ \Omega(k^2) $) for approximate equilibria, and then demonstrate that randomization can break this barrier, achieving near-linear query complexity ($ O(k \log k) $) for certain approximations.

What Problem Does This Paper Address?

Game theory's central concept, the Nash equilibrium, represents a stable state where no player can improve their outcome by unilaterally changing their strategy. However, finding exact Nash equilibria can be computationally expensive. This paper focuses on the "payoff query" model, a more practical setting where we know the game's structure (strategy spaces) but not the payoffs. To learn payoffs, we must "query" the game, essentially playing a strategy profile and observing the outcome. The core problem is to find approximate Nash equilibria (where players are "close" to their best possible outcome) while minimizing the number of these costly payoff queries. Specifically, the paper addresses the gap in understanding the query complexity for approximate Nash equilibria, especially when the approximation tolerance ($ \epsilon $) is small, and explores how randomization can improve efficiency compared to deterministic approaches.

Methods

The paper employs a combination of lower bound proofs and algorithm design. For lower bounds, they use an "adversarial" approach, constructing specific game instances and demonstrating that any algorithm, even a randomized one, would need to make a certain number of queries to distinguish between game states and guarantee finding an approximate equilibrium. This involves carefully crafting payoff matrices and analyzing the information gained from queries. For upper bounds, they adapt existing algorithms. A key technique is reducing the problem of finding approximate Nash equilibria in general games to finding them in simpler zero-sum games, for which more efficient algorithms exist. They then leverage randomized algorithms for zero-sum games and combine them with techniques for approximating payoff vectors to construct efficient algorithms for the original problem.

Datasets

Not discussed in the paper. The paper deals with theoretical game instances rather than empirical datasets.

Key Insights and Ideas

  • Deterministic Barrier: The paper reveals a significant hurdle for deterministic algorithms: finding an $ \epsilon $-Nash equilibrium (where $ \epsilon < 1/2 $) requires $ \Omega(k^2) $ payoff queries. This means that for larger games, a deterministic algorithm essentially needs to query almost all possible strategy profiles.
  • Randomization's Power: Crucially, randomization can overcome this $ \Omega(k^2) $ barrier. The authors show that randomized algorithms can find approximate Nash equilibria with significantly fewer queries, specifically $ O(k \log k) $. This highlights the power of probabilistic approaches in this query model.
  • Breaking the 1/2 Threshold: For deterministic algorithms, the query complexity jumps from $ O(k) $ to $ \Omega(k^2) $ when the approximation tolerance $ \epsilon $ drops below $ 1/2 $. Randomized algorithms can achieve good approximations even for $ \epsilon $ values below $ 1/2 $ with much better query complexity.
  • Well-Supported Nash Equilibria (WSNE): The paper extends the analysis to WSNE, a stricter form of approximate equilibrium. They develop randomized algorithms for finding WSNE with $ O(k \log k) $ queries, demonstrating that randomization is also effective here.
  • Lower Bounds for Randomized Algorithms: The paper also establishes a lower bound for randomized algorithms, showing that finding a $ 1/(6k) $-Nash equilibrium still requires $ \Omega(k^2) $ queries. This implies that query-efficient randomized algorithms for exact Nash equilibria are not possible.

Key Results

  • Deterministic $ \epsilon $-Nash Equilibrium: The deterministic query complexity for finding an $ \epsilon $-Nash equilibrium is $ \Theta(k) $ for $ \epsilon > 1/2 $ and $ \Omega(k^2) $ for $ \epsilon < 1/2 $.
  • Randomized $ \epsilon $-Nash Equilibrium: A randomized algorithm can find a $ (3-\sqrt{5}/2 + \epsilon) $-Nash equilibrium using $ O(k \log k) $ payoff queries.
  • Randomized $ \epsilon $-WSNE:
    • For zero-sum games, an $ \epsilon $-WSNE can be found using $ O(k \log k) $ queries.
  • For general bimatrix games, a $ (2/3 + \epsilon) $-WSNE can be found using $ O(k \log k) $ queries.
  • Randomized Lower Bound: The randomized query complexity for finding a $ 1/(6k) $-Nash equilibrium is $ \Omega(k^2) $.

Limitations and Future Work

  • Constant Approximations: The paper initiates the study of lower bounds against randomized algorithms but focuses on specific small $ \epsilon $ values. A key open problem is to prove lower bounds for constant approximations of Nash equilibria.
  • Matching Bounds: While the paper provides $ O(k \log k) $ upper bounds for randomized algorithms for $ \epsilon $-Nash and $ \epsilon $-WSNE, matching $ \Omega(k \log k) $ lower bounds are not proven for these specific cases.
  • WSNE Deterministic Complexity: The paper characterizes the deterministic query complexity for $ \epsilon $-Nash equilibria but not for $ \epsilon $-WSNE when $ \epsilon > 1/2 $.
  • Practical Algorithms: The authors mention that existing polynomial-time algorithms for approximate Nash equilibria (e.g., using gradient descent) are not easily adaptable to the query model, suggesting future work in bridging this gap.

Summary updated

Abstract

We study the deterministic and randomized query complexity of finding approximate equilibria in a k x k bimatrix game. We show that the deterministic query complexity of finding an ε-Nash equilibrium when ε < 1/2 is Ω(k2), even in zero-one constant-sum games. In combination with previous results, 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 1/2 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 O(k . log k/ε4) payoff queries, and we then use this to obtain a randomized algorithm for finding a (2/3 + ε)-WSNE in a general bimatrix game using O(k . log k /ε2) 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 Omega(k2) payoff queries in order to find a 1/6k-Nash equilibrium, 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