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.
gz-compressed POSTSCRIPT-file (88 kB, 13 pages).