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
Joint Authors
Zhu, Changan
Wu, Zhengtian
Dang, Chuangyin
Gao, Qing
Karimi, Hamid Reza
Source
Mathematical Problems in Engineering
Issue
Vol. 2014, Issue 2014 (31 Dec. 2014), pp.1-8, 8 p.
Publisher
Hindawi Publishing Corporation
Publication Date
2014-04-08
Country of Publication
Egypt
No. of Pages
8
Main Subjects
Abstract EN
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.
American Psychological Association (APA)
Wu, Zhengtian& Dang, Chuangyin& Karimi, Hamid Reza& Zhu, Changan& Gao, Qing. 2014. 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. Mathematical Problems in Engineering،Vol. 2014, no. 2014, pp.1-8.
https://search.emarefa.net/detail/BIM-487478
Modern Language Association (MLA)
Wu, Zhengtian…[et al.]. 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. Mathematical Problems in Engineering No. 2014 (2014), pp.1-8.
https://search.emarefa.net/detail/BIM-487478
American Medical Association (AMA)
Wu, Zhengtian& Dang, Chuangyin& Karimi, Hamid Reza& Zhu, Changan& Gao, Qing. 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. Mathematical Problems in Engineering. 2014. Vol. 2014, no. 2014, pp.1-8.
https://search.emarefa.net/detail/BIM-487478
Data Type
Journal Articles
Language
English
Notes
Includes bibliographical references
Record ID
BIM-487478