|
Title
|
|
|
|
Looking at mean payoff through foggy windows
|
|
|
Author
|
|
|
|
|
|
|
Abstract
|
|
|
|
| Mean-payoff games (MPGs) are infinite duration two-player zero-sum games played on weighted graphs. Under the hypothesis of full observation, they admit memoryless optimal strategies for both players and can be solved in NP∩coNP. MPGs are suitable quantitative models for open reactive systems. However, in this context the assumption of full observation is not always realistic. For the partial-observation case, the problem that asks if the first player has an observation-based winning strategy that enforces a given threshold on the mean payoff, is undecidable. In this paper, we study the window mean-payoff objectives introduced recently as an alternative to the classical mean-payoff objectives. We show that, in sharp contrast to the classical mean-payoff objectives, some of the window mean-payoff objectives are decidable in games with partial observation. |
|
|
|
Language
|
|
|
|
English
|
|
|
Source (journal)
|
|
|
|
Acta informatica. - Berlin
|
|
|
Publication
|
|
|
|
Berlin
:
2018
|
|
|
ISSN
|
|
|
|
0001-5903
|
|
|
DOI
|
|
|
|
10.1007/S00236-017-0304-7
|
|
|
Volume/pages
|
|
|
|
55
:8
(2018)
, p. 627-647
|
|
|
ISI
|
|
|
|
000452106900002
|
|
|
Full text (Publisher's DOI)
|
|
|
|
|
|
|
Full text (publisher's version - intranet only)
|
|
|
|
|
|