Abstract
This paper introduces an average-value-at-risk (AVaR) criterion for discrete-time zero-sum stochastic games with varying discount factors. The state space is a Borel space, the action space is denumerable, and the payoff function is allowed to be unbounded. We first transform the AVaR game problem into a bi-level optimization-game problem in which the outer optimization problem is a problem of minimizing a function of a single variable and the inner game problem has been shown to be equivalent to a so-called expected-discounted-positive-deviation (EDPD) game for discrete-time stochastic game. We solve the EDPD game problem in advance. More precisely, under suitable conditions, we not only establish the Shapley equation, the existence of the value of the game, and saddle points, but also prove that the saddle points can be computed by introducing a primal linear program and a dual linear program. Then, we show that the outer problem can be settled by solving the EDPD game problem. Furthermore, we provide an algorithm for computing (or at least approximating) the value of the game and the saddle points for the AVaR game problem. Finally, as an application, we apply our main results to an inventory-production system with numerical experiments.
Similar content being viewed by others
References
Andersson F, Mausser H, Rosen D, Uryasev S (2001) Credit risk optimization with conditional value-at-risk criterion. Math Program 89:273–291
Basu A, Ghosh MK (2012) Zero-sum risk-sensitive stochastic differential games. Math Oper Res 37(3):437–449
Basu A, Ghosh MK (2014) Zero-sum risk-sensitive stochastic games on a countable state space. Stoch Proc Appl 124(1):961–983
Bäuerle N, Ott J (2011) Markov decision processes with average-value-at-risk criteria. Math Meth Oper Res 74:361–379
Bauerle N, Rieder U (2017) Zero-sum risk-sensitive stochastic games. Stochastic Process Appl 127:622–642
Bertsekas DP, Shreve SE (1978) Stochastic optimal control: the discrete-time case. Academic Press, New York
Boda K, Filar JA (2006) Time consistent dynamic risk measures. Math Meth Oper Res 63:169–186
Filar JA, Boda K (2006) Two types of risk, in stochastic processes, optimization, and control theory: applications in financial engineering, queueing networks, and manufacturing systems, Internat. Ser. Oper. Res. Management Sci. 94, Springer, New York, 109–140
Ghosh MK, Kumar KS, Pal C (2016) Zero-sum risk-sensitive stochastic games for continuous-time Markov chains. Stoch Anal Appl 34:835–851
González-Sánchez D, Luque-Vázquez F, Minjárez-Sosa JA (2019) Zero-sum Markov games with random state-actions-dependent discount factors: existence of optimal strategies. Dyn Games Appl 9:103–121
González-Sánchez D, Luque-Vázquez F, Minjárez-Sosa JA (2021) Markov games with unknown random state-actions-dependent discount factors: empirical estimation. Asian J Control 23:166–177
Guo XP, Hernández-Lerma O (2007) Zero-sum games for continuous-time jump Markov processes in Polish spaces: discounted payoffs. Adv Appl Prob 39:645–668
Guo X, Zhang Y (2017) Zero-sum continuous-time Markov pure jump game over a fixed duration. J Math Anal Appl 452:1194–1203
Haurie A, Krawczyk JB, Zaccour G(2012) Games and dynamic games. World Scientific Publishing Co. Pre. Ltd, Singapore
Hernández-Lerma O, Lasserre JB (1996) Discrete-time Markov control processes. Basic optimality criteria. Springer-Verlag, New York
Hernández-Lerma O, Lasserre JB (1999) Further topics on discrete-time Markov control processes. Springer-Verlag, New York
Hernández-Lerma O, Lasserre JB (2001) Zero-sum stochastic games in Borel spaces: average payoff criterion. SIAM J Control Optim 39:1520–1539
Huang YH, Guo XP (2016) Minimum average value-at-risk for finite horizon semi-Markov decision processes in continuous time. SIAM J Optim 26:1–28
Huang XX, Guo XP (2017) A probability criterion for zero-sum stochastic games. J Dyn Games 4:369–383
Huang XX, Guo XP, Liu QL (2019) N-person nonzero-sum for continuous-time jump processes with varying discount factors. IEEE Trans Autom Control 64:2037–2044
Liu QL, Huang XX (2017) Discrete-time zero-sum Markov games with first passage criteria. Optimization 66:571–587
Miller CW, Yang I (2017) Optimal control of conditional value-at-risk in continuous time. SIAM J Optim 55:856–884
Minjárez-Sosa JA (2015) Markov control models with unknown random state-action-dependent discount factors. TOP 23(3):743–772
Nowak AS (1984) On zero-sum stochastic games with general state space. I. Prob Math Stat 4:13–32
Puterman ML (1994) Markov decision processes: discrete stochastic dynamic programming. John Wiley & Sons Inc, New York
Rockafellar RT, Uryasev S (2000) Optimization of conditional value-at-risk. J Risk 2:21–41
Rockafellar RT, Uryasev S (2002) Conditional value-at-risk for general loss distributions. J Bank Finane 26:1443–1471
Uǧurlu K (2017) Controlled Markov decision processes with AVaR criteria for unbounded costs. J Comput Appl Math 319:24–37
Wei QD (2018) Zero-sum games for continuous-time Markov jump processes with risk-sensitive finite-horizon cost criterion. Oper Res Lett 46:69–75
Zhang WZ, Huang YH, Guo XP (2014) Nonzero-sum constrained discrete-time Markov games: the case of unbounded costs. TOP 22:1074–1102
Acknowledgements
This research was supported in part by National Key Research and Development Program of China (Grant No. 2022YFA1004600), the National Natural Science Foundation of China (Grant No. 11931018) and Natural Science Foundation of Guangdong Province (No. 2023A1515012829).
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.
About this article
Cite this article
Liu, Q., Ching, WK. & Guo, X. Zero-sum stochastic games with the average-value-at-risk criterion. TOP 31, 618–647 (2023). https://doi.org/10.1007/s11750-023-00655-7
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11750-023-00655-7