Double Oracle Algorithm for Computing Equilibria in Continuous Games

Lukás Adam, Rostislav Horcík, Tomás Kasl, Tomás KroupaAAAI 2021 · DOI

Abstract

Continuous two-person zero-sum games present a significant computational challenge due to their infinite strategy spaces. This paper adapts the Double Oracle (DO) algorithm—originally designed for large-scale finite games—to the continuous domain. We provide a theoretical proof of convergence to a Nash equilibrium and demonstrate through numerical experiments that the algorithm efficiently finds $\epsilon$-approximate equilibria, significantly outperforming traditional methods like fictitious play in terms of convergence speed and precision.

Introduction: Solving the Infinite

In game theory, standard solution methods often assume a finite set of moves. However, many real-world scenarios, such as resource allocation or physical coordination, involve continuous strategy spaces where a "move" can be any real value within an interval. These continuous games are notoriously difficult to solve because they involve utility functions defined over uncountable sets, making it impossible to represent the game as a simple matrix.

The Double Oracle Framework

The core contribution of this work is the extension of the Double Oracle (DO) framework to continuous settings. Rather than attempting to solve the infinite game directly, the algorithm proceeds by solving a sequence of finite "subgames":

  1. Initialization: Start with a small, finite subset of strategies for both players.
  2. Subgame Solution: Compute the Nash equilibrium of the current finite subgame using standard linear programming.
  3. Best Response Oracles: For each player, find the best response strategy in the entire continuous space against the opponent's current mixed strategy.
  4. Expansion: Add these best responses to the strategy sets and repeat until the duality gap (the difference between the upper and lower bounds of the game's value) is sufficiently small.

The authors prove that this iterative process converges to a Nash equilibrium of the original continuous game, leveraging the "weak convergence of measures" to show that finite subgames can effectively "trap" the true equilibrium.

Empirical Performance and Comparison

The algorithm was evaluated against Fictitious Play (FP), the traditional iterative solver for such games. In benchmarks like the Townsend function—a highly oscillatory surface—and polynomial games, the Double Oracle algorithm demonstrated superior performance.

Comparison of convergence between Double Oracle and Fictitious Play. The DO algorithm closes the duality gap much faster than the averaging approach of FP.

While Fictitious Play updates strategies slowly by averaging past moves, DO jumps directly to the optimal counter-move in each iteration. This leads to a much faster collapse of the duality gap, providing a clear mathematical guarantee of the solution's quality.

High-Dimensional Resource Allocation: Colonel Blotto

To test the algorithm's scalability, the researchers applied it to the Continuous Colonel Blotto game. In this scenario, players must distribute a fixed resource across multiple battlefields. This high-dimensional problem requires sophisticated "Best Response" oracles, implemented here using Mixed-Integer Linear Programming (MILP).

Strategy distribution on a simplex and convergence for the Continuous Colonel Blotto game. The algorithm recovers complex symmetric patterns consistent with theoretical predictions.

The results showed that DO could recover complex, symmetric strategy distributions, often visualized as patterns on a simplex. The algorithm's ability to handle these high-dimensional spaces confirms its robustness beyond simple one-dimensional benchmarks.

Key Insights and Conclusion

A vital theoretical insight from this research is that any continuous game possesses an $\epsilon$-equilibrium with finite support. This justifies the DO approach of building finite strategy sets to solve infinite problems.

While the algorithm is highly effective, its performance is tied to the efficiency of the "Best Response" oracle. Future work includes exploring convergence rates and extending the framework to multi-player or general-sum games. Overall, this adaptation of the Double Oracle algorithm provides a powerful, general-purpose tool for solving complex continuous games that were previously computationally intractable.

Summary updated

BibTeX
@inproceedings{adam2021double,
  author = {Lukás Adam and Rostislav Horcík and Tomás Kasl and Tomás Kroupa},
  title = {{Double Oracle Algorithm for Computing Equilibria in Continuous Games}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.1609/aaai.v35i6.16641},
}
Figure