Fast algorithms for rank-1 bimatrix games

Bharat Adsul, Jugal Garg, Ruta Mehta, Milind Sohoni, Bernhard Von Stengel

Research output: Contribution to journalArticlepeer-review


The rank of a bimatrix game is the matrix rank of the sum of the two payoff matrices. This paper comprehensively analyzes games of rank one and shows the following: (1) For a game of rank r, the set of its Nash equilibria is the intersection of a generically one-dimensional set of equilibria of parameterized games of rank r - 1 with a hyperplane. (2) One equilibrium of a rank-1 game can be found in polynomial time. (3) All equilibria of a rank-1 game can be found by following a piecewise linear path. In contrast, such a path-following method finds only one equilibrium of a bimatrix game. (4) The number of equilibria of a rank-1 game may be exponential. (5) There is a homeomorphism between the space of bimatrix games and their equilibrium correspondence that preserves rank. It is a variation of the homeomorphism used for the concept of strategic stability of an equilibrium component.

Original languageEnglish (US)
Pages (from-to)613-631
Number of pages19
JournalOperations Research
Issue number2
StatePublished - Mar 1 2021


  • Bimatrix game
  • Homeomorphism
  • Nash equilibrium
  • Polynomial-time algorithm
  • Rank-1 game

ASJC Scopus subject areas

  • Computer Science Applications
  • Management Science and Operations Research


Dive into the research topics of 'Fast algorithms for rank-1 bimatrix games'. Together they form a unique fingerprint.

Cite this