Searching One Pure-Strategy Nash Equilibrium Using a Distributed Computation Approach

摘要

—A distributed implementation of Dang’s Fixed- Point algorithm is proposed for searching one Nash equilibrium of a finite n-person game in normal form. In this paper, the problem consists of two subproblems. One is changing the problem form to a mixed 0-1 linear programming form. This process is derived from applications of the properties of pure strategy and multilinear terms in the payoff function. The other subproblem is to solve the 0-1 linear programming generated in the former subproblem. A distributed computation network which is based on the Dang’s Fixed-Point method is built to solve this 0-1 linear programming. Numerical results show that this distributed computation network is effective to finding a pure-strategy Nash equilibrium of a finite n-person game in normal form and it can be easily extended to other NP-hard problems.