ABSTRACT
We present a new procedure for solving large games of imperfect information. Our approach involves---somewhat counterintuitively---solving an infinite approximation of the original game, then mapping the equilibrium to a strategy profile in the original game. Our main algorithm exploits some qualitative model of equilibrium structure as an additional input to find an equilibrium in continuous games. We prove that our approach is correct even if given a set of qualitative models (satisfying a technical property) of which only some are accurate. We compute equilibria in several classes of games for which no prior algorithms have been developed. 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 can outperform the prior state of the art, abstraction-based approaches. In addition, we demonstrate the effectiveness of our main algorithm on a subgame of limit Texas hold'em---the most studied imperfect-information game in computer science.
- J. Ankenman and B. Chen. The Mathematics of Poker. 2006.Google Scholar
- C. Archibald and Y. Shoham. Modeling billiards games. AAMAS, 2009. Google ScholarDigital Library
- D. Billings, et al. Approximating game-theoretic optimal strategies for full-scale poker. IJCAI, 2003. Google ScholarDigital Library
- J. Bisschop. AIMMS---Optimization Modeling. 2006. Google ScholarDigital Library
- L. Blumrosen, et al. Auctions with severely bounded communication. JAIR, 2007. Google ScholarDigital Library
- X. Chen and X. Deng. Settling the complexity of 2-player Nash equilibrium. FOCS, 2006. Google ScholarDigital Library
- K. Etessami and M. Yannakakis. On the complexity of Nash equilibria and other fixed points. FOCS, 2007. Google ScholarDigital Library
- D. Fudenberg and J. Tirole. Game Theory. 1991.Google Scholar
- S. Ganzfried and T. Sandholm. Computing equilibria in multiplayer stochastic games of imperfect information. IJCAI, 2009. Google ScholarDigital Library
- A. Gilpin, et al. Gradient-based algorithms for finding Nash equilibria in extensive form games. WINE, 2007. Google ScholarDigital Library
- D. Koller, et al. Efficient computation of equilibria for extensive two-person games. GEB, 1996.Google ScholarCross Ref
- H. Kuhn. Simplified two-person poker. Contributions to the Theory of Games, 1950.Google Scholar
- T. Sandholm and A. Gilpin. Sequences of take-it-or-leave-it offers: Near-optimal auctions without full valuation revelation. AAMAS, 2006. Google ScholarDigital Library
- T. Sandholm, et al. Mixed-integer programming methods for finding Nash equilibria. AAAI, 2005. Google ScholarDigital Library
- T. Sandholm and V. Lesser. Leveled commitment contracts and strategic breach. GEB, 2001.Google ScholarCross Ref
- S. Singh, et al. Computing approximate Bayes-Nash equilibria in tree-games of incomplete information. EC, 2004. Google ScholarDigital Library
- N. Stein, et al. Separable and low-rank continuous games. International Journal of Game Theory, 2008.Google ScholarCross Ref
- J. Vielma and G. Nemhauser. Modeling disjunctive constraints with a logarithmic number of binary variables and constraints. IPCO, 2008. Google ScholarDigital Library
- Y. Vorobeychik and M. Wellman. Stochastic search methods for Nash equilibrium approximation in simulation-based games. AAMAS, 2008. Google ScholarDigital Library
- K. Waugh, et al. Abstraction pathologies in extensive games. AAMAS, 2009. Google ScholarDigital Library
- M. Zinkevich, et al. Regret minimization in games with incomplete information. NIPS, 2007.Google ScholarDigital Library
Index Terms
Computing equilibria by incorporating qualitative models?
Recommendations
Computing an approximate jam/fold equilibrium for 3-player no-limit Texas Hold'em tournaments
AAMAS '08: Proceedings of the 7th international joint conference on Autonomous agents and multiagent systems - Volume 2A recent paper computes near-optimal strategies for two-player no-limit Texas hold'em tournaments; however, the techniques used are unable to compute equilibrium strategies for tournaments with more than two players. Motivated by the widespread ...
Finding equilibria in large sequential games of imperfect information
EC '06: Proceedings of the 7th ACM conference on Electronic commerceFinding 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 ...
GS3 and Tartanian: game theory-based heads-up limit and no-limit Texas Hold'em poker-playing programs
AAMAS '08: Proceedings of the 7th international joint conference on Autonomous agents and multiagent systems: demo papersWe demonstrate two game theory-based programs for heads-up limit and no-limit Texas Hold'em poker. The first player, GS3, is designed for playing limit Texas Hold'em, in which all bets are a fixed amount. The second player, Tartanian, is designed for ...
Comments