Alladi Ramakrishnan Hall

Determinacy of Gale Stewart Games with a Borel winning set and its implications to stochastic games

T.E.S. Raghavan

University of Illinois at Chicago

Martin in 1975 (Ann Math) proved the remarkable theorem that in two person games of perfect information with infinite moves and with
finitely many choices in each move with a winning set as a Borel set on the plays has value and a winner with a winning strategy. Later in 1998 (J Symbolic Logic), he established value for infinite G delta games of Blackwell. Avoiding the complicated approach using real algebraic
geometric theorems of Tarsky-Seidenberg and the theorems on Pseux series and algebraically closed fields etc., Maitra and Sudderth use Martin's theorem in Logic and Doob's Martingale convergence theorem to prove the
existence of value for stochastic games with countable states and very general payoffs that include Cesaro payoffs as a special case.