• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>Annual ACM/IEEE Symposium on Logic in Computer Science >Perfect-Information Stochastic Games with Generalized Mean-Payoff Objectives*
【24h】

Perfect-Information Stochastic Games with Generalized Mean-Payoff Objectives*

机译：具有广义均值支付目标的完美信息随机游戏*

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

摘要

Graph games provide the foundation for modeling and synthesizing reactive processes. In the synthesis of stochastic reactive processes, the traditional model is perfect-information stochastic games, where some transitions of the game graph are controlled by two adversarial players, and the other transitions are executed probabilistically. We consider such games where the objective is the conjunction of several quantitative objectives (specified as mean-payoff conditions), which we refer to as generalized mean-payoff objectives. The basic decision problem asks for the existence of a finite-memory strategy for a player that ensures the generalized mean-payoff objective be satisfied with a desired probability against all strategies of the opponent. A special case of the decision problem is the almost-sure problem where the desired probability is 1. Previous results presented a semi-decision procedure for ε-approximations of the almost-sure problem. In this work, we show that both the almost-sure problem as well as the general basic decision problem are coNP-complete, significantly improving the previous results. Moreover, we show that in the case of 1-player stochastic games, randomized memoryless strategies are sufficient and the problem can be solved in polynomial time. In contrast, in two-player stochastic games, we show that even with randomized strategies exponential memory is required in general, and present a matching exponential upper bound. We also study the basic decision problem with infinite-memory strategies and present computational complexity results for the problem. Our results are relevant in the synthesis of stochastic reactive systems with multiple quantitative requirements.
机译：图形游戏为建模和综合反应过程提供了基础。在随机反应过程的综合中，传统模型是完美信息随机游戏，其中游戏图的某些过渡由两个对抗性玩家控制，而其他过渡则按概率执行。我们考虑这样的博弈，其目标是多个量化目标（指定为均值收益条件）的结合，我们将其称为广义均值收益目标。基本的决策问题要求为玩家提供一种有限记忆策略，以确保以相对于对手所有策略的期望概率满足广义均值支付目标。决策问题的一个特例是期望概率为1的几乎确定问题。先前的结果提出了关于几乎确定问题的ε逼近的半确定过程。在这项工作中，我们表明几乎确定的问题以及一般的基本决策问题都是coNP完全的，大大改善了先前的结果。此外，我们表明，在1人随机游戏的情况下，随机无记忆策略就足够了，并且可以在多项式时间内解决该问题。相反，在两人随机游戏中，我们表明，即使采用随机策略，通常也需要指数存储，并呈现出匹配的指数上限。我们还研究了具有无限内存策略的基本决策问题，并给出了该问题的计算复杂度结果。我们的结果与具有多个定量要求的随机反应系统的合成有关。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号