期刊
THEORETICAL COMPUTER SCIENCE
卷 735, 期 -, 页码 82-110出版社
ELSEVIER SCIENCE BV
DOI: 10.1016/j.tcs.2017.03.038
关键词
Quantitative games; Partial observation; Verification; Synthesis; Game theory
资金
- ERC Starting grant inVEST [FP7-279499]
Mean-payoff games are important quantitative models for open reactive systems. They have been widely studied as games of full observation. In this paper we investigate the algorithmic properties of several sub-classes of mean-payoff games where the players have asymmetric information about the state of the game. These games are in general undecidable and not determined according to the classical definition. We show that such games are determined under a more general notion of winning strategy. We also consider mean-payoff games where the winner can be determined by the winner of a finite cycle forming game. This yields several decidable classes of mean-payoff games of asymmetric information that require only finite-memory strategies, including a generalization of full observation games where positional strategies are sufficient. We give an exponential time algorithm for determining the winner of the latter. (C) 2017 Elsevier B.V. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据