BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/586
DTSTAMP:20230914T125930Z
SUMMARY:On Martin's Determinacy of Borel Games and its Application to Stoch
astic Games
DESCRIPTION:Speaker: T.E.S. Raghavan (University of Illinois at Chicago\nDe
partment of Mathematics\, Statistics\nand Computer Science\n851\, S. Morga
n\nChicago\, IL 60607-7045\nUnited States of America)\n\nAbstract: \nAbstr
act: While every win-lose two person extensive game with finitely many mov
es and finitely many actions in each move and with perfect information adm
its an optimal winning strategy\, it can fail to be true once the number o
f moves is countable even if the action sets for the players are finite in
each move. Gale and Stewart introduced this class of games and showed tha
t open sets or closed sets defined on the terminal vertices of the infinit
e game tree as winning sets admit winning strategies and hence those games
are determined. Blackwell showed thatĀ $G_{\\delta}$ set as winning set
on the terminal vertices are also determined. Martin proved the remarkable
theorem that if the winning set is a Borel subset of the terminal vertice
s\, then also such games are determined.\n\nWhile zero sum two person stoc
hastic games with finitely many states and actions admit stationary optima
l strategies for discounted payoffs\, the existence of value with Cesaro p
ayoff is possible only in the space of behavioral strategies. At each move
players may have to peg on the entire history so far to make their random
ized action choices. The seminal theorem of Mertens and Neyman on the exis
tence of value for Cesaro payoff stochastic games is made quite simple and
transparent by an application of the above theorem of Martin on perfect i
nformation Gale Stewart games. It simply bypasses many complicated constru
ctions and technical estimates that view solution to the discounted Shaple
y value equation as an elementary sentence in the space of the ordered fie
ld of Laurentz series in fractional powers of the discount factor\, namely
the real closed field of Puiseux series and hence relies on many tools fr
omĀ real algebraic geometry. The talk will present this proof due to Asho
k Maitra and Sudderth. Their theorem is applicable to much more general cl
asses of payoffs besides Cesaro payoffs. This is a fruitful interplay betw
een mathematical logic and game theory.\n
URL:https://www.tcs.tifr.res.in/web/events/586
DTSTART;TZID=Asia/Kolkata:20150311T113000
DTEND;TZID=Asia/Kolkata:20150311T123000
LOCATION:AG-66 (Lecture Theatre)
END:VEVENT
END:VCALENDAR