Finding the Pure-Strategy Nash Equilibrium Using a Fixed-Point Algorithm

摘要

It is well known that determining whether a finite game has a pure-strategy Nash equilibrium is an NP-hard problem and it is an active research topic to find a Nash equilibrium recently. In this paper, an implementation of Dang's Fixed-Point iterative method is introduced to find a pure-strategy Nash equilibrium of a finite n-person game in normal form. There are two steps to find one pure-strategy Nash equilibrium in this paper. The first step is converting the problem to a mixed 0-1 linear programming formulation based on the properties of pure strategy and multilinear terms in the payoff function. In the next step, the Dang's method is used to solve the formulation generated in the former step. Numerical results show that this method is effective to find a pure-strategy Nash equilibrium of a finite n-person game in normal form.