Complexity of finding Nash equilibria in 0-1 bimatrix games

Author(s)
Abbott, Tim; Kane, Daniel; Valiant, Paul
Thumbnail
DownloadMIT-CSAIL-TR-2005-010.ps (6346.Kb)
Additional downloads
Other Contributors
Cryptography and Information Security
Metadata
Show full item record
Abstract
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.
Date issued
2005-02-08
URI
http://hdl.handle.net/1721.1/30523
Other identifiers
MIT-CSAIL-TR-2005-010
MIT-LCS-TM-648
Series/Report no.
Massachusetts Institute of Technology Computer Science and Artificial Intelligence Laboratory
Collections