Fast Algorithms for Rank-1 Bimatrix Games

Bharat Adsul (), Jugal Garg (), Ruta Mehta (), Milind Sohoni and Bernhard von Stengel
Additional contact information
Bharat Adsul: Department of Computer Science and Engineering, Indian Institute of Technology Bombay, Powai, Mumbai 400 076, India;
Jugal Garg: Department of Industrial and Enterprise Systems Engineering, University of Illinois at Urbana–Champaign, Urbana, Illinois 61801;
Ruta Mehta: Department of Computer Science, University of Illinois at Urbana–Champaign, Urbana, Illinois 61801;

Operations Research, 2021, vol. 69, issue 2, 613-631

Abstract: 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.

Keywords: bimatrix game; Nash equilibrium; rank-1 game; polynomial-time algorithm; homeomorphism (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://doi.org/10.1287/opre.2020.1981 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:69:y:2021:i:2:p:613-631

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().