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.

25 pages

Return to: SCS Technical Report Collection
School of Computer Science

This page maintained by [email protected]