Using computer algebra to find nash equilibria

ABSTRACT

A central concern of game theory is the computation of Nash equilibria. These are characterized by systems of polynomial equations and inequalities. We survey the use of currently available software to solve these systems, and conclude that polyhedral homotopy continuation appears to scale best with increasing problem size.

REFERENCES

• 1: D. N. Bernstein. The number of roots of a system of equations. Functional Analysis and Applications, 9(2):183--185, 1975.
• 2: Ruchira S. Datta, Universality of Nash Equilibria, Mathematics of Operations Research, v.28 n.3, p.424-432, July 2003 [doi>10.1287/moor.28.3.424.16397]
• 3: Ioannis Zacharias Emiris, Sparse elimination and applications in kinematics, University of California at Berkeley, Berkeley, CA, 1994
• 4: Ioannis Z. Emiris , John F. Canny, Efficient incremental algorithms for the sparse resultant and the mixed volume, Journal of Symbolic Computation, v.20 n.2, p.117-149, Aug. 1995 [doi>10.1006/jsco.1995.1041]
• 5: Jean Charles Faugère, A new efficient algorithm for computing Gröbner bases without reduction to zero (F₅), Proceedings of the 2002 international symposium on Symbolic and algebraic computation, p.75-83, July 07-10, 2002, Lille, France [doi>10.1145/780506.780516]
• 6: H. Gintis. Game Theory Evolving. Princeton University Press, 2000.
• 7: D. R. Grayson and M. E. Stillman. Macaulay 2, a software system for research in algebraic geometry. Available at http://www.math.uiuc.edu/Macaulay2/.
• 8: G.-M. Greuel, G. Pfister, and H. Schönemann. Singular 2.0. A Computer Algebra System for Polynomial Computations, Centre for Computer Algebra, University of Kaiserslautern, 2001. http://www.singular.uni-kl.de.
• 9: T. Gunji, S. Kim, M. Kojima, A. Takeda, K. Fujisawa, and T. Mizutani. PHoM---a polyhedral homotopy continuation method for polynomial systems. Research Report B-386, Tokyo Institute of Technology, Tokyo, January 2003. http://www.is.titech.ac.jp/˜kojima/PHoM/.
• 10: J. Harsanyi. Oddness of the number of equilibrium points: a new proof. International Journal of Game Theory, 2:235--250, 1973.
• 11: Birkett Huber , Bernd Sturmfels, A polyhedral method for solving sparse polynomial systems, Mathematics of Computation, v.64 n.212, p.1541-1555, Oct. 1995 [doi>10.2307/2153370]
• 12: X. Leroy, J. Vouillon, and D. Doligez. Objective Caml. Available at http://caml.inria.fr.
• 13: R. McKelvey and A. McLennan. The maximal number of regular totally mixed Nash equilibria. Journal of Economic Theory, 72:411--425, 1997.
• 14: R. D. McKelvey, A. McLennan, and T. Turocy. Gambit: Software tools for game theory. Available at http://www.hss.caltech.edu/gambit/.
• 15: Antonio Montes, A new algorithm for discussing Gröbner bases with parameters, Journal of Symbolic Computation, v.33 n.2, p.183-208, February 2002 [doi>10.1006/jsco.2001.0504]
• 16: J. Nash. Equilibrium points in N-person games. Proceedings of the National Academy of Sciences of the United States of America, 36:48--49, 1950.
• 17: Eric van Damme, Stability and perfection of Nash equilibria, Springer-Verlag, London, 1987
• 18: Jan Verschelde, Algorithm 795: PHCpack: a general-purpose solver for polynomial systems by homotopy continuation, ACM Transactions on Mathematical Software (TOMS), v.25 n.2, p.251-276, June 1999 [doi>10.1145/317275.317286]
• 19: Jan Verschelde , Pierre Verlinden , Ronald Cools, Homotopies exploiting Newton polytopes for solving sparse polynomial systems, SIAM Journal on Numerical Analysis, v.31 n.3, p.915-930, June 1994 [doi>10.1137/0731049]
• 20: J. von Neumann and O. Morgenstern. Theory of Games and Economic Behavior. Princeton University Press, 1944.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.4 Applications

Additional Classification:
  J. Computer Applications
  J.4 SOCIAL AND BEHAVIORAL SCIENCES

General Terms:
Performance

Keywords:
Gröbner bases, game theory, polyhedral homotopy continuation, polynomial systems