• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>Computer Science Logic >Trading Probability for Fairness
【24h】

Trading Probability for Fairness

机译：公平交易的可能性

获取原文
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

Behavioral properties of open systems can be formalized as objectives in two-player games. Turn-based games model asynchronous interaction between the players (the system and its environment) by interleaving their moves. Concurrent games model synchronous interaction: the players always move simultaneously. Inflnitary winning criteria are considered: Buechi, co-Buechi, and more general parity conditions. A generalization of determinacy for parity games to concurrent parity games demands probabilistic (mixed) strategies: either player 1 has a mixed strategy to win with probability 1 (almost-sure winning), or player 2 has a mixed strategy to win with positive probability. This work provides efficient reductions of concurrent probabilistic Biichi and co-Buechi games to turn-based games with Buechi condition and parity winning condition with three priorities, respectively. From a theoretical point of view, the latter reduction shows that one can trade the probabilistic nature of almost-sure winning for a more general parity (fairness) condition. The reductions improve understanding of concurrent games and provide an alternative simple proof of determinacy of concurrent Buechi and co-Buechi games. From a practical point of view, the reductions turn solvers of turn-based games into solvers of concurrent probabilistic games. Thus improvements in the well-studied algorithms for the former carry over immediately to the latter. In particular, a recent improvement in the complexity of solving turn-based parity games yields an improvement in time complexity of solving concurrent probabilistic co-Buechi games from cubic to quadratic.
机译：开放系统的行为特性可以形式化为两人游戏中的目标。基于回合的游戏通过交错玩家的动作来建模玩家（系统及其环境）之间的异步交互。并发游戏模拟同步交互：玩家总是同时移动。要考虑硬性制胜标准：Buechi，co-Buechi和更一般的同等条件。将平价游戏的确定性推广到并发的平价游戏的一般性要求概率（混合）策略：玩家1具有以概率1获胜的混合策略（几乎确定获胜），或者玩家2具有以正概率获胜的混合策略。这项工作有效地将并发概率Biichi和co-Buechi游戏有效地减少为分别具有Buechi条件和奇偶性获胜条件且具有三个优先级的回合制游戏。从理论上讲，后者的减少表明人们可以用几乎确定的胜利的概率性质换取更一般的均等（公平）条件。减少可增强对并发游戏的理解，并提供并发Buechi和联合Buechi游戏确定性的另一种简单证明。从实际的角度来看，这种减少将基于回合的游戏的求解器转变为并发概率游戏的求解器。因此，对前者经过深入研究的算法的改进可立即应用于后者。特别地，解决基于回合的奇偶性游戏的复杂性的最近改进产生了解决从立方到二次的并发概率联合布奇游戏的时间复杂性的改进。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号