Computer Science Department
School of Computer Science, Carnegie Mellon University
Computing Equilibria by Incorporating
Qualitative Models
Sam Ganzfried, Tuomas Sandholm
March 2010
We present a new approach for solving large (even infinite) multiplayer games of imperfect information. The key idea behind our approach is that we include additional inputs in the form of qualitative models of equilibrium strategies (how the signal space should be qualitatively partitioned into action regions). In addition, we show that our approach can lead to strong strategies in large finite games that we approximate with infinite games. We prove that our main algorithm is correct even if given a set of qualitative models (satisfying a technical property) of which only some are accurate. We also show how to check the output in settings where all of the models might be wrong (under a weak assumption). Our algorithms can compute equilibria in several classes of games for which no prior algorithms have been developed, and we demonstrate that they run efficiently in practice. In the course of our analysis, we also develop the first mixed-integer programming formulations for computing an epsilon-equilibrium in general multiplayer normal and extensive-form games based on the extension of our initial algorithm to the multiplayer setting, which may be of independent interest. Experiments suggest that our approach of modeling a finite game with an infinite one can outperform the state of the art, abstraction-based approaches on some games. In addition, we demonstrate that our main algorithm can be used to improve play in two-player limit Texas hold'em–the most studied imperfect-information game in computer science–by solving endgames. Finally, we present experimental results on an infinite three-player game which suggest the effectiveness of our algorithm in games with more than two players.
40 pages
Return to:
SCS Technical Report Collection This page maintained by reports@cs.cmu.edu
School of Computer Science