Andrew McLennan

Polyhedral Homotopy Computation of
Extensive Form Nash Equilibrium Paths

Abstract:

When the payoffs of an extensive game lie in a generic
set, a particular version of the equations characterizing
totally mixed behavioral Nash equilibrium satisfies the
prerequisites of polyhedral homotopy algorithms.
Application of these algorithms yields an algorithm for
computing all totally mixed behavioral Nash equilibria.
We discuss the application of these algorithms to the
computation of all behavioral Nash equilibrium paths.
We also obtain combinatoric necessary and sufficient
conditions for the existence of payoffs supporting a
regular equilibrium.