Looking at mean-payoff and total-payoff through windows Journal Article

Author(s): Chatterjee, Krishnendu; Doyen, Laurent; Randour, Mickael; Raskin, Jean-François
Article Title: Looking at mean-payoff and total-payoff through windows
Affiliation IST Austria
Abstract: We consider two-player games played on weighted directed graphs with mean-payoff and total-payoff objectives, two classical quantitative objectives. While for single-dimensional games the complexity and memory bounds for both objectives coincide, we show that in contrast to multi-dimensional mean-payoff games that are known to be coNP-complete, multi-dimensional total-payoff games are undecidable. We introduce conservative approximations of these objectives, where the payoff is considered over a local finite window sliding along a play, instead of the whole play. For single dimension, we show that (i) if the window size is polynomial, deciding the winner takes polynomial time, and (ii) the existence of a bounded window can be decided in NP ∩ coNP, and is at least as hard as solving mean-payoff games. For multiple dimensions, we show that (i) the problem with fixed window size is EXPTIME-complete, and (ii) there is no primitive-recursive algorithm to decide the existence of a bounded window.
Keywords: Quantitative objectives; two-player games on graphs; window mean-payoff; window total-payoff
Journal Title: Information and Computation
Volume: 242
ISSN: 0890-5401
Publisher: Elsevier  
Date Published: 2015-10-06
Start Page: 25
End Page: 52
DOI: 10.1016/j.ic.2015.03.010
Open access: yes (repository)
IST Austria Authors
Related IST Austria Work