¹Department of Precision Machinery and Precision Instrumentation, University of Science and Technology of China, Hefei, China
²Department of Systems Engineering and Engineering Management, City University of Hong Kong, Kowloon, Hong Kong

---

Abstract—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.

Index Terms—Finite Game, Nash Equilibrium, Mixed 0- 1 Linear Programming, Fixed-Point Method, Distributed Implementation

[PDF]

Cite: Zhengtian Wu, Chuangyin Dang, and Changan Zhu, "Searching One Pure-Strategy Nash Equilibrium Using a Distributed Computation Approach," Journal of Computers vol. 9, no. 4, pp. 859-866, 2014.