Title : Rank-1 Two-player Games: A Homeomorphism and a Polynomial Time Algorithm.
Speaker : Ruta Mehta, Computer Science and Engineering, IIT Bombay
Time : 3:30pm, Friday February 4, 2011
Venue : Room 217, Mechanical Engineering
Abstract
Given a rank-1 Two-player (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 2007) and Theobald (2007). 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. This technique also proves the existence, oddness and the index theorem of Nash equilibria in a bimatrix game. 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. (Joint work with Bharat Adsul, Jugal Garg, and Milind Sohoni.)