ACO/Theory Seminar: A Polynomial Time Algorithm for Rank-1 Bimatrix Games (Despite Disconnected Solutions)

Other Talks
Wednesday, April 24, 2013 - 3:00pm for 1 hour (actually 50 minutes)
Klaus 1456
Ruta Mehta – Indian Institute of Technology, Bombay
Robin Thomas
The rank of a bimatrix game (A, B) is defined as the rank of (A+B). For zero-sum games, i.e., rank 0, Nash equilibrium computation reduces to solving a linear program. We solve the open question of Kannan and Theobald (2005) of designing an efficient algorithm for rank-1 games. The main difficulty is that the set of equilibria can be disconnected. We circumvent this by moving to a space of rank-1 games which contains our game (A, B), and defining a quadratic program whose optimal solutions are Nash equilibria of all games in this space. We then isolate the Nash equilibrium of (A, B) as the fixed point of a single variable function which can be found in polynomial time via an easy binary search. Based on a joint work with Bharat Adsul, Jugal Garg and Milind Sohoni.