@inproceedings{63c5da5423b84f8a90d303de7628bc2d,

title = "Rank-1 bimatrix games: A homeomorphism and a polynomial time algorithm",

abstract = "Given a rank-1 bimatrix game (A,B), i.e., where rank(A+B)=1, we construct a suitable linear subspace of the rank-1 game space and show that this subspace is homeomorphic to its Nash equilibrium correspondence. Using this homeomorphism, we give the first polynomial time algorithm for computing an exact Nash equilibrium of a rank-1 bimatrix game. This settles an open question posed by Kannan and Theobald (SODA'07). In addition, we give a novel algorithm to enumerate all the Nash equilibria of a rank-1 game and show that a similar technique may also be applied for finding a Nash equilibrium of any bimatrix game. Our approach also provides new proofs of important classical results such as the existence and oddness of Nash equilibria, and the index theorem for bimatrix games. Further, we extend the rank-1 homeomorphism result to a fixed rank game space, and give a fixed point formulation on [0,1]k for solving a rank-k game. The homeomorphism and the fixed point formulation are piece-wise linear and considerably simpler than the classical constructions.",

keywords = "homeomorphism, nash equilibrium, rank-1 games",

author = "Bharat Adsul and Jugal Garg and Ruta Mehta and Milind Sohoni",

year = "2011",

doi = "10.1145/1993636.1993664",

language = "English (US)",

isbn = "9781450306911",

series = "Proceedings of the Annual ACM Symposium on Theory of Computing",

publisher = "Association for Computing Machinery",

pages = "195--204",

booktitle = "STOC'11 - Proceedings of the 43rd ACM Symposium on Theory of Computing",

address = "United States",

note = "43rd ACM Symposium on Theory of Computing, STOC 2011 ; Conference date: 06-06-2011 Through 08-06-2011",

}