Computing equilibria for two-person games

Bernhard von Stengel

This paper is a self-contained survey of algorithms for computing Nash equilibria of two-person games given in normal form or extensive form. The classical Lemke--Howson algorithm for finding one equilibrium of a bimatrix game is presented graph-theoretically as well as algebraically in terms of complementary pivoting. Common definitions of degenerate games are shown as equivalent. Enumeration of all equilibria is presented as a polytope problem. Algorithms for computing simply stable equilibria and perfect equilibria are explained. For games in extensive form, the reduced normal form may be exponentially large. If the players have perfect recall, the sequence form grows linearly with the size of the game tree and can be used instead of the normal form. Theoretical and practical computational issues of these approaches are mentioned.

Handbook of Game Theory, Vol. 3, eds. R. J. Aumann and S. Hart, North-Holland, Amsterdam (2002), Chapter 45, pages 1723-1759.

PDF-file (187 kB, 38 pages)

gz-compressed POSTSCRIPT-file (175 kB, 40 pages)

Earlier version:

B. von Stengel (1996), Computing Equilibria for Two-Person Games. Technical Report 253, Department of Computer Science, ETH Zurich. gz-compressed POSTSCRIPT-file (217 kB, 62 pages).

BvSBack to Bernhard von Stengel's list of publications