Computing sequential equilibria for two-player games

ABSTRACT

Koller, Megiddo and von Stengel showed how to efficiently compute minimax strategies for two-player extensive-form zero-sum games with imperfect information but perfect recall using linear programming and avoiding conversion to normal form. Koller and Pfeffer pointed out that the strategies obtained by the algorithm are not necessarily sequentially rational and that this deficiency is often problematic for the practical applications. We show how to remove this deficiency by modifying the linear programs constructed by Koller, Megiddo and von Stengel so that pairs of strategies forming a sequential equilibrium are computed. In particular, we show that a sequential equilibrium for a two-player zero-sum game with imperfect information but perfect recall can be found in polynomial time. In addition, the equilibrium we find is normal-form perfect. Our technique generalizes to general-sum games, yielding an algorithm for such games which is likely to be prove practical, even though it is not polynomial-time.

REFERENCES

• 1: Salman Azhar , Andrew McLennan , H J Reif, Computation of Equilibria in Noncooperative Games, Duke University, Durham, NC, 1991
• 2: Darse Billings, Neil Burch, Aaron Davidson, Robert Holte, Jonathan Schaeffer, Terence Schauenberg, and Duane Szafron. Approximating game-theoretic optimal strategies for full-scale poker. In Proceedings of the 18th International Joint Conference on Aritificial Intelligence (IJCAI-03), 2003.
• 3: A. Charnes. Optimality and degeneracy in linear programming. Econometrica, 20:160--170, 1952.
• 4: V. Chvátal. Linear Programming. W. H. Freeman, 1983.
• 5: Vincent Conitzer and Tuomas Sandholm. Complexity results about Nash equilibria. In Proceedings of the 18th International Joint Conference on Aritificial Intelligence (IJCAI-03); pages 765--771, Acalpulco, Mexico, 2003.
• 6: G. B. Dantzig, A. Orden, and P. Wolfe. The generalized simplex method for minimizing a linear form under linear inequality restraints. Pacific Journal of Mathematics, 5:183--195, 1955.
• 7: B. Curtis Eaves. The linear complementarity problem. Management Science, 17(9):612--634, 1971.
• 8: Andrew Gilpin and Tuomas Sandholm. Finding equilibria in large sequential games of imperfect information. Technical Report CMU-CS-05-158, Carnegie Mellon University, Pittsburgh, PA, 2005.
• 9: J. Harsanyi and R. Selten. A General Theory of Equilibrium Selection in Games. MIT Press, 1988.
• 10: David S. Johnson , Christos H. Papadimtriou , Mihalis Yannakakis, How easy is local search?, Journal of Computer and System Sciences, v.37 n.1, p.79-100, August 1988 [doi>10.1016/0022-0000(88)90046-3]
• 11: N. Karmarkar, A new polynomial-time algorithm for linear programming, Combinatorica, v.4 n.4, p.373-395, Dec. 1984 [doi>10.1007/BF02579150]
• 12: L. G. Khachiyan. A polynomial algorithm in linear programming. Soviet Mathematics Doklady, 20:191--194, 1979.
• 13: Elon Kohlberg and Philip J. Reny. Independence on relative probability spaces and consistent assessments in game trees. Journal of Economic Theory, 75(2):280--313, 1997.
• 14: Daphne Koller and Nimrod Megiddo. The complexity of two-person zero-sum games in extensive form. Games and Economic Behavior, 4:528--552, 1992.
• 15: Daphne Koller , Nimrod Megiddo , Bernhard von Stengel, Fast algorithms for finding randomized strategies in game trees, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.750-759, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195451]
• 16: Daphne Koller, Nimrod Megiddo, and Bernhard von Stengel. Efficient computation of equilibria for extensive form games. Games and Economic Behavior, 14:247--259, 1996.
• 17: 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]
• 18: David M. Kreps and Robert Wilson. Sequential equilibria. Econometrica, 50(4):863--894, July 1982.
• 19: H. W. Kuhn. A simplified two-person poker. In H. W. Kuhn and A. W. Tucker, editors, Contributions to the theory of games I, volume 24 of Annals of Mathematical Studies. 1950.
• 20: Richard McKelvey and Andrew McLennan. Computation of equilibria in finite games. In J. Rust H. Amman, D. Kendrick, editor, Handbook of Computational Economics, pages 87--142. Elsevier, 1996.
• 21: Richard McKelvey and Tom Palfrey. Quantal response equilibria for extensive form games. Experimental Economics, 1:9--41, 1998.
• 22: Richard D. McKelvey, Andrew M. McLennan, and Theodore L. Turocy. Gambit: Software tools for game theory, version 0.97.0.7. http://econweb.tamu.edu/gambit, 2004.
• 23: Andrew McLennan and Rabee Tourky. From imitation games to Kakutani. Manuscript, 2005.
• 24: Jean-Francois Mertens. Two examples of strategic equilibrium. Games and Economic Behavior, 8:378--388, 1995.
• 25: Peter Bro Miltersen and Troels Bjerre Sørensen. Finding proper equilibria in matrix games efficiently. Manuscript, available at http://www.daimi.au.dk/~bromille/Papers/, 2005.
• 26: R. B. Myerson. Refinements of the Nash equilibrium concept. International Journal of Game Theory, 15:133--154, 1978.
• 27: J. F. Nash. Equilibrium points in n-person games. Proc. Nat. Acad. Sci. U.S.A., 36:48--49, 1950.
• 28: C. H. Papadimitriou. On graph-theoretic lemmata and complexity classes. In Proceedings of the 31st Annual Symposium on Foundations of Computer Science, pages 794--801, St. Louis, MS, October 1990. IEEE Computer Society Press.
• 29: I. V. Romanovskii. Reduction of a game with complete memory to a matrix game. Soviet Mathematics, 3:678--681, 1962.
• 30: 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]
• 31: Alex Selby. Optimal heads-up preflop holdem. Webpage, http://www.archduke.demon.co.uk/ simplex/index.html.
• 32: Reinhard Selten. A reexamination of the perfectness concept for equilibrium points in extensive games. International Journal of Game Theory, 4:25--55, 1975.
• 33: Theodore L. Turocy. Personal communication.
• 34: Eric van Damme. A relation between perfect equilibria in extensive form games and proper equilibria in normal form games. International Journal of Game Theory, 13:1--13, 1984.
• 35: Eric van Damme, Stability and perfection of Nash equilibria, Springer-Verlag, London, 1987
• 36: J. von Neumann and O. Morgenstern. Theory of games and economic behaviour. Princeton University Press, Princeton, 1953. 3rd edition.
• 37: B. von Stengel. LP representation and efficient computation of behavior strategies. Technical Report S-9301, University of the Federal Armed Forces at Munich, 1993.
• 38: B. von Stengel. Efficient computation of behavior strategies. Games and Economic Behavior, 14:220--246, 1996.
• 39: B. von Stengel. Computing equilibria for two-person games. In R. J. Aumann and S. Hart, editors, Handbook of Game Theory with Economic Applications, volume 3, chapter 45. North-Holland, 2002.
• 40: B. von Stengel, A. van den Elzen, and A. J. J. Talman. Computing normal form perfect equilibria for extensive two-person games. Econometrica, 70:693--715, 2002.
• 41: Robert B. Wilson. Computing simply stable equilibria. Econometrica, 60(5):1039--1070, 1992.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.2 Approximation
          Subjects: Minimax approximation and algorithms

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Linear programming

General Terms:
Algorithms, Theory