BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//labri.fr//NONSGML kigkonsult.se iCalcreator 2.39.1//
CALSCALE:GREGORIAN
METHOD:PUBLISH
UID:1fb78937-a7da-42ba-b5df-8e0880ce16d3
X-WR-CALNAME:[MTV] Sougata Bose (U. of Liverpool) - Solving Concurrent Mean
-payoff games with Bounded-memory Strategies
X-WR-TIMEZONE:Europe/Paris
BEGIN:VTIMEZONE
TZID:Europe/Paris
BEGIN:STANDARD
TZNAME:CET
DTSTART:20231029T030000
TZOFFSETFROM:+0200
TZOFFSETTO:+0100
RDATE:20241027T030000
RDATE:20251026T030000
END:STANDARD
BEGIN:DAYLIGHT
TZNAME:CEST
DTSTART:20240331T020000
TZOFFSETFROM:+0100
TZOFFSETTO:+0200
RDATE:20250330T020000
END:DAYLIGHT
END:VTIMEZONE
BEGIN:VEVENT
UID:1fb78937-a7da-42ba-b5df-8e0880ce16d3
DTSTAMP:20240723T201035Z
CLASS:PUBLIC
DESCRIPTION:In this talk\, we will consider the computational complexity of
solving stochastic games with mean-payoff objectives\, where ($\epsilon$-
)optimal strategies may require infinite memory. Instead of identifying sp
ecial classes in which simple strategies are sufficient to play 𝜀optimally
\, we ask what can be achieved with (and against) finite-memory strategies
up to a given bound on the memory. We show NP-hardness for approximating
zero-sum values\, already with respect to memoryless strategies and for 1-
player reachability games. \n\nWe show that one can decide in polynomial s
pace\, for a given game\, memory bounds b\, a non-negative error $\epsilon
$ and a value v\, if there exists a strategy that uses at most b memory mo
des and achieves a value at least $v-\epsilon$ against any opponent strate
gy that also uses at most b memory modes. Furthermore\, if $\epsilon>0$\,
we show that the complexity can be reduced to FNP[NP]\, i.e\, in the secon
d level of the polynomial hierarchy.\n\nOur results can be easily generali
sed to partial-information games and other objectives\, such as parity\, w
hich establish several complexity results for special classes of games. In
the talk\, we will focus on a well-known connection between stochastic ga
mes with discounted-payoff objectives and mean-payoff objectives to show t
hat approximating the unrestricted value of mean-payoff games\, i.e.\, eve
n when the players are not restricted to bounded-memory strategies can be
done in FNP[NP].\n\nThis talk is based on a joint work with Rasmus Ibsen-J
ensen and Patrick Totzke accepted at LICS 2024.\n
DTSTART;TZID=Europe/Paris:20240613T130000
DTEND;TZID=Europe/Paris:20240613T140000
LOCATION:salle 178\, zoom: https://bordeaux-inp-fr.zoom.us/j/89508306159
SEQUENCE:0
SUMMARY:[MTV] Sougata Bose (U. of Liverpool) - Solving Concurrent Mean-payo
ff games with Bounded-memory Strategies
TRANSP:OPAQUE
END:VEVENT
END:VCALENDAR