Date:

2014-09-22 14:00

Room:

Name of External Lecturer:

Branislav Bošanský

Affiliation of External Lecturer:

FEL ČVUT

Department:

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.