Stochastic games with limited memory space

18^th October 2022, 13:00 Ashton Lecture Theatre
Prof. Abraham Neyman
Einstein Institute of Mathematics, The Hebrew University of Jerusalem

Abstract

Uniform e-optimal strategies in two-person zero-sum stochastic games that use little public memory space (explicitly, O(log n) memory states are used in the first n stages of the game) are introduced, and it is shown that any strategy in the Big Match that uses a finite public memory is worthless.

(Joint work with Kristoffer Arnsfelt Hansen and Rasmus Ibsen-Jensen)