Subgame Optimal Strategies in Zero-Sum Stochastic Games with Tolerance Levels

(joint with Jean-Jacques Herings, Jasmine Maes, and Arkadi Predtetchinski)

Abstract: We study subgame f-optimal strategies in two-player zero-sum stochastic games with finite action spaces and a countable state space. Here f denotes the tolerance function, a function which assigns a non-negative tolerated error level to every subgame. Subgame f-optimal strategies are strategies that guarantee the value in every subgame within the subgame-dependent tolerance level as given by f. We present sufficient conditions for the existence of a subgame f-optimal strategy. We also show that the existence of subgame f-optimal strategies for every positive tolerance function f is equivalent to the existence of a subgame optimal strategy.