Exponential Lower Bounds on the Double Oracle Algorithm in Zero-Sum Games

Brian Hu Zhang, Tüomas Sandholm, Chuanwen Feng, Yukun Cao, Xike Xie, S. Kevin Zhou, Lei Feng

Abstract

The Double Oracle (DO) algorithm is a cornerstone of modern computational game theory, enabling the solution of massive games by iteratively expanding a subset of strategies. Despite its empirical success in domains like StarCraft and Stratego, its theoretical complexity has remained poorly understood. This paper establishes the first exponential lower bounds for DO, demonstrating that it can require exponentially many iterations to converge in both stochastic and extensive-form games. We show that specific "counting" game structures can force DO into a linear search over the strategy space, and we analyze the impact of tiebreaking schemes on these bounds. Our findings suggest that the efficiency of DO in practice is not a universal property but depends on the strategic structure of the game.

Introduction

In game theory, solving games with a massive number of possible strategies is computationally daunting. The Double Oracle (DO) algorithm addresses this by starting with a small subset of strategies (a "meta-game") and iteratively adding the best response to the current meta-Nash equilibrium. While DO often converges quickly in practice—sometimes in just a few dozen iterations—this paper investigates whether its efficiency is guaranteed or if "trap" games can be constructed to force exponential scaling. This research is critical for understanding the fundamental limits of iterative strategy expansion in complex strategic environments.

Theoretical Framework and Methodology

The authors employ a theoretical approach to construct mathematical counterexamples that exploit DO's mechanics. The core construction is the "n-bigger-number game," where players pick numbers from $0$ to $n-1$. The winner is determined by specific rules: picking a larger number wins unless the numbers are consecutive, which flips the outcome.

By mapping this logic into Partially Observable Stochastic Games (POSGs) and Extensive-Form Games (EFGs), the authors demonstrate that DO can be forced into a "counting" behavior. In this scenario, the algorithm adds strategies one by one in a linear sequence instead of jumping toward the equilibrium. This is particularly problematic when the number of strategies $n$ is exponential relative to the game's description (e.g., $2^k$ for a $k$-bit game).

Figure 5: A game structure illustrating the strategic dependencies used to construct lower bound proofs.

The study also examines the role of tiebreaking schemes. Since games often have multiple best responses, the authors test whether DO fails only under adversarial tiebreaking (where an adversary picks the worst possible response to add) or even with random selection.

Key Insights and Ideas

  • The "Counting" Trap: The most significant insight is that DO can be "tricked" into a linear search. If a game is structured such that the best response to strategy $i$ is always strategy $i+1$, DO will take $n$ iterations to solve a game with $n$ strategies. This leads to an exponential blowup in complexity for many standard game representations.
  • Tiebreaking is a Critical Variable: For Extensive-Form Games (tree-like games), the authors found that DO only hits the exponential wall if the tiebreaking is "adversarial." However, for POSGs, the algorithm can fail even with random initialization and random choices, suggesting a deeper structural vulnerability in stochastic settings.
  • Strategic vs. Structural Complexity: The paper highlights that a game might look simple in terms of its state space but possess a "flat" strategic landscape that makes DO's iterative approach fundamentally inefficient.

Complexity Bounds and Results

The paper presents several theorems establishing lower bounds across different game types, summarized in the table below. These results prove that DO is not a polynomial-time algorithm in the worst case.

Figure 6: Summary of the paper's main theorems and the resulting lower bounds on DO iterations across various game properties.

Key results include:

  • Theorem 3.2: In POSGs with $O(k)$ states, DO requires $\Theta(2^k)$ iterations in expectation, even when starting with random strategies.
  • Theorem 3.5: In the most restrictive case—a zero-sum, fully observable, tree-form game—DO still takes at least $2^{k-1}$ iterations if the meta-Nash and best responses are chosen adversarially.
  • Approximation Hardness: Even when DO is allowed to find an $\epsilon$-approximate equilibrium (rather than an exact one), the authors show it can still require exponential time for certain games, with $\epsilon$ scaling as $2^{-\Theta(k)}$.

Conclusion and Future Work

These results provide a theoretical limit to the Double Oracle algorithm, showing that its practical success is not due to a universal polynomial-time guarantee. While most practical games likely don't have the specific "incrementing" structure required to trigger this exponential blowup, the existence of these bounds is a cautionary tale for algorithm design.

Future directions include investigating the "$\alpha$-Double Oracle" variant, where a best response is only added if it improves utility by a certain threshold, and exploring whether these bounds apply to the "Deep" version of DO (known as PSRO) used in modern reinforcement learning research.

Summary updated

BibTeX
@inproceedings{zhang2024exponential,
  author = {Brian Hu Zhang and Tüomas Sandholm and Chuanwen Feng and Yukun Cao and Xike Xie and S. Kevin Zhou and Lei Feng},
  title = {{Exponential Lower Bounds on the Double Oracle Algorithm in Zero-Sum Games}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2024},
  url = {https://openreview.net/forum?id=qPFEo5BD5S},
}
Figure