Complementarity Enhanced Nash's Mappings and Differentiable Homotopy Methods to Select Perfect Equilibria

To extend the concept of subgame perfect equilibrium to an extensive-form game with imperfect information but perfect recall, Selten (Int J Game Theory 4:25-55, 1975) formulated the notion of perfect equilibrium and attained its existence through the agent normal-form representation of the extensive-form game. As a strict refinement of Nash equilibrium, a perfect equilibrium always yields a sequential equilibrium. The selection of a perfect equilibrium thus plays an essential role in the applications of game theory. Moreover, a different procedure may select a different perfect equilibrium. The existence of Nash equilibrium was proved by Nash (Ann Math 54:289-295, 1951) through the construction of an elegant continuous mapping and an application of Brouwer's fixed point theorem. This paper intends to enhance Nash's mapping to select a perfect equilibrium. By incorporating the complementarity condition into the equilibrium system with Nash's mapping through an artificial game, we successfully eliminate the nonnegativity constraints on a mixed strategy profile imposed by Nash's mapping. In the artificial game, each player solves against a given mixed strategy profile a strictly convex quadratic optimization problem. This enhancement enables us to derive differentiable homotopy systems from Nash's mapping and establish the existence of smooth paths for selecting a perfect equilibrium. The homotopy methods start from an arbitrary totally mixed strategy profile and numerically trace the smooth paths to a perfect equilibrium. Numerical results show that the methods are numerically stable and computationally efficient in search of a perfect equilibrium and outperform the existing differentiable homotopy method.

Automated summary

The paper introduces the application of perfect equilibrium in extensive-form games and proposes a method to enhance Nash's mapping for selecting a perfect equilibrium through an artificial game.