A Multi-Modal Coevolutionary Algorithm for Finding All Nash Equilibria of a Multi-Player Normal Form Game

摘要

Nash's theorem says that every game that has a finite strategic form has at least one Nash point. The problem of finding one Nash point is a well studied problem, and there exist a number of different methods for numerically computing a sample Nash equilibrium. But the problem of finding all equilibria has been addressed only recently. Literature review shows that many of the existing methods for detecting all equilibria are computationally intensive and error prone. In this paper we present a multi-modal coevolutionary algorithm that is able to detect all Nash points of a multi-player normal form game at the same time. We formulate the problem of solving a matrix game as a multi- modal optimization problem. Then a coevolutionary algorithm decomposes the problem and solves it in a parallel form. It associates one population to each player's strategies. So various components of the problem will coevolve and better results may be produced at lower computational costs.