6533b823fe1ef96bd127fd51

RESEARCH PRODUCT

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

Zhengtian WuChuangyin DangHamid Reza KarimiChangan ZhuQing Gao

subject

TheoryofComputation_MISCELLANEOUSComputer Science::Computer Science and Game TheoryEngineering (all)Article Subjectlcsh:TA1-2040lcsh:MathematicsVDP::Technology: 500::Mechanical engineering: 570Mathematics (all)TheoryofComputation_GENERALVDP::Technology: 500::Information and communication technology: 550lcsh:Engineering (General). Civil engineering (General)lcsh:QA1-939Mathematics (all); Engineering (all)

description

Published version of an article in the journal: Mathematical Problems in Engineering. Also available from the publisher at: http://dx.doi.org/10.1155/2014/640960 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.

yearjournalcountryeditionlanguage
2014-01-01
10.1155/2014/640960http://hdl.handle.net/11250/279492