Local Search Methods for Finding a Nash Equilibrium in Two-Player Games

The computation of a Nash equilibrium of a game is a challenging problem in artificial intelligence. This is because the computational time of the algorithms provided by the literature is, in the worst case, exponential in the size of the game. In this paper, we present, to the best of our knowledge, the first anytime algorithm based on the combination of support enumeration methods and local search techniques to find a Nash equilibrium in two-player general-sum games. The algorithm searches for a Nash equilibrium and, if it is stopped before it has found an equilibrium, it returns the best approximate equilibrium found so far. We design some dimensions for our algorithm and we experimentally evaluate them. Our algorithm solves with high probability games that are unsolvable with the algorithms known in the literature within a reasonable time and provides good anytime performance.