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. |
Year | DOI | Venue |
---|---|---|
2018 | 10.1287/opre.2020.1981 | OPERATIONS RESEARCH |
Keywords | DocType | Volume |
bimatrix game, Nash equilibrium, rank-1 game, polynomial-time algorithm, homeomorphism | Journal | 69 |
Issue | ISSN | Citations |
2 | 0030-364X | 0 |
PageRank | References | Authors |
0.34 | 2 | 5 |
Name | Order | Citations | PageRank |
---|---|---|---|
Bharat Adsul | 1 | 37 | 7.62 |
Jugal Garg | 2 | 85 | 18.43 |
Ruta Mehta | 3 | 104 | 23.11 |
Milind A. Sohoni | 4 | 108 | 14.50 |
Bernhard von Stengel | 5 | 275 | 38.51 |