Solving Extensive-Form Games with Double-Oracle Methods

We investigate iterative algorithms for computing exact Nash equilibria in two-player zero-sum extensive-form games. The algorithms use an algorithmic framework of double-oracle methods. The main idea is to restrict the game by allowing the players to play only some of the strategies, and then iteratively solve this restricted game and exploit fast best-response algorithms to add additional strategies to the restricted game for the next iteration. The experimental evaluation on different games shows that the doubleoracle methods often provide significant improvement in runningtime, and can find exact solution of much larger games compared to the existing approaches.

Authors

• Branislav Bosansky

Keywords

• game theory
• extensive-form games
• algorithms
• iterative approaches