BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//labri.fr//NONSGML kigkonsult.se iCalcreator 2.41.92//
CALSCALE:GREGORIAN
METHOD:PUBLISH
UID:ae7d8763-75c5-4c21-aa95-30d61f8e3a16
X-WR-CALNAME:[M2F] Laurent Doyen (LMF\, ENS Paris-Saclay) - 'Stochastic Gam
 es with Synchronizing Objectives'
X-WR-TIMEZONE:Europe/Paris
BEGIN:VTIMEZONE
TZID:Europe/Paris
TZUNTIL:20241027T010000Z
BEGIN:STANDARD
TZNAME:CET
DTSTART:20211031T030000
TZOFFSETFROM:+0200
TZOFFSETTO:+0100
RDATE:20221030T030000
RDATE:20231029T030000
END:STANDARD
BEGIN:DAYLIGHT
TZNAME:CEST
DTSTART:20220327T020000
TZOFFSETFROM:+0100
TZOFFSETTO:+0200
RDATE:20230326T020000
RDATE:20240331T020000
END:DAYLIGHT
END:VTIMEZONE
BEGIN:VEVENT
UID:ae7d8763-75c5-4c21-aa95-30d61f8e3a16
DTSTAMP:20260531T194556Z
CLASS:PUBLIC
DESCRIPTION:We consider two-player stochastic games played on a finite grap
 h for infinitely many rounds. Stochastic games generalize both Markov deci
 sion processes (MDP) by adding an adversary player\, and two-player\ndeter
 ministic games by adding stochasticity. The outcome of the game is a seque
 nce of distributions over the states of the game graph.\nWe consider synch
 ronizing objectives\, which require the probability mass to accumulate in 
 a set of target states\, either always\, once\, infinitely often\, or alwa
 ys after some point in the outcome sequence\; and the winning modes of sur
 e winning (if the accumulated probability is equal to 1) and almost-sure w
 inning (if the accumulated probability is arbitrarily close to 1).\n\nWe p
 resent algorithms to compute the set of winning distributions for each of 
 these synchronizing modes\,\nshowing that the corresponding decision probl
 em is PSPACE-complete for synchronizing once and infinitely often\, and PT
 IME-complete for synchronizing always and always after some point. These b
 ounds are remarkably in line with the special case of MDPs\, while the alg
 orithmic solution and proof technique are considerably more involved\, eve
 n for deterministic games. This is because those games have a flavour of i
 mperfect information\, in particular they are not determined and randomize
 d strategies need to be considered\, even if there is no stochastic transi
 tions in the game graph. Moreover\, in combination with stochasticity in t
 he game graph\, finite-memory strategies are not sufficient in general (fo
 r synchronizing\ninfinitely often).
DTSTART;TZID=Europe/Paris:20221004T140000
DTEND;TZID=Europe/Paris:20221004T150000
LOCATION:LaBRI
SEQUENCE:0
SUMMARY:[M2F] Laurent Doyen (LMF\, ENS Paris-Saclay) - 'Stochastic Games wi
 th Synchronizing Objectives'
TRANSP:OPAQUE
END:VEVENT
END:VCALENDAR
