Georgia Institute of Technology College of Sciences

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.