BEGIN:VCALENDAR
VERSION:2.0
PRODID:icalendar-ruby
CALSCALE:GREGORIAN
METHOD:PUBLISH
BEGIN:VTIMEZONE
TZID:America/New_York
BEGIN:DAYLIGHT
DTSTART:20140309T030000
TZOFFSETFROM:-0500
TZOFFSETTO:-0400
RRULE:FREQ=YEARLY;BYDAY=2SU;BYMONTH=3
TZNAME:EDT
END:DAYLIGHT
BEGIN:STANDARD
DTSTART:20131103T010000
TZOFFSETFROM:-0400
TZOFFSETTO:-0500
RRULE:FREQ=YEARLY;BYDAY=1SU;BYMONTH=11
TZNAME:EST
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTAMP:20220128T183654Z
UID:46f93882-86a7-44ab-bec1-2a9374626ce2
DTSTART;TZID=America/New_York:20131106T160000
DTEND;TZID=America/New_York:20131106T170000
CREATED:20131030T103056
DESCRIPTION: \n\nThe 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 Theob
ald (2005) of designing an efficient algorithm for rank-1 games. The main
difficulty is that the set of equilibria can be disconnected. We circumven
t 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 equi
libria 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 fou
nd in polynomial time via an easy binary search.\n\nThe next immediate que
stion to consider is rank-2 games\, or in general constant rank games\, fo
r which an FPTAS is already known due to Kannan and Theobald (2005). We sh
ow that constant rank games are PPAD-hard in general by reducing 2D-Brouwe
r 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 PP
AD-hardness for bimatrix games. This leaves the status of only rank-2 game
s unresolved.\n\nThe first part of the talk is based on a joint work with
Bharat Adsul\, Jugal Garg and Milind Sohoni.\n
LAST-MODIFIED:20131104T095818
LOCATION:32-G575
SUMMARY:(Essentially) Resolving the Complexity of Constant Rank Bimatrix Ga
mes
URL:https://calendar.csail.mit.edu/events/117073
END:VEVENT
END:VCALENDAR