Tata Institute of Fundamental Research
On Martin's Determinacy of Borel Games and its Application to Stochastic Games
STCS Seminar
Speaker:
T.E.S. Raghavan (University of Illinois at Chicago
Department of Mathematics, Statistics
and Computer Science
851, S. Morgan
Chicago, IL 60607-7045
United States of America)
Organiser:
Sandeep K Juneja
Date:
Wednesday, 11 Mar 2015, 11:30 to 12:30
Venue:
AG-66 (Lecture Theatre)
(Scan to add to calendar)
Abstract:
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 Mertens and Neyman on the existence of value for Cesaro payoff stochastic 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 Ashok 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.
| Speaker: | T.E.S. Raghavan (University of Illinois at Chicago Department of Mathematics, Statistics and Computer Science 851, S. Morgan Chicago, IL 60607-7045 United States of America) |
| Organiser: | Sandeep K Juneja |
| Date: | Wednesday, 11 Mar 2015, 11:30 to 12:30 |
| Venue: | AG-66 (Lecture Theatre) |
(Scan to add to calendar)
Abstract:
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 Mertens and Neyman on the existence of value for Cesaro payoff stochastic 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 Ashok 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.
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 Mertens and Neyman on the existence of value for Cesaro payoff stochastic 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 Ashok 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.