Computing equilibria by incorporating qualitative models
Sam Ganzfried, Tüomas Sandholm · 2010
IIS-0905390. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation. We also acknowledge Intel Corporation and IBM for their machine gifts. Keywords: Game theory, continuous games, games of imperfect information, equilibrium 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