一句话：提出 Joker 博弈，将并发博弈中的有限帮助建模为带成本动作，研究最小化 Joker 使用的策略，并用于模型测试生成。
本文提出 Joker 博弈，一种非严格对抗的并发博弈变体：玩家1可借助玩家2的 Joker 动作获胜。作者将其形式化为成本博弈，其中 Joker 的使用视为成本，并构造以最少帮助确保胜利的策略。理论研究表明，成本最小策略与可容许策略并不一致；随机化虽不能帮助赢得 Joker 博弈，却可能减少所需 Joker 数量；此外还引入最小化策略执行步数的次级目标。最后，作者将该框架应用于基于模型的测试生成，展示其实用优势。
This paper coins the notion of Joker games, a variant of concurrent games where the players are not strictly adversarial. Instead, Player 1 can get help from Player 2 by playing a Joker move. We formalize these games as cost games and develop strategies that minimize the use of Jokers - viewed as costs - to secure a win with the least possible help. Our investigation studies the theoretical underpinnings of these games and their associated Joker strategies. In particular, when comparing our cost-minimal strategies with admissible strategies, we find out that they differ. Moreover, while randomization can be beneficial in conventional concurrent games, it does not aid in winning Joker games, although it can help reduce the number of needed Jokers. We also enhance our framework by introducing a secondary objective, namely by minimizing the number of moves executed by a Joker strategy. Finally, we demonstrate the practical advantages of our approach by applying it to test generation in model-based testing.
DOI 原文 · arXiv · PDF（开放获取） · DBLP
@article{abs-2304-13417,
title = {With a little help from your friends: semi-cooperative games via Joker moves},
author = {Petra van den Bos and Marielle Stoelinga},
journal = {Logical Methods in Computer Science},
volume = {Volume 21, Issue 1},
year = {2025},
doi = {10.46298/lmcs-21(1:26)2025}
}