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. D. Billings, A. Davidson, J. Schaeffer, and D. Szafron. The challenge of poker. Artificial Intelligence, 134:201--240, 2002.]]
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. M. L. Ginsberg. GIB: Steps toward an expert-level bridge-playing program. In IJCAI, Stockholm, Sweden, 1999.]]
19. S. Govindan and R. Wilson. A global Newton method to compute Nash equilibria. J. of Econ. Theory, 110:65--86, 2003.]]
20. C. A. Knoblock. Automatically generating abstractions for planning. Artificial Intelligence, 68(2):243--302, 1994.]]
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. D. Koller and A. Pfeffer. Representations and solutions for game-theoretic problems. Artificial Intelligence, 94(1):167--215, July 1997.]]
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. R. Lipton, E. Markakis, and A. Mehta. Playing large games using simple strategies. In ACM-EC, pages 36--41, 2003.]]
32. C.-L. Liu and M. Wellman. On state-space abstraction for anytime evaluation of Bayesian networks. SIGART Bulletin, 7(2):50--57, 1996.]]
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. P. B. Miltersen and T. B. Sørensen. Computing sequential equilibria for two-player games. In SODA, pages 107--116, 2006.]]
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. R. Savani and B. von Stengel. Exponentially many steps for finding a Nash equilibrium in a bimatrix game. In FOCS, pages 258--267, 2004.]]
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. J. Shi and M. Littman. Abstraction methods for game theoretic poker. In Computers and Games, pages 333--345. Springer-Verlag, 2001.]]
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. R. E. Tarjan. Efficiency of a good but not linear set union algorithm. Journal of the ACM, 22(2):215--225, 1975.]]
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. S. J. Wright. Primal-Dual Interior-Point Methods. SIAM, 1997.]]

Index Terms

• Applied computing

  • Law, social and behavioral sciences

    • Economics

• Computing methodologies

  • Artificial intelligence

    • Philosophical/theoretical foundations of artificial intelligence

• Theory of computation

  • Design and analysis of algorithms