The complexity of admissibility in Omega-regular games
The complexity of admissibility in Omega-regular games
复制标题
欧米茄常规游戏中可接受性的复杂性
DOI：
--
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
Mathieu Sassolas
中科院分区：
文献类型：
--
作者：
Romain Brenguier;Jean;Mathieu Sassolas
迭代可容许性是经典博弈论中一个广为人知的重要概念，用于确定多人矩阵对策中的理性行为。正如Berwanger最近所证明的那样，这个概念可以很好地扩展到具有ω-正则目标的图上的无限对策。在这篇文章中，我们研究了这类对策的算法性质。我们在一组策略上解决了自然决策问题的确切复杂性，这些策略在支配策略的迭代消除中幸存下来。作为我们构建的副产品，我们获得了自动机，它可以识别这些策略的所有可能结果。
Iterated admissibility is a well-known and important concept in classical game theory, e.g. to determine rational behaviors in multi-player matrix games. As recently shown by Berwanger, this concept can be soundly extended to infinite games played on graphs with ω-regular objectives. In this paper, we study the algorithmic properties of this concept for such games. We settle the exact complexity of natural decision problems on the set of strategies that survive iterated elimination of dominated strategies. As a byproduct of our construction, we obtain automata which recognize all the possible outcomes of such strategies.