Benjamin Monmege ; Julie Parreaux ; Pierre-Alain Reynier - Playing Stochastically in Weighted Timed Games to Emulate Memory

lmcs:10993 - Logical Methods in Computer Science, February 26, 2025, Volume 21, Issue 1 - https://doi.org/10.46298/lmcs-21(1:19)2025
Playing Stochastically in Weighted Timed Games to Emulate MemoryArticle

Authors: Benjamin Monmege ; Julie Parreaux ; Pierre-Alain Reynier

    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 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 work, we allow the players to use stochastic decisions, both in the choice of transitions and of timing delays. We give a definition of the expected value in weighted timed games. We then show that, in divergent weighted timed games as well as in (untimed) weighted games (that we call shortest-path games in the following), 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.


    Volume: Volume 21, Issue 1
    Published on: February 26, 2025
    Accepted on: November 27, 2024
    Submitted on: February 27, 2023
    Keywords: Computer Science - Computer Science and Game Theory

    Consultation statistics

    This page has been seen 445 times.
    This article's PDF has been downloaded 158 times.