BEGIN:VCALENDAR
VERSION:2.0
CALSCALE:GREGORIAN
METHOD:PUBLISH
X-WR-CALNAME:
X-WR-TIMEZONE:Europe/Paris
BEGIN:VTIMEZONE
TZID:Europe/Paris
X-LIC-LOCATION:Europe/Paris
BEGIN:DAYLIGHT
TZOFFSETFROM:+0100
TZOFFSETTO:+0200
TZNAME:CEST
DTSTART:19700329T020000
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=-1SU
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0200
TZOFFSETTO:+0100
TZNAME:CET
DTSTART:19701025T030000
RRULE:FREQ=YEARLY;BYMONTH=10;BYDAY=-1SU
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
SUMMARY:
Meet Your Expectations With Guarantees: Beyond Worst-Case Sy
nthesis in Quantitative Games
STATUS:CONFIRMED
ATTENDEE;CN="Mickael Randour
":
MAILTO:no@spam.com
DESCRIPTION:
We extend the quantitative synthesis framework by going beyo
nd the worst-case. On the one hand\, classical analysis of t
wo-player games involves an adversary (modeling the environm
ent of the system) which is purely antagonistic and asks for
strict guarantees. On the other hand\, stochastic models li
ke Markov decision processes represent situations where the
system is faced to a purely randomized environment: the aim
is then to optimize the expected payoff\, with no guarantee
on individual outcomes. We introduce the beyond worst-case s
ynthesis problem\, which is to construct strategies that gua
rantee some quantitative requirement in the worst-case while
providing an higher expected value against a particular sto
chastic model of the environment given as input. This proble
m is relevant to produce system controllers that provide nic
e expected performance in the everyday situation while ensur
ing a strict (but relaxed) performance threshold even in the
event of very bad (while unlikely) circumstances. We study
the beyond worst-case synthesis problem for two important qu
antitative settings: the mean-payoff and the shortest path.
In both cases\, we show how to decide the existence of finit
e-memory strategies satisfying the problem and how to synthe
size one if one exists. We establish algorithms and we study
complexity bounds and memory requirements.
DTSTART;TZID=Europe/Paris:20131126T110000
DURATION:PT1H
URL;VALUE=URI:http://www.lsv.ens-cachan.fr/Seminaires/?sem=201311261
100
UID:LSVsemLSV.201311261100@lsv.ens-cachan.fr
LOCATION:Salle de ConfĂ©rence (Pavillon des Jardins)
END:VEVENT
END:VCALENDAR