TY - JOUR

T1 - Subgame maxmin strategies in zero-sum stochastic games with tolerance levels

AU - Flesch, Janos

AU - Herings, P.J.J.

AU - Maes, Jasmine

AU - Predtetchinski, Arkadi

PY - 2021/12

Y1 - 2021/12

N2 - We study subgame phi-maxmin strategies in two-player zero-sum stochastic games with a countable state space, finite action spaces, and a bounded and universally measurable payoff function. Here, phi denotes the tolerance function that assigns a nonnegative tolerated error level to every subgame. Subgame f-maxmin strategies are strategies of the maximizing player that guarantee the lower value in every subgame within the subgame-dependent tolerance level as given by phi. First, we provide necessary and sufficient conditions for a strategy to be a subgame phi-maxmin strategy. As a special case, we obtain a characterization for subgame maxmin strategies, i.e., strategies that exactly guarantee the lower value at every subgame. Secondly, we present sufficient conditions for the existence of a subgame f-maxmin strategy. Finally, we show the possibly surprising result that each game admits a strictly positive tolerance function phi* with the following property: if a player has a subgame phi*-maxmin strategy, then he has a subgame maxmin strategy too. As a consequence, the existence of a subgame phi-maxmin strategy for every positive tolerance function f is equivalent to the existence of a subgame maxmin strategy.

AB - We study subgame phi-maxmin strategies in two-player zero-sum stochastic games with a countable state space, finite action spaces, and a bounded and universally measurable payoff function. Here, phi denotes the tolerance function that assigns a nonnegative tolerated error level to every subgame. Subgame f-maxmin strategies are strategies of the maximizing player that guarantee the lower value in every subgame within the subgame-dependent tolerance level as given by phi. First, we provide necessary and sufficient conditions for a strategy to be a subgame phi-maxmin strategy. As a special case, we obtain a characterization for subgame maxmin strategies, i.e., strategies that exactly guarantee the lower value at every subgame. Secondly, we present sufficient conditions for the existence of a subgame f-maxmin strategy. Finally, we show the possibly surprising result that each game admits a strictly positive tolerance function phi* with the following property: if a player has a subgame phi*-maxmin strategy, then he has a subgame maxmin strategy too. As a consequence, the existence of a subgame phi-maxmin strategy for every positive tolerance function f is equivalent to the existence of a subgame maxmin strategy.

KW - Stochastic games

KW - Zero-sum games

KW - Subgame phi-maxmin strategies

UR - https://www.scopus.com/record/display.uri?eid=2-s2.0-85102034401&origin=inward&txGid=768bff2c9891d7efc4009276d2c5068e

U2 - 10.1007/s13235-021-00378-z

DO - 10.1007/s13235-021-00378-z

M3 - Article

SN - 2153-0785

VL - 11

SP - 704

EP - 737

JO - Dynamic Games and Applications

JF - Dynamic Games and Applications

IS - 4

ER -