Working Seminar on Formal Models, Discrete Structures, and Algorithms

Double-oracle Algorithms for Solving Large Games

Branislav Bosansky (Czech Technical University in Prague)

When: June 13, 2pm

Where: room G2.91b


Successful deployment of game-theoretic models to real-world applications increase the need for scaling-up solvable instances of games. Using standard methods and out-of-box optimization solvers is often intractable due to large memory requirements for even the simplest two-player zero-sum games. Therefore, a number of deployed solutions use iterative methods for computing the equilibria. These methods are often based on column generation techniques used in operations research, that are known as oracle algorithms in computational game theory. The main idea of the oracle methods is to iteratively construct the game with a hope of finding a solution before constructing the complete game. Therefore, the first part of the talk will describe principles behind the oracle algorithms, while in the second part of the talk a new algorithm based on oracle methods for computing exact Nash equilibrium in two-player zero-sum extensive-form games with imperfect information will be described.