BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1246
DTSTAMP:20230914T125956Z
SUMMARY:Total-payoff games on graphs with windows
DESCRIPTION:Speaker: Pranshu Gaba\n\nAbstract: \nWe look at a two-player ga
me 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 a
n adjacent vertex in the graph\, yielding an infinite walk in the graph. E
ach time an edge is traversed\, Player 1 receives a payoff equal to the we
ight of the edge. An objective that has been traditionally studied for suc
h games is the total-payoff objective.\nIn this objective\, Player 1 wins
the game if the total payoff that they receive in the long run is non-nega
tive\, whereas Player 2 wins if the total-payoff is negative.\nA drawback
of this objective is that Player 1 may win the game\, and yet there may ex
ist arbitrarily long stretches in the play in which the total-payoff is ne
gative. This leads us to consider a stronger\nobjective: window total-payo
ff. In this objective\, Player 1 wins if from every point in the play\, th
ey can ensure that the total-payoff becomes non-negative in at most L step
s. This objective gives stronger guarantees on the payoff received by Play
er 1 while at the same time being easier to compute. Computing the winni
ng regions and winning strategies for the players for the traditional tota
l-payoff objective is only known to be in NP \\cap coNP\, whereas we see p
olynomial time algorithms to compute the same for the window total-payoff
objective.\nAll results presented in this talk are from the paper “Looki
ng at mean-payoff and total-payoff through windows” by Chatterjee\, Doye
n\, Randour\, and Raskin (2015).\n
URL:https://www.tcs.tifr.res.in/web/events/1246
DTSTART;TZID=Asia/Kolkata:20221021T140000
DTEND;TZID=Asia/Kolkata:20221021T150000
LOCATION:A201
END:VEVENT
END:VCALENDAR