BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//labri.fr//NONSGML kigkonsult.se iCalcreator 2.41.92//
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
TZUNTIL:20260329T010000Z
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:20260407T074344Z
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 ?-optimall
 y\, we ask what can be achieved with (and against) finite-memory strategie
 s 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 
 space\, for a given game\, memory bounds b\, a non-negative error $\epsilo
 n$ and a value v\, if there exists a strategy that uses at most b memory m
 odes and achieves a value at least $v-\epsilon$ against any opponent strat
 egy 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 seco
 nd level of the polynomial hierarchy.\n\nOur results can be easily general
 ised to partial-information games and other objectives\, such as parity\, 
 which establish several complexity results for special classes of games. I
 n the talk\, we will focus on a well-known connection between stochastic g
 ames with discounted-payoff objectives and mean-payoff objectives to show 
 that approximating the unrestricted value of mean-payoff games\, i.e.\, ev
 en 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-
 Jensen and Patrick Totzke accepted at LICS 2024.
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
