Fast Algorithms for Rank-1 Bimatrix Games

• 成果类型: Article
• 署名作者: Adsul, Bharat; Garg, Jugal; Mehta, Ruta; Sohoni, Milind; von Stengel, Bernhard
• 署名单位: Indian Institute of Technology System (IIT System); Indian Institute of Technology (IIT) - Bombay; University of Illinois System; University of Illinois Urbana-Champaign; University of Illinois System; University of Illinois Urbana-Champaign; University of London; London School Economics & Political Science
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2020.1981
• 发表日期: 2021
• 页码: 613-631
• 关键词: bimatrix game; Nash equilibrium; rank-1 game; Polynomial-time algorithm; homeomorphism

摘要

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.