Rank-1 bimatrix games: A homeomorphism and a polynomial time algorithm

Bharat Adsul, Jugal Garg, Ruta Mehta, Milind Sohoni

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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.

Original languageEnglish (US)
Title of host publicationSTOC'11 - Proceedings of the 43rd ACM Symposium on Theory of Computing
PublisherAssociation for Computing Machinery
Number of pages10
ISBN (Print)9781450306911
StatePublished - 2011
Externally publishedYes
Event43rd ACM Symposium on Theory of Computing, STOC 2011 - San Jose, United States
Duration: Jun 6 2011Jun 8 2011

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
ISSN (Print)0737-8017


Conference43rd ACM Symposium on Theory of Computing, STOC 2011
Country/TerritoryUnited States
CitySan Jose


  • homeomorphism
  • nash equilibrium
  • rank-1 games

ASJC Scopus subject areas

  • Software


Dive into the research topics of 'Rank-1 bimatrix games: A homeomorphism and a polynomial time algorithm'. Together they form a unique fingerprint.

Cite this