BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//talks.cam.ac.uk//v3//EN
BEGIN:VTIMEZONE
TZID:Europe/London
BEGIN:DAYLIGHT
TZOFFSETFROM:+0000
TZOFFSETTO:+0100
TZNAME:BST
DTSTART:19700329T010000
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=-1SU
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0100
TZOFFSETTO:+0000
TZNAME:GMT
DTSTART:19701025T020000
RRULE:FREQ=YEARLY;BYMONTH=10;BYDAY=-1SU
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
CATEGORIES:Optimization and Incentives Seminar
SUMMARY:Exponential Lower Bounds for Solving Infinitary Pa
yoff Games and Linear Programs - Oliver Friedmann
(LMU Munich)
DTSTART;TZID=Europe/London:20120507T150000
DTEND;TZID=Europe/London:20120507T160000
UID:TALK37305AThttp://talks.cam.ac.uk
URL:http://talks.cam.ac.uk/talk/index/37305
DESCRIPTION:Policy iteration is one of the most important algo
rithmic schemes for solving infinitary payoff game
s such as parity games\, stochastic games and Mark
ov decision processes\, and many more. It is param
eterized by an improvement rule that determines ho
w to proceed in the iteration from one policy to t
he next. It is a major open problem whether there
is an improvement rule that results in a polynomia
l time algorithm for solving\none of the considere
d (two-player) game classes.\nSimplex algorithms f
or solving linear programs are closely related to
policy iteration algorithms. Like policy iteration
\, the simplex algorithm is\nparameterized by a so
-called pivoting rule that describes how to procee
d from one basic feasible solution in the linear p
rogram to the next. Also\,\nit is a major open pro
blem whether there is a pivoting rule that results
in a (strongly) polynomial time algorithm for sol
ving linear programs. We describe our recent const
ructions for parity games that give rise to\nexpon
ential lower bounds for several improvement rules\
, and how to extend the lower bound to more expres
sive game classes like stochastic games. We show t
hat our construction for parity games can be trans
lated to Markov decision processes\, transferring
our lower bound to their domain\, and finally show
how the lower bounds for the MDPs can be transfer
red to the linear programming domain\, solving pro
blems that have been open for several decades.
LOCATION:MR12\, Centre for Mathematical Sciences\, Wilberfo
rce Road\, Cambridge
CONTACT:Felix Fischer
END:VEVENT
END:VCALENDAR