Efficient computation of equilibria for extensive two-person games

Abstract:
The Nash equilibria of a two-person, non-zero-sum game are the solutions of a certain linear complementarity problem (LCP). In order to use this for solving a game in extensive form, the game must first be converted to a strategic description such as the normal form. The classical normal form, however, is often exponentially large in the size of the game tree. If the game has perfect recall, a linear-sized strategic description is the sequence form. For the resulting small LCP, we show that an equilibrium is found efficiently by Lemke's algorithm, a generalization of the Lemke-Howson method.

Keywords:
Equilibrium, extensive game, Lemke-Howson algorithm, linear complementarity, sequence form.

In:
Games and Economic Behavior 14 (1996), 247-259.

PDF-file (135 kB, 13 pages).

gz-compressed POSTSCRIPT-file (88 kB, 13 pages).

Related work:

• B. von Stengel (1996), Efficient computation of behavior strategies. Games and Economic Behavior 14, 220-246.

• D. Koller, N. Megiddo, and B. von Stengel (1994), Fast algorithms for finding randomized strategies in game trees. Proceedings of the 26th ACM Symposium on Theory of Computing, 750-759.

Back to Bernhard von Stengel's list of publications