Publication
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
Volume/pages
9364(2015), p. 429-445
ISI
000374241600031
Full text (Publisher's DOI)
Full text (open access)
UAntwerpen
Publication type
Subject
External links
Web of Science
Record
Identification
Creation 16.11.2018
Last edited 25.08.2021