Local search techniques for computing equilibria in two-player general-sum strategic-form games

The computation of a Nash equilibrium in a game is a chal-lenging problem in artificial intelligence. This is because the computational time of the algorithms provided by the litera-ture is, in the worst case, exponential in the size of the game. To deal with this problem, it is common the resort to con-cepts of approximate equilibrium. In this paper, we follow a different route, presenting, to the best of our knowledge, the first algorithm based on the combination of support enumer-ation methods and local search techniques to find an exact Nash equilibrium in two-player general-sum games and, in the case no equilibrium is found within a given deadline, to provide an approximate equilibrium. We design some di-mensions for our algorithm and we experimentally evaluate them with games that are unsolvable with the algorithms known in the literature within a reasonable time. Our pre-liminary results are promising, showing that our techniques can allow one to solve hard games in a short time. Categories and Subject Descriptor