Subgame maxmin strategies in zero-sum stochastic games with tolerance levels. (English) Zbl 1481.91018
Summary: 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 \(\phi \)-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 \(\phi \)-maxmin strategy. Finally, we show the possibly surprising result that each game admits a strictly positive tolerance function \(\phi^\ast\) with the following property: if a player has a subgame \(\phi^\ast\)-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 \(\phi\) is equivalent to the existence of a subgame maxmin strategy.
MSC:
| 91A15 | Stochastic games, stochastic differential games |
| 91A10 | Noncooperative games |
| 91A05 | 2-person games |
References:
| [1] | Abate, A.; Redig, F.; Tkachev, I., On the effect of perturbation of conditional probabilities in total variation, Stat Probab Lett, 88, 1-8 (2014) · Zbl 1370.60006 · doi:10.1016/j.spl.2014.01.009 |
| [2] | Blackwell, D.; Ferguson, T., The big match, Ann Math Stat, 39, 159-163 (1968) · Zbl 0164.50305 · doi:10.1214/aoms/1177698513 |
| [3] | Bogachev, VI, Measure Theory (2007), Berlin: Springer, Berlin · Zbl 1120.28001 · doi:10.1007/978-3-540-34514-5 |
| [4] | Bruyère V (2017) Computer aided synthesis: a game-theoretic approach. In: Charlier E, Leroy J, Rigo M (eds) Developments in Language Theory, vol 10396. Lecture Notes in Computer Science. Springer, pp 3-35 · Zbl 1494.91033 |
| [5] | Flesch J, Herings PJJ, Maes J, Predtetchinski A (2018) Subgame maxmin strategies in zero-sum stochastic games with tolerance levels. GSBE Research Memorandum 18/20, Maastricht University, Maastricht, pp. 1-37 |
| [6] | Flesch, J.; Predtetchinski, A., On refinements of subgame perfect \(\epsilon \)-equilibrium, Int J Game Theory, 45, 523-542 (2016) · Zbl 1388.91040 · doi:10.1007/s00182-015-0468-8 |
| [7] | Flesch, J.; Predtetchinski, A.; Sudderth, W., Characterization and simplification of optimal strategies in positive stochastic games, J Appl Probab, 55, 728-741 (2018) · Zbl 1417.91072 · doi:10.1017/jpr.2018.47 |
| [8] | Flesch J, Thuijsman F, Vrieze OJ (1998) Improving strategies in stochastic games. In: Proceedings of the 37th IEEE Conference on Decision and Control, Vol 3, IEEE, pp. 2674-2679 · Zbl 0909.90284 |
| [9] | Gillette D (1957) Stochastic games with zero stop probabilities. In: Dresher M, Tucker AW, Wolfe P (eds) Contributions to the Theory of Games, vol III. Annals of Mathematics Studies, Volume 39. Princeton University Press, Princeton, New Jersey, pp 179-187 · Zbl 0078.33001 |
| [10] | Laraki, R.; Maitra, A.; Sudderth, W., Two-person zero-sum stochastic games with semicontinuous payoff, Dyn Games Appl, 3, 162-171 (2013) · Zbl 1273.91050 · doi:10.1007/s13235-012-0054-7 |
| [11] | Mailath, G.; Postlewaite, A.; Samuelson, L., Contemporaneous perfect epsilon-equilibria, Games Econ Behav, 53, 126-140 (2005) · Zbl 1117.91313 · doi:10.1016/j.geb.2005.05.002 |
| [12] | Maitra, A.; Sudderth, W., Discrete gambling and stochastic games (1996), New York: Springer, New York · Zbl 0864.90148 · doi:10.1007/978-1-4612-4002-0 |
| [13] | Maitra, A.; Sudderth, W., Finitely additive stochastic games with Borel measurable payoffs, Int J Game Theory, 27, 257-267 (1998) · Zbl 0947.91013 · doi:10.1007/s001820050071 |
| [14] | Martin, DA, The determinacy of Blackwell games, J Symb Logic, 63, 1565-1581 (1998) · Zbl 0926.03071 · doi:10.2307/2586667 |
| [15] | Mashiah-Yaakovi, A., Correlated equilibria in stochastic games with Borel measurable payoffs, Dyn Games Appl, 5, 120-135 (2015) · Zbl 1319.91029 · doi:10.1007/s13235-014-0122-2 |
| [16] | Puterman, ML, Markov decision processes, discrete stochastic dynamic programming (1994), Hoboken: Wiley, Hoboken · Zbl 0829.90134 · doi:10.1002/9780470316887 |
| [17] | Radner, R., Collusive behavior in noncooperative epsilon-equilibria of oligopolies with long but finite lives, J Econ Theory, 22, 136-154 (1980) · Zbl 0434.90015 · doi:10.1016/0022-0531(80)90037-X |
| [18] | Rosenberg, D.; Solan, E.; Vieille, N., Stopping games with randomized strategies, Probab Theory Related Fields, 119, 433-451 (2001) · Zbl 0988.60037 · doi:10.1007/PL00008766 |
| [19] | Selten, R., Spieltheoretische Behandlung eines Oligopolmodells mit Nachfrageträgheit: Teil I: Bestimmung des dynamischen Preisgleichgewichts, Zeitschrift für die gesamte Staatswissenschaft, 121, 301-324 (1965) |
| [20] | Solan, E.; Vieille, N., Uniform value in recursive games, Ann App Probab, 12, 1185-1201 (2002) · Zbl 1040.91018 |
| [21] | Tversky, A.; Kahneman, D., The framing of decisions and the psychology of choice, Science, 211, 453-458 (1981) · Zbl 1225.91017 · doi:10.1126/science.7455683 |
| [22] | Yeh, J., Martingales and stochastic analysis (1995), Singapore: World Scientific, Singapore · Zbl 0848.60001 · doi:10.1142/2948 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
