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 Wu, Chuangyin Dang, Hamid Reza Karimi, Changan Zhu and Qing Gao

Mathematical Problems in Engineering, 2014, vol. 2014, 1-8

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

Date: 2014
References: Add references at CitEc
Citations:

Downloads: (external link)
http://downloads.hindawi.com/journals/MPE/2014/640960.pdf (application/pdf)
http://downloads.hindawi.com/journals/MPE/2014/640960.xml (text/xml)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:hin:jnlmpe:640960

DOI: 10.1155/2014/640960

Access Statistics for this article

More articles in Mathematical Problems in Engineering from Hindawi
Bibliographic data for series maintained by Mohamed Abdelhakeem ().