Looking at mean-payoff and total-payoff through windows

K. Chatterjee, L. Doyen, M. Randour, J. Raskin, Information and Computation 242 (2015) 25–52.


Journal Article | Published | English
Author
; ; ;
Department
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.
Publishing Year
Date Published
2015-03-24
Journal Title
Information and Computation
Volume
242
Issue
6
Page
25 - 52
IST-REx-ID

Cite this

Chatterjee K, Doyen L, Randour M, Raskin J. Looking at mean-payoff and total-payoff through windows. Information and Computation. 2015;242(6):25-52. doi:10.1016/j.ic.2015.03.010
Chatterjee, K., Doyen, L., Randour, M., & Raskin, J. (2015). Looking at mean-payoff and total-payoff through windows. Information and Computation, 242(6), 25–52. https://doi.org/10.1016/j.ic.2015.03.010
Chatterjee, Krishnendu, Laurent Doyen, Mickael Randour, and Jean Raskin. “Looking at Mean-Payoff and Total-Payoff through Windows.” Information and Computation 242, no. 6 (2015): 25–52. https://doi.org/10.1016/j.ic.2015.03.010.
K. Chatterjee, L. Doyen, M. Randour, and J. Raskin, “Looking at mean-payoff and total-payoff through windows,” Information and Computation, vol. 242, no. 6, pp. 25–52, 2015.
Chatterjee K, Doyen L, Randour M, Raskin J. 2015. Looking at mean-payoff and total-payoff through windows. Information and Computation. 242(6), 25–52.
Chatterjee, Krishnendu, et al. “Looking at Mean-Payoff and Total-Payoff through Windows.” Information and Computation, vol. 242, no. 6, Elsevier, 2015, pp. 25–52, doi:10.1016/j.ic.2015.03.010.

Link(s) to Main File(s)
Access Level
OA Open Access

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar