一句话：证明单时钟简单价格时间博弈可在伪多项式时间内计算最优值与最优策略，并推广至负重置无环情形。
价格时间博弈是在价格时间自动机上的双人零和博弈：位置和变迁带权重，分别表示停留与执行动作的代价，玩家分别最小化和最大化到达目标位置的成本。本文研究单时钟且允许任意整数权重（含负权重）的价格时间博弈，重点分析‘简单价格时间博弈’子类，给出伪多项式时间算法，计算双方可达到的最优值及相应最优策略。作为副结果，作者还证明单时钟价格时间博弈是确定的，并将简单类的结果用于求解更一般的负重置无环价格时间博弈；完整的单时钟任意整数权重价格时间博弈的可判定性仍开放。
Priced timed games are two-player zero-sum games played on priced timed automata (whose locations and transitions are labeled by weights modelling the cost of spending time in a state and executing an action, respectively). The goals of the players are to minimise and maximise the cost to reach a target location, respectively. We consider priced timed games with one clock and arbitrary integer weights and show that, for an important subclass of them (the so-called simple priced timed games), one can compute, in pseudo-polynomial time, the optimal values that the players can achieve, with their associated optimal strategies. As side results, we also show that one-clock priced timed games are determined and that we can use our result on simple priced timed games to solve the more general class of so-called negative-reset-acyclic priced timed games (with arbitrary integer weights and one clock). The decidability status of the full class of priced timed games with one-clock and arbitrary integer weights still remains open.
@article{paperbot1666,
title = {One-Clock Priced Timed Games with Negative Weights},
author = {Thomas Brihaye and Gilles Geeraerts and Axel Haddad and Engel Lefaucheux and Benjamin Monmege},
journal = {Logical Methods in Computer Science},
volume = {Volume 18, Issue 3},
year = {2022},
doi = {10.46298/lmcs-18(3:17)2022}
}