BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//University of Liverpool Computer Science Seminar System//v2//EN
BEGIN:VEVENT
DTSTAMP:20260921T003248Z
UID:Seminar-EcCo-567@lxserverM.csc.liv.ac.uk
ORGANIZER:CN=Nicos 	Protopapas:MAILTO:N.Protopapas@liverpool.ac.uk
DTSTART:20180117T130000
DTEND:20180117T140000
SUMMARY:Economics and Computation Series
DESCRIPTION:Rahul Savani: Reachability Switching Games\n\nWe study the problem of deciding the winner of reachability switching games. These games provide deterministic analogues of Markovian systems. We study zero-, one-, and two-player variants of these games. We show that the zero-player case is NL-hard, the one-player case is NP-complete, and that the two-player case is PSPACE-hard and in EXPTIME. In the one- and two-player cases, the problem of determining the winner of a switching game turns out to be much harder than the problem of determining the winner of a Markovian game. We also study the structure of winning strategies in these games, and in particular we show that both players in a two-player reachability switching game require exponential memory.\n\nJoint work with John Fearnley, Martin Gairing, and Matthias Mnich.\n\nhttps://www.csc.liv.ac.uk/research/seminars/abstract.php?id=567
LOCATION:
END:VEVENT
END:VCALENDAR