Thumbnail
Access Restriction
Subscribed

Author Gilpin, Andrew ♦ Sandholm, Tuomas
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2007
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Automated abstraction ♦ Computer poker ♦ Equilibrium finding ♦ Game theory ♦ Sequential games of imperfect information
Abstract Finding 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 a multi-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 algorithm, $\textit{GameShrink},$ for abstracting the game using our isomorphism exhaustively. Its complexity is $õ(n^{2}),$ where $\textit{n}$ is the number of nodes in a structure we call the signal tree. It is no larger than the game tree, and on nontrivial games it is drastically smaller, so $\textit{GameShrink}$ has time and space complexity $\textit{sublinear}$ in the size of the game tree. Using $\textit{GameShrink},$ we find an equilibrium to a poker game with 3.1 billion nodes—over four orders of magnitude more than in 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.
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2007-10-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 54
Issue Number 5


Open content in new tab

   Open content in new tab
Source: ACM Digital Library