Talks & Seminars
Title: Rank-1 Two-player Games: A Homeomorphism and a Polynomial Time Algorithm
Ms. Ruta Mehta, Department of Computer Science & Engg., IIT Bombay
Date & Time: February 9, 2011 17:00
Venue: Lecture Hall, B Block, Third floor, Kanwal Rekhi Building
Analysis and computation of Nash equilibrium for finite two player (bimatrix) games is a central problem in non-cooperative game theory. Homotopy of Nash equilibrium turns out to be useful to address these problems. 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. arXiv:1010.3083, Accepted at STOC'11)
Speaker Profile:
List of Talks


Faculty CSE IT
Forgot Password
    [+] Sitemap     Feedback