Speaker: Andrew Gilpin

Time: Wednesday 12-1pm

Place: NSH 1507

Title: Finding equilibria in large sequential games of imperfect
information

Abstract:

Computing an equilibrium of an extensive form game of imperfect
information is a fundamental problem in computational game theory, but
current techniques do not scale to large games.  To address this, we
introduce the ordered game isomorphism and the related ordered game
isomorphic abstraction transformation. For an n-player sequential game
of imperfect information with observable actions and an ordered signal
space, we prove that any Nash equilibrium in an abstracted smaller
game, obtained by one or more applications of the transformation, can
be easily converted into a Nash equilibrium in the original game.  We
present an efficient algorithm, GameShrink, which automatically and
exhaustively abstracts the game.  Using GameShrink, we find an
equilibrium to a poker game that is over four orders of magnitude
larger than the largest poker game solved previously. To address even
larger games, we introduce approximation methods that do not preserve
equilibrium, but nevertheless yield (ex post) provably
close-to-optimal strategies.