(Essentially) Resolving the Complexity of Constant Rank Bimatrix Games
, Gerogia Tech
Date: Wednesday, November 06, 2013
Time: 4:00 PM to 5:00 PM Note: all times are in the Eastern Time Zone
Host: Costis Daskalakis, MIT CSAIL
Contact: Joanne Talbot Hanley, 617-253-6054, firstname.lastname@example.org
Speaker URL: None
email@example.com, firstname.lastname@example.org, email@example.com
TALK: Algorithms and Complexity Special Seminar: Ruta Mehta "(Essentially) Resolving the Complexity of Constant Rank Bimatrix Games"
The rank of a bimatrix game (A, B) is defined as the rank of (A+B). For zero-sum games, i.e., rank-0, von Neumann (1928) showed that Nash equilibrium are min-max strategies, which is equivalent to the linear programming duality. 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 equilibria of (A, B) as the fixed points of a single variable function which can be found in polynomial time via an easy binary search.
The next immediate question to consider is rank-2 games, or in general constant rank games, for which an FPTAS is already known due to Kannan and Theobald (2005). We show that constant rank games are PPAD-hard in general by reducing 2D-Brouwer to rank-3 bimatrix games. This is the first time that a problem with an FPTAS turns out to be PPAD-hard. Our reduction gives a simpler proof of PPAD-hardness for bimatrix games. This leaves the status of only rank-2 games unresolved.
The first part of the talk is based on a joint work with Bharat Adsul, Jugal Garg and Milind Sohoni.
Created by Joanne Talbot Hanley at Wednesday, October 30, 2013 at 10:30 AM.