A Globally Convergent Algorithm to Compute All Nash Equilibria of n-Person Games

In this paper an algorithm is presented to compute all Nash equilibria for games in normal form on the only premises that the number of Nash equilibria is finite. The algorithm relies on decomposing the game by means of support-sets. For each support-set, the set of totally mixed equilibria of the support-restricted game that results by restricting the players to strategies in the support-set can be characterized by a system of polynomial equations and inequalities. By solving those systems for each support-set, all equilibria are found. The algorithm belongs to the class of homotopy-methods and is implementable. Finally, several techniques to speed up computations are proposed.