一句话：证明在发散加权时间博弈和无权加权博弈中，随机策略无需记忆即可达到与经典确定值相同的值。
加权时间博弈是在带整数权的时间自动机上进行的双人零和博弈，考虑最优可达目标：Min 希望到达目标位置并最小化累积权。已知两个以上时钟时判断 Min 能否保证低于阈值是不可判定的，但在发散性等条件下可恢复可判定性；且 Min 可能需要有限记忆才能（接近）最优。本文允许玩家在迁移选择和时延选择上使用随机决策，并给出加权时间博弈中期望值的定义。作者证明，在发散加权时间博弈以及无权加权博弈（称为最短路径博弈）中，随机值等于经典确定值。因此 Min 仅用随机选择、无需记忆，仍可保证相同值。
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.
DOI 原文 · arXiv · PDF（开放获取） · DBLP
@article{abs-2105-00984,
title = {Playing Stochastically in Weighted Timed Games to Emulate Memory},
author = {Benjamin Monmege and Julie Parreaux and Pierre-Alain Reynier},
journal = {Logical Methods in Computer Science},
volume = {Volume 21, Issue 1},
year = {2025},
doi = {10.46298/lmcs-21(1:19)2025}
}