Finding equilibria in large 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, GameShrink, for abstracting the game using our isomorphism exhaustively. Its complexity is Õ(n²), where 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 GameShrink has time and space complexity sublinear in the size of the game tree. Using 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. We discuss several electronic commerce applications for GameShrink. To address even larger games, we introduce approximation methods that do not preserve equilibrium, but nevertheless yield (ex post) provably close-to-optimal strategies.

REFERENCES

• 1: W. Ackermann. Zum Hilbertschen Aufbau der reellen Zahlen. Math. Annalen, 99:118--133, 1928.
• 2: D. Applegate, G. Jacobson, and D. Sleator. Computer analysis of sprouts. Technical Report CMU-CS-91-144, 1991.
• 3: R. Bellman and D. Blackwell. Some two-person games involving bluffing. PNAS, 35:600--605, 1949.
• 4: 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 IJCAI, 2003.
• 5: Darse Billings , Aaron Davidson , Jonathan Schaeffer , Duane Szafron, The challenge of poker, Artificial Intelligence, v.134 n.1-2, p.201-240, January 2002 [doi>10.1016/S0004-3702(01)00130-8 ]
• 6: B. Bollobàs. Combinatorics. Cambridge University Press, 1986.
• 7: A. Casajus. Weak isomorphism of extensive games. Mathematical Social Sciences, 46:267--290, 2003.
• 8: X. Chen and X. Deng. Settling the complexity of 2-player Nash equilibrium. ECCC, Report No. 150, 2005.
• 9: V. Chvátal. Linear Programming. W. H. Freeman & Co., 1983.
• 10: B. P. de Bruin. Game transformations and game equivalence. Technical note x-1999-01, University of Amsterdam, Institute for Logic, Language, and Computation, 1999.
• 11: S. Elmes and P. J. Reny. On the strategic equivalence of extensive form games. J. of Economic Theory, 62:1--23, 1994.
• 12: L. R. Ford, Jr. and D. R. Fulkerson. Flows in Networks. Princeton University Press, 1962.
• 13: A. Gilpin and T. Sandholm. Finding equilibria in large sequential games of imperfect information. Technical Report CMU-CS-05-158, Carnegie Mellon University, 2005.
• 14: A. Gilpin and T. Sandholm. Optimal Rhode Island Hold'em poker. In AAAI, pages 1684--1685, Pittsburgh, PA, USA, 2005.
• 15: A. Gilpin and T. Sandholm. A competitive Texas Hold'em poker player via automated abstraction and real-time equilibrium computation. Mimeo, 2006.
• 16: A. Gilpin and T. Sandholm. A Texas Hold'em poker player based on automated abstraction and real-time equilibrium computation. In AAMAS, Hakodate, Japan, 2006.
• 17: M. L. Ginsberg. Partition search. In AAAI, pages 228--233, Portland, OR, 1996.
• 18: Matthew L. Ginsberg, GIB: Steps Toward an Expert-Level Bridge-Playing Program, Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence, p.584-593, July 31-August 06, 1999
• 19: S. Govindan and R. Wilson. A global Newton method to compute Nash equilibria. J. of Econ. Theory, 110:65--86, 2003.
• 20: Craig A. Knoblock, Automatically generating abstractions for planning, Artificial Intelligence, v.68 n.2, p.243-302, Aug. 1994 [doi>10.1016/0004-3702(94)90069-8 ]
• 21: E. Kohlberg and J.-F. Mertens. On the strategic stability of equilibria. Econometrica, 54:1003--1037, 1986.
• 22: D. Koller and N. Megiddo. The complexity of two-person zero-sum games in extensive form. Games and Economic Behavior, 4(4):528--552, Oct. 1992.
• 23: D. Koller and N. Megiddo. Finding mixed strategies with small supports in extensive form games. International Journal of Game Theory, 25:73--92, 1996.
• 24: D. Koller, N. Megiddo, and B. von Stengel. Efficient computation of equilibria for extensive two-person games. Games and Economic Behavior, 14(2):247--259, 1996.
• 25: 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 ]
• 26: D. M. Kreps and R. Wilson. Sequential equilibria. Econometrica, 50(4):863--894, 1982.
• 27: H. W. Kuhn. Extensive games. PNAS, 36:570--576, 1950.
• 28: H. W. Kuhn. A simplified two-person poker. In Contributions to the Theory of Games, volume 1 of Annals of Mathematics Studies, 24, pages 97--103. Princeton University Press, 1950.
• 29: H. W. Kuhn. Extensive games and the problem of information. In Contributions to the Theory of Games, volume 2 of Annals of Mathematics Studies, 28, pages 193--216. Princeton University Press, 1953.
• 30: C. Lemke and J. Howson. Equilibrium points of bimatrix games. Journal of the Society for Industrial and Applied Mathematics, 12:413--423, 1964.
• 31: Richard J. Lipton , Evangelos Markakis , Aranyak Mehta, Playing large games using simple strategies, Proceedings of the 4th ACM conference on Electronic commerce, p.36-41, June 09-12, 2003, San Diego, CA, USA [doi>10.1145/779928.779933]
• 32: Chao-Lin Liu , Michael P. Wellman, On state-space abstraction for anytime evaluation of Bayesian networks, ACM SIGART Bulletin, v.7 n.2, p.50-57, April 1996 [doi>10.1145/242587.242601]
• 33: A. Mas-Colell, M. Whinston, and J. R. Green. Microeconomic Theory. Oxford University Press, 1995.
• 34: R. D. McKelvey and A. McLennan. Computation of equilibria in finite games. In Handbook of Computational Economics, volume 1, pages 87--142. Elsevier, 1996.
• 35: Peter Bro Miltersen , Troels Bjerre Sørensen, Computing sequential equilibria for two-player games, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.107-116, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109570]
• 36: J. Nash. Equilibrium points in n-person games. Proc. of the National Academy of Sciences, 36:48--49, 1950.
• 37: J. F. Nash and L. S. Shapley. A simple three-person poker game. In Contributions to the Theory of Games, volume 1, pages 105--116. Princeton University Press, 1950.
• 38: A. Perea. Rationality in extensive form games. Kluwer Academic Publishers, 2001.
• 39: A. Pfeffer, D. Koller, and K. Takusagawa. State-space approximations for extensive form games, July 2000. Talk given at the First International Congress of the Game Theory Society, Bilbao, Spain.
• 40: R. Porter, E. Nudelman, and Y. Shoham. Simple search methods for finding a Nash equilibrium. In AAAI, pages 664--669, San Jose, CA, USA, 2004.
• 41: I. Romanovskii. Reduction of a game with complete memory to a matrix game. Soviet Mathematics, 3:678--681, 1962.
• 42: T. Sandholm and A. Gilpin. Sequences of take-it-or-leave-it offers: Near-optimal auctions without full valuation revelation. In AAMAS, Hakodate, Japan, 2006.
• 43: T. Sandholm, A. Gilpin, and V. Conitzer. Mixed-integer programming methods for finding Nash equilibria. In AAAI, pages 495--501, Pittsburgh, PA, USA, 2005.
• 44: Rahul Savani , Bernhard von Stengel, Exponentially Many Steps for Finding a Nash Equilibrium in a Bimatrix Game, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04), p.258-267, October 17-19, 2004 [doi>10.1109/FOCS.2004.28]
• 45: R. Selten. Spieltheoretische behandlung eines oligopolmodells mit nachfrageträgheit. Zeitschrift fòr die gesamte Staatswissenschaft, 12:301--324, 1965.
• 46: R. Selten. Evolutionary stability in extensive two-person games -- correction and further development. Mathematical Social Sciences, 16:223--266, 1988.
• 47: Jiefu Shi , Michael L. Littman, Abstraction Methods for Game Theoretic Poker, Revised Papers from the Second International Conference on Computers and Games, p.333-345, October 26-28, 2000
• 48: S. J. J. Smith, D. S. Nau, and T. Throop. Computer bridge: A big win for AI planning. AI Magazine, 19(2):93--105, 1998.
• 49: Robert Endre Tarjan, Efficiency of a Good But Not Linear Set Union Algorithm, Journal of the ACM (JACM), v.22 n.2, p.215-225, April 1975 [doi>10.1145/321879.321884]
• 50: F. Thompson. Equivalence of games in extensive form. RAND Memo RM-759, The RAND Corporation, Jan. 1952.
• 51: J. von Neumann and O. Morgenstern. Theory of games and economic behavior. Princeton University Press, 1947.
• 52: B. von Stengel. Efficient computation of behavior strategies. Games and Economic Behavior, 14(2):220--246, 1996.
• 53: B. von Stengel. Computing equilibria for two-person games. In Handbook of Game Theory, volume 3. North Holland, Amsterdam, 2002.
• 54: R. Wilson. Computing equilibria of two-person games from the extensive form. Management Science, 18(7):448--460, 1972.
• 55: Stephen J. Wright, Primal-dual interior-point methods, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1997

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

  J. Computer Applications
  J.4 SOCIAL AND BEHAVIORAL SCIENCES
      Subjects: Economics

General Terms:
Algorithms, Economics, Theory

Keywords:
automated abstraction, computer poker, equilibrium finding, game theory, sequential games of imperfect information