Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

Extensive games can be used to model many scenarios in which multiple agents interact with an environment. There has been considerable recent research on finding strong strategies in very large, zero-sum extensive games. The standard approach in such work is to employ abstraction techniques to derive a more tractably sized game. An extensive game solver is then employed to compute an equilibrium in that abstract game, and the resulting strategy is presumed to be strong in the full game. Progress in this line of research has focused on solving larger abstract games, which more closely resemble the full game. However, there is an underlying assumption that by abstracting less, and solving a larger game, an agent will have a stronger strategy in the full game. In this work we show that this assumption is not true in general. Refining an abstraction can actually lead to a weaker strategy. We show examples of these abstraction pathologies in a small game of poker that can be analyzed exactly. These examples show that pathologies arise when abstracting both chance nodes as well as a player's actions. In summary, this paper shows that the standard approach to finding strong strategies for large extensive games rests on shaky ground.

REFERENCES

• 1: D. Billings, N. Burch, A. Davidson, R. Holte, J. Schaeffer, T. Schauenberg, and D. Szafron. Approximating game-theoretic optimal strategies for full-scale poker. In Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence (IJCAI), 2003.
• 2: Sam Ganzfried , Tuomas Sandholm, Computing an approximate jam/fold equilibrium for 3-player no-limit Texas Hold'em tournaments, Proceedings of the 7th international joint conference on Autonomous agents and multiagent systems, May 12-16, 2008, Estoril, Portugal
• 3: A. Gilpin, S. Hoda, J. Peña, and T. Sandholm. Gradient-based algorithms for finding nash equilibria in extensive form games. In Proceedings of the Eighteenth International Conference on Game Theory, 2007.
• 4: Andrew Gilpin , Tuomas Sandholm, A competitive Texas Hold'em poker player via automated abstraction and real-time equilibrium computation, proceedings of the 21st national conference on Artificial intelligence, p.1007-1013, July 16-20, 2006, Boston, Massachusetts
• 5: A. Gilpin and T. Sandholm. Potential-aware automated abstraction of sequential games, and holistic equilibrium analysis of texas hold'em poker. In Proceedings of the National Conference on Artificial Intelligence (AAAI). AAAI Press, 2007.
• 6: Andrew Gilpin , Tuomas Sandholm , Troels Bjerre Sørensen, A heads-up no-limit Texas Hold'em poker player: discretized betting models and automatically generated equilibrium-finding programs, Proceedings of the 7th international joint conference on Autonomous agents and multiagent systems, May 12-16, 2008, Estoril, Portugal
• 7: M. Johanson. Robust strategies and counter-strategies: Building a champion level computer poker player. Master's thesis, University of Alberta, 2007.
• 8: Daphne Koller , Avi Pfeffer, Representations and solutions for game-theoretic problems, Artificial Intelligence, v.94 n.1-2, p.167-215, July 1997 [doi>10.1016/S0004-3702(97)00023-4]
• 9: J. V. Neumann. Zur theorie der gesellschaftsspiele. Mathematische Annalen, 100(1):295--320, 1928.
• 10: M. Osborne and A. Rubenstein. A Course in Game Theory. The MIT Press, 1994.
• 11: F. Southey, M. Bowling, B. Larson, C. Piccione, N. Burch, D. Billings, and C. Rayner. Bayes. bluff: Opponent modelling in poker. In Proceedings of the 21st Annual Conference on Uncertainty in Artificial Intelligence (UAI), pages 550--558. AUAI Press, 2005.
• 12: B. V. Stengel. Efficient computation of behavior strategies. Games and Economic Behavior, 14:220--246, 1996.
• 13: M. Zinkevich, M. Bowling, and N. Burch. A new algorithm for generating equilibria in massive zero-sum games. In Proceedings of the Twenty-Second Conference on Artificial Intelligence (AAAI), pages 788--793, 2007.
• 14: M. Zinkevich, M. Johanson, M. Bowling, and C. Piccione. Regret minimization in games with incomplete information. In Advances in Neural Information Processing Systems 20 (NIPS), 2008.
• 15: M. Zinkevich and M. Littman. The AAAI computer poker competition. Journal of the International Computer Games Association, 29, 2006. News item.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search

General Terms:
Algorithms, Economics, Reliability

Keywords:
abstraction, equilibrium, game theory, pathologies