Hyperplane Separation Technique for Multidimensional Mean-Payoff Games
Hyperplane Separation Technique for Multidimensional Mean-Payoff Games
复制标题
DOI：
10.1007/978-3-642-40184-8_35
复制
发表时间：
2012-10
期刊：
影响因子：
--
通讯作者：
K. Chatterjee;Yaron Velner
中科院分区：
文献类型：
--
作者：
K. Chatterjee;Yaron Velner
我们考虑具有多维平均支付目标的有限状态递归对策图。在递归游戏中，有两种策略是相关的：全局策略和模块化策略。我们的贡献在于：(1)证明了在维数和权重绝对值一定的情况下，有限状态多维均值-支付对策可以在多项式时间内求解；而对于任意维，该问题是coNP-完全的。(2)证明了具有多维平均支付目标的单人递归对策可以在多项式时间内求解。以上两种算法均基于超平面分离技术。(3)对于递归对策，我们证明了在模块化策略下，多维问题是不可判定的。证明了当模数、退出数和权的最大绝对值固定时，一维模策略下的递归均值-支付对策可以在多项式时间内求解，而当退出数或模数无限时，该问题是NP难的。
We consider finite-state and recursive game graphs with multidimensional mean-payoff objectives. In recursive games two types of strategies are relevant: global strategies and modular strategies. Our contributions are: (1) We show that finite-state multidimensional mean-payoff games can be solved in polynomial time if the number of dimensions and the maximal absolute value of weights are fixed; whereas for arbitrary dimensions the problem is coNP-complete. (2) We show that one-player recursive games with multidimensional mean-payoff objectives can be solved in polynomial time. Both above algorithms are based on hyperplane separation technique. (3) For recursive games we show that under modular strategies the multidimensional problem is undecidable. We show that if the number of modules, exits, and the maximal absolute value of the weights are fixed, then one-dimensional recursive mean-payoff games under modular strategies can be solved in polynomial time, whereas for unbounded number of exits or modules the problem is NP-hard.