Admissible Strategies in Infinite Games over Graphs
Admissible Strategies in Infinite Games over Graphs
复制标题
图上无限博弈中可接受的策略
DOI：
--
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
M. Faella
中科院分区：
文献类型：
--
作者：
M. Faella
我们考虑在有限图上进行的博弈，其目标是获得属于给定接受迹集合的迹。我们关注的是1号玩家不能强行获胜的状态。我们比较了几个标准，从这些状态确定博弈者1的最佳行为，最终确定了可接受策略的概念。
作为主要结果，我们给出了允许位置允许策略的目标的刻画。此外，我们还给出了一种计算各种共同目标的策略的简单算法，并证明了位置制胜策略的存在与位置子博弈完美策略的存在是等价的。
We consider games played on finite graphs, whose objective is to obtain a trace belonging to a given set of accepting traces. We focus on the states from which Player 1 cannot force a win. We compare several criteria for establishing what is the preferable behavior of Player 1 from those states, eventually settling on the notion of admissible strategy.
As the main result, we provide a characterization of the goals admitting positional admissible strategies. In addition, we derive a simple algorithm for computing such strategies for various common goals, and we prove the equivalence between the existence of positional winning strategies and the existence of positional subgame perfect strategies.