We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Looking at mean payoff through foggy windows.
- Authors
Hunter, Paul; Pérez, Guillermo A.; Raskin, Jean-François
- 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.
- Subjects
BRIBERY; PARTIAL algebras; MEMORYLESS systems; SYSTEM analysis; SIMULATION methods &; models
- Publication
Acta Informatica, 2018, Vol 55, Issue 8, p627
- ISSN
0001-5903
- Publication type
Article
- DOI
10.1007/s00236-017-0304-7