Logic Seminar
T. E. S. Raghavan
UIC
On Martin's Determinacy of Borel Games and its Application to Stochastic games
Abstract: While every win-lose two person extensive game with finitely many moves and finitely many actions in each move and with perfect information admits an optimal winning strategy, it can fail to be true once the number of 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 that open sets or closed sets defined on the terminal vertices of the infinite 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 vertices, then also such games are determined.
While zero sum two person stochastic games with finitely many states and actions admit stationary optimal strategies for discounted payoffs, the existence of value with Cesaro payoff 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 randomized action choices. The seminal theorem of games is made quite simple and transparent by an application of the above theorem of Martin on perfect information Gale Stewart games. It simply bypasses many complicated constructions and technical estimates that view solution to the discounted Shapley value equation as an elementary sentence in the space of the ordered field of Laurentz series in fractional powers of the discount factor, namely the real closed field of Puiseux series and hence relies on many tools from real algebraic geometry. The talk will present this proof due to Ahok Maitra and Sudderth. Their theorem is applicable to much more general classes of payoffs besides Cesaro payoffs. This is a fruitful interplay between mathematical logic and game theory.
Thursday April 21, 2016 at 4:00 PM in SEO 636