(Essentially) Resolving the Complexity of Constant Rank Bimatrix Games

Speaker: Ruta Mehta , Gerogia Tech

Date: Wednesday, November 06, 2013

Time: 4:00 PM to 5:00 PM Note: all times are in the Eastern Time Zone

Public: Yes

Location: 32-G575

Event Type:

Room Description:

Host: Costis Daskalakis, MIT CSAIL

Contact: Joanne Talbot Hanley, 617-253-6054, joanne@csail.mit.edu

Relevant URL:

Speaker URL: None

Speaker Photo:
None

Reminders to: seminars@csail.mit.edu, theory-seminars@csail.mit.edu, compalgsem@lists.csail.mit.edu

Reminder Subject: 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.

Research Areas:

Impact Areas:

See other events that are part of the Algorithms and Complexity Series Fall 2013 / Spring 2014.

Created by Joanne Talbot Hanley Email at Wednesday, October 30, 2013 at 10:30 AM.