Playing stochastically in Weighted Timed Games to Emulate Memory
- Prelegent(ci)
- Julie Parreaux
- Afiliacja
- University of Warsaw
- Termin
- 20 grudnia 2023 14:15
- Pokój
- p. 5050
- Seminarium
- Seminarium „Teoria automatów”
Weighted timed games are two-player zero-sum games played in a timed
automaton equipped with integer weights. We consider optimal
reachability objectives, in which one of the players, that we call Min,
wants to reach a target location while minimising the cumulated weight.
While knowing if Min has a strategy to guarantee a value lower than a
given threshold is known to be undecidable (with two or more clocks),
several conditions, one of them being the divergence, have been given to
recover decidability. In such weighted timed games (like in untimed
weighted games in the presence of negative weights), Min may need finite
memory to play (close to) optimally. This is thus tempting to try to
emulate this finite memory with other strategic capabilities.
In this talk, after presenting weighted timed games and the properties
of the classical (deterministic) value, we allow the players to use
stochastic decisions, both in the choice of transitions and of timing
delays. We give for the first time a definition of the expected value in
weighted timed games, overcoming several theoretical challenges. We then
show that, in divergent weighted timed games, the stochastic value is
indeed equal to the classical (deterministic) value, thus proving that
Min can guarantee the same value while only using stochastic choices,
and no memory.
This is joint work with Benjamin Monmege and Pierre-Alain Reynier.