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:
Qualitative Determinacy and Decidability of Stochastic Games
with Partial Observation
STATUS:CONFIRMED
ATTENDEE;CN="Hugo Gimbert
":
MAILTO:no@spam.com
DESCRIPTION:
(Joint work with Nathalie Bertrand and Blaise Genest.) We co
nsider the standard model of finite two-person zero-sum stoc
hastic games with signals. We are interested in the existenc
e of almost-surely winning or positively winning strategies\
, under reachability\, safety\, Büchi or co-Büchi winning ob
jectives. We prove two qualitative determinacy results. Firs
t\, in a reachability game either player 1 can achieve almos
t surely the reachability objective\, or player 2 can ensure
almost surely the complimentary safety objective\, or both
players have positively winning strategies. Second\, in a Bü
chi game if player 1 cannot achieve almost surely the Büchi
objective\, then player 2 can ensure positively the complime
ntary co-Büchi objective. We prove that players only need st
rategies with finite-memory\, whose sizes range from no memo
ry at all to doubly-exponential size\, with matching lower b
ounds. We provide fix-point algorithms to decide which playe
r has an almost surely winning or positive winning strategy
and compute the finite memory strategy. Complexity ranges fr
om EXPTIME to 2EXPTIME with matching lower bounds\, and bett
er complexity can be achieved for some special cases where o
ne of the players is better informed than her opponent.
DTSTART;TZID=Europe/Paris:20090421T110000
DURATION:PT1H
URL;VALUE=URI:http://www.lsv.ens-cachan.fr/Seminaires/?sem=200904211
100
UID:LSVsemLSV.200904211100@lsv.ens-cachan.fr
LOCATION:Salle de Conférence (Pavillon des Jardins)
END:VEVENT
END:VCALENDAR