A mixed 0-1 linear programming approach to the computation of all pure-strategy nash equilibria of a finite n -person game in normal form

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journal

7 Scopus Citations
View graph of relations

Author(s)

Detail(s)

Original languageEnglish
Article number640960
Journal / PublicationMathematical Problems in Engineering
Volume2014
Publication statusPublished - 2014

Link(s)

Abstract

A main concern in applications of game theory is how to effectively select a Nash equilibrium, especially a pure-strategy Nash equilibrium for a finite n -person game in normal form. This selection process often requires the computation of all Nash equilibria. It is well known that determining whether a finite game has a pure-strategy Nash equilibrium is an NP-hard problem and it is difficult to solve by naive enumeration algorithms. By exploiting the properties of pure strategy and multilinear terms in the payoff functions, this paper formulates a new mixed 0-1 linear program for computing all pure-strategy Nash equilibria. To our knowledge, it is the first method to formulate a mixed 0-1 linear programming for pure-strategy Nash equilibria and it may work well for similar problems. Numerical results show that the approach is effective and this method can be easily distributed in a distributed way. © 2014 Zhengtian Wu et al.

Research Area(s)

Citation Format(s)

A mixed 0-1 linear programming approach to the computation of all pure-strategy nash equilibria of a finite n -person game in normal form. / Wu, Zhengtian; Dang, Chuangyin; Karimi, Hamid Reza; Zhu, Changan; Gao, Qing.

In: Mathematical Problems in Engineering, Vol. 2014, 640960, 2014.

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journal

Download Statistics

No data available