Speaker: |
Pranshu Gaba |

Date: |
Friday, 21 Oct 2022, 14:00 to 15:00 |

Venue: |
A201 |

(Scan to add to calendar)

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