One-clock priced time games

4^th November 2020, 13:00
Rasmus Ibsen-Jensen

Abstract

Priced 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).



One-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.



Since 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.



The 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).