Complexity of finding Nash equilibria in 0-1 bimatrix games

We exhibit a polynomial reduction from the problem of finding a Nashequilibrium of a bimatrix game with rational coefficients to the problemof finding a Nash equilibrium of a bimatrix game with 0-1 coefficients.

Bibliographic Details
Main Authors: Abbott, Tim, Kane, Daniel, Valiant, Paul
Other Authors: Cryptography and Information Security
Language:en_US
Published: 2005
Online Access:http://hdl.handle.net/1721.1/30523