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.
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Language: | en_US |
| Published: |
2005
|
| Online Access: | http://hdl.handle.net/1721.1/30523 |
| _version_ | 1826189057787428864 |
|---|---|
| author | Abbott, Tim Kane, Daniel Valiant, Paul |
| author2 | Cryptography and Information Security |
| author_facet | Cryptography and Information Security Abbott, Tim Kane, Daniel Valiant, Paul |
| author_sort | Abbott, Tim |
| collection | MIT |
| description | 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. |
| first_indexed | 2024-09-23T08:08:51Z |
| id | mit-1721.1/30523 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T08:08:51Z |
| publishDate | 2005 |
| record_format | dspace |
| spelling | mit-1721.1/305232019-04-09T16:57:29Z Complexity of finding Nash equilibria in 0-1 bimatrix games Abbott, Tim Kane, Daniel Valiant, Paul Cryptography and Information Security 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. 2005-12-22T02:24:28Z 2005-12-22T02:24:28Z 2005-02-08 MIT-CSAIL-TR-2005-010 MIT-LCS-TM-648 http://hdl.handle.net/1721.1/30523 en_US Massachusetts Institute of Technology Computer Science and Artificial Intelligence Laboratory 6 p. 6499249 bytes 336493 bytes application/postscript application/pdf application/postscript application/pdf |
| spellingShingle | Abbott, Tim Kane, Daniel Valiant, Paul Complexity of finding Nash equilibria in 0-1 bimatrix games |
| title | Complexity of finding Nash equilibria in 0-1 bimatrix games |
| title_full | Complexity of finding Nash equilibria in 0-1 bimatrix games |
| title_fullStr | Complexity of finding Nash equilibria in 0-1 bimatrix games |
| title_full_unstemmed | Complexity of finding Nash equilibria in 0-1 bimatrix games |
| title_short | Complexity of finding Nash equilibria in 0-1 bimatrix games |
| title_sort | complexity of finding nash equilibria in 0 1 bimatrix games |
| url | http://hdl.handle.net/1721.1/30523 |
| work_keys_str_mv | AT abbotttim complexityoffindingnashequilibriain01bimatrixgames AT kanedaniel complexityoffindingnashequilibriain01bimatrixgames AT valiantpaul complexityoffindingnashequilibriain01bimatrixgames |