We look at a two-player game played on a weighted directed graph. The game begins by placing a pawn on a vertex in the graph. The players then take turns moving the pawn to an adjacent vertex in the graph, yielding an infinite walk in the graph. Each time an edge is traversed, Player 1 receives a payoff equal to the weight of the edge. An objective that has been traditionally studied for such games is the total-payoff objective.
In this objective, Player 1 wins the game if the total payoff that they receive in the long run is non-negative, whereas Player 2 wins if the total-payoff is negative.
A drawback of this objective is that Player 1 may win the game, and yet there may exist arbitrarily long stretches in the play in which the total-payoff is negative. This leads us to consider a stronger
objective: window total-payoff. In this objective, Player 1 wins if from every point in the play, they can ensure that the total-payoff becomes non-negative in at most L steps. This objective gives stronger guarantees on the payoff received by Player 1 while at the same time being easier to compute. Computing the winning regions and winning strategies for the players for the traditional total-payoff objective is only known to be in NP \cap coNP, whereas we see polynomial time algorithms to compute the same for the window total-payoff objective.
All results presented in this talk are from the paper “Looking at mean-payoff and total-payoff through windows” by Chatterjee, Doyen, Randour, and Raskin (2015).
