# Looking at Mean-Payoff and Total-Payoff through Windows

arXiv: https://arxiv.org/abs/1302.4248 · HTML: https://mlsanity.com/paper/1302.4248/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Feb 2013.

## Built on by (most cited first, 3 of 3)

- [Multiple Mean-Payoff Optimization under Local Stability Constraints](https://mlsanity.com/paper/2412.13369/) (2024)
- [Simplicity Lies in the Eye of the Beholder: A Strategic Perspective on Controllers in Reactive Synthesis](https://mlsanity.com/paper/2509.04129/) (2025)
- [Shielding for Higher-Order Safety](https://mlsanity.com/paper/2608.03662/) (2026)

## Abstract (arXiv)

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 cap 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.