Publication
Title
Mean-payoff games with partial observation
Author
Abstract
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.
Language
English
Source (journal)
Theoretical computer science. - Amsterdam
Publication
Amsterdam : 2018
ISSN
0304-3975
DOI
10.1016/J.TCS.2017.03.038
Volume/pages
735 :SI (2018) , p. 82-110
ISI
000436215300006
Full text (Publisher's DOI)
Full text (open access)
UAntwerpen
Faculty/Department
Research group
Publication type
Subject
External links
Web of Science
Record
Identifier
Creation 19.11.2018
Last edited 02.02.2023
To cite this reference