Finding a Nash Equilibrium in Noncooperative N-Person Games by Solving a Sequenceof Linear Stationary Point Problems

摘要

The paper presents an algorithm for finding a Nash equilibrium in anoncooperative normal form N-person game. More generally, the algorithm can be applied for solving a nonlinear stationary point problem on a simplotope, being the Cartesian product of several simplices. The algorithm solves the problem by solving a sequence of linear stationary point problems. Each problem in the sequence is solved in a finite number of iterations. Although the overall convergence cannot be proved, the method performs rather well. Computational results suggest that the algorithm performs at least as good as simplicial algorithms do. For the special case of a bi-matrix game (N = 2), the algorithm has an appealing game-theoretic interpretation. In that case, the problem is linear and the algorithm always finds a solution. Furthermore, the equilibrium found in a bimatrix game is perfect whenever the algorithm starts from a strategy vector at which all actions are played with positive probability.