|
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 perfect information, they admit memoryless optimal strategies for both players and can be solved in NP boolean AND coNP. MPGs are suitable quantitative models for open reactive systems. However, in this context the assumption of perfect information 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)
|
|
|
|
Lecture notes in computer science. - Berlin, 1973, currens
|
|
|
Source (book)
|
|
|
|
13th International Symposium on Automated Technology for Verification, and Analysis (ATVA), OCT 12-15, 2015, Shanghai, PEOPLES R CHINA
|
|
|
Publication
|
|
|
|
Cham
:
Springer int publishing ag
,
2015
|
|
|
ISBN
|
|
|
|
978-3-319-24953-7
978-3-319-24952-0
|
|
|
DOI
|
|
|
|
10.1007/978-3-319-24953-7_31
|
|
|
Volume/pages
|
|
|
|
9364
(2015)
, p. 429-445
|
|
|
ISI
|
|
|
|
000374241600031
|
|
|
Full text (Publisher's DOI)
|
|
|
|
|
|
|
Full text (open access)
|
|
|
|
|
|