  Classical objectives in two-player zero-sum games played on graphs often deal
with limit behaviors of infinite plays: e.g., mean-payoff and total-payoff in
the quantitative setting, or parity in the qualitative one (a canonical way to
encode omega-regular properties). Those objectives offer powerful abstraction
mechanisms and often yield nice properties such as memoryless determinacy.
However, their very nature provides no guarantee on time bounds within which
something good can be witnessed. In this work, we consider two approaches
toward inclusion of time bounds in parity games. The first one, parity-response
games, is based on the notion of finitary parity games [CHH09] and parity games
with costs [FZ14,WZ16]. The second one, window parity games, is inspired by
window mean-payoff games [CDRR15]. We compare the two approaches and show that
while they prove to be equivalent in some contexts, window parity games offer a
more tractable alternative when the time bound is given as a parameter (P-c.
vs. PSPACE-C.). In particular, it provides a conservative approximation of
parity games computable in polynomial time. Furthermore, we extend both
approaches to the multi-dimension setting. We give the full picture for both
types of games with regard to complexity and memory bounds.
  [CHH09] K. Chatterjee, T.A. Henzinger, F. Horn (2009): Finitary winning in
omega-regular games. ACM Trans. Comput. Log. 11(1). [FZ14] N. Fijalkow, M.
Zimmermann (2014): Parity and Streett Games with Costs. LMCS 10(2). [WZ16] A.
Weinert, M. Zimmermann (2016): Easy to Win, Hard to Master: Optimal Strategies
in Parity Games with Costs. Proc. of CSL, LIPIcs 62, pp. 31:1-31:17, Schloss
Dagstuhl - LZI. [CDRR15] K. Chatterjee, L. Doyen, M. Randour, J.-F. Raskin
(2015): Looking at mean-payoff and total-payoff through windows. Information
and Computation 242, pp. 25-52.
