Solving Two-Player Extensive-Form Games: Algorithms and Compact Strategy Representation

Many real-world scenarios can be modeled as finite sequential games with imperfect information called extensive-form games. The strategy space in these games is composed of sequences of actions causing an exponential number of pure strategies and posing computational challenges to solve these games using mathematical programming. However, a compact representation of strategies can be often used to avoid the exponential size of mathematical programs. I will introduce our two novel algorithms that exploit the compact representation of strategies in extensive-form games for computing two different solution concepts. First algorithm combines the compact representation with incremental generation of strategies and finds Nash equilibria in zero-sum games; second algorithm is the first to use the compact representation for computing Stackelberg equilibria in general extensive-form games.