TRACING EQUILIBRIA IN EXTENSIVE GAMES BY COMPLEMENTARY PIVOTING

by Bernhard von Stengel, Antoon van den Elzen, and Dolf Talman

ABSTRACT:
An algorithm is presented for computing an equilibrium
of an extensive two-person game with perfect recall.
The equilibrium is traced on a piecewise linear path
from an arbitrary starting point.  If this is a pair of completely
mixed strategies, then the equilibrium is normal form perfect.
The normal form computation is performed efficiently using the
sequence form, which has the same size as the extensive game itself.

Discussion paper No. 9686, Tilburg University, September 1996, 30 pages.