BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//University of Liverpool Computer Science Seminar System//v2//EN
BEGIN:VEVENT
DTSTAMP:20260607T023558Z
UID:Seminar-EcCo-1123@lxserverM.csc.liv.ac.uk
ORGANIZER:CN=Nicos 	Protopapas:MAILTO:N.Protopapas@liverpool.ac.uk
DTSTART:20201104T130000
DTEND:20201104T140000
SUMMARY:Economics and Computation Series
DESCRIPTION:Rasmus Ibsen-Jensen: One-clock priced time games\n\nPriced games (or longest-shortest path games or Dijkstra like games or total-payoff stopping games or ...) is basically the kind of game you get by starting from Dijkstra's shortest path problem and then making it into a zero-sum, turn-based game by adding in an opponent (i.e. you try to get to goal while minimizing the sum of cost of edges and your opponent tries to maximize this, when the states belong to either you or him and you decide how to move in your states and him in his states).\n\n \n\nOne-clock priced time games (formally this describes an polynomial-time equivalent special case called simple priced timed games) is then that kind of games but where we also add in time, which is a real number and then each player can choose to wait some amount of time before moving, but only such that time stays in [0,1]. Such a wait cost you an amount equal to the rate (a non-negative number associated with the state) times the amount waited.\n\n \n\nSince I currently have the best upper bound and lower bound for these one-clock priced timed games (with co-authors) spread out over two papers (one old, one new), I will talk about that.\n\n\n\nThe talk is based on "One-clock priced timed games are PSPACE-Hard" from LICS'20, with John and Rahul and "A faster algorithm for one-clock priced timed games" from CONCUR'12 with Thomas Dueholm Hansen and Peter Bro Miltersen from (at the time) Aarhus University (they have since both left academia).\n\nhttps://www.csc.liv.ac.uk/research/seminars/abstract.php?id=1123
LOCATION:
END:VEVENT
END:VCALENDAR