{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,16]],"date-time":"2026-03-16T16:54:35Z","timestamp":1773680075470,"version":"3.50.1"},"reference-count":42,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2026,1,24]],"date-time":"2026-01-24T00:00:00Z","timestamp":1769212800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2026,1,24]],"date-time":"2026-01-24T00:00:00Z","timestamp":1769212800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"France 2030 program","award":["ANR-11-IDEX-0003"],"award-info":[{"award-number":["ANR-11-IDEX-0003"]}]},{"name":"72T28-1","award":["CEFIPRA Project No. 72T28-1"],"award-info":[{"award-number":["CEFIPRA Project No. 72T28-1"]}]},{"name":"72T28-1","award":["CEFIPRA Project No. 72T28-1"],"award-info":[{"award-number":["CEFIPRA Project No. 72T28-1"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Ann Oper Res"],"published-print":{"date-parts":[[2026,3]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>We consider a two-person zero-sum discounted stochastic game with random rewards and known transition probabilities. The players have opposite objectives and are interested in optimizing the expected discounted reward which they can obtain with a given confidence level when both the players play the worst possible move against each other. We model such a game problem by defining the chance-constrained optimization problem for each player. In this framework, risk attitudes are determined by confidence levels, where values of 0.5 or below correspond to risk-seeking behavior and values above 0.5 correspond to risk-averse behavior. When the reward vector follows a multivariate elliptically symmetric distribution, the game is equivalent to a minimax formulation. We consider the game with risk-seeking and risk-averse players separately. We show that the risk-seeking problem is equivalent to a constrained optimization of a parameterized zero-sum stochastic game and the optimal payoff of player 1 and optimal cost of player 2 can be computed using Riemann gradient sampling algorithms. Later we use the solution of the constrained optimization problem of each player to compute its optimal strategy by solving a linear programming problem. We reformulate the risk-averse problem as a discrete minimax problem. We propose an algorithm based on a linearization method and discuss its convergence properties. Alternatively, we reformulate the risk-averse problem as a second-order cone programming problem with bilinear constraints. The numerical experiments on randomly generated instances are performed to illustrate our theoretical results.<\/jats:p>","DOI":"10.1007\/s10479-026-07060-w","type":"journal-article","created":{"date-parts":[[2026,1,24]],"date-time":"2026-01-24T11:36:28Z","timestamp":1769254588000},"page":"1453-1484","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Zero-sum discounted stochastic games with random rewards"],"prefix":"10.1007","volume":"358","author":[{"given":"Lucas","family":"Osmani","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1318-6679","authenticated-orcid":false,"given":"Abdel","family":"Lisser","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Vikas Vikram","family":"Singh","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2026,1,24]]},"reference":[{"issue":"10","key":"7060_CR1","doi-asserted-by":"publisher","first-page":"1095","DOI":"10.1073\/pnas.39.10.1095","volume":"39","author":"LS Shapley","year":"1953","unstructured":"Shapley, L. S. (1953). Stochastic games. Proc. National Academy Sci., 39(10), 1095\u20131100.","journal-title":"Proc. National Academy Sci."},{"issue":"6","key":"7060_CR2","doi-asserted-by":"publisher","first-page":"1930","DOI":"10.1214\/aoms\/1177693059","volume":"42","author":"MJ Sobel","year":"1971","unstructured":"Sobel, M. J. (1971). Noncooperative stochastic games. Annals Math. Stat., 42(6), 1930\u20131935.","journal-title":"Annals Math. Stat."},{"key":"7060_CR3","doi-asserted-by":"crossref","unstructured":"Takahashi, M. (1964). Equilibrium points of stochastic non-cooperative $$ n $$-person games. Journal of Science of the Hiroshima University, Series AI (Mathematics) 28(1), 95\u201399","DOI":"10.32917\/hmj\/1206139509"},{"issue":"1","key":"7060_CR4","first-page":"89","volume":"28","author":"AM Fink","year":"1964","unstructured":"Fink, A. M. (1964). Equilibrium in a stochastic $$ n $$-person game. J. Sci. Hiroshima University, Series ai (Mathematics), 28(1), 89\u201393.","journal-title":"J. Sci. Hiroshima University, Series ai (Mathematics)"},{"key":"7060_CR5","doi-asserted-by":"crossref","unstructured":"Filar, J., & Vrieze, K. (1997). Summable Stochastic Games, pp. 155\u2013234. Springer, New York, NY.","DOI":"10.1007\/978-1-4612-4054-9_4"},{"issue":"6","key":"7060_CR6","first-page":"437","volume":"35","author":"T Raghavan","year":"1991","unstructured":"Raghavan, T., & Filar, J. A. (1991). Algorithms for stochastic games\u2013a survey. Zeitschrift f\u00fcr Operations Research, 35(6), 437\u2013472.","journal-title":"Zeitschrift f\u00fcr Operations Research"},{"issue":"1","key":"7060_CR7","doi-asserted-by":"publisher","first-page":"227","DOI":"10.1007\/BF01594936","volume":"50","author":"JA Filar","year":"1991","unstructured":"Filar, J. A., Schultz, T. A., Thuijsman, F., & Vrieze, O. (1991). Nonlinear programming and stationary equilibria in stochastic games. Mathematical Programming, 50(1), 227\u2013237.","journal-title":"Mathematical Programming"},{"issue":"2","key":"7060_CR8","doi-asserted-by":"publisher","first-page":"633","DOI":"10.1007\/s10479-020-03750-1","volume":"295","author":"N Krishnamurthy","year":"2020","unstructured":"Krishnamurthy, N., & Neogy, S. (2020). On Lemke processibility of lcp formulations for solving discounted switching control stochastic games. Annals Operations Res., 295(2), 633\u2013644.","journal-title":"Annals Operations Res."},{"issue":"2","key":"7060_CR9","doi-asserted-by":"publisher","first-page":"384","DOI":"10.1287\/moor.27.2.384.318","volume":"27","author":"T Raghavan","year":"2002","unstructured":"Raghavan, T., & Syed, Z. (2002). Computing stationary Nash equilibria of undiscounted single-controller stochastic games. Math. Operations Res., 27(2), 384\u2013400.","journal-title":"Math. Operations Res."},{"issue":"3","key":"7060_CR10","doi-asserted-by":"publisher","first-page":"375","DOI":"10.1007\/BF00935250","volume":"33","author":"T Parthasarathy","year":"1981","unstructured":"Parthasarathy, T., & Raghavan, T. (1981). An orderfield property for stochastic games when one player controls transition probabilities. J. Optim. Theory Appl., 33(3), 375\u2013392.","journal-title":"J. Optim. Theory Appl."},{"issue":"1","key":"7060_CR11","doi-asserted-by":"publisher","first-page":"48","DOI":"10.1016\/j.orl.2013.11.007","volume":"42","author":"VV Singh","year":"2014","unstructured":"Singh, V. V., & Hemachandra, N. (2014). A characterization of stationary Nash equilibria of constrained stochastic games with independent state processes. Oper. Res. Lett., 42(1), 48\u201352.","journal-title":"Oper. Res. Lett."},{"issue":"04","key":"7060_CR12","doi-asserted-by":"publisher","first-page":"1340025","DOI":"10.1142\/S0219198913400252","volume":"15","author":"VV Singh","year":"2013","unstructured":"Singh, V. V., Hemachandra, N., & Mallikarjuna Rao, K. (2013). Blackwell optimality in stochastic games. Int. Game Theory Rev., 15(04), 1340025.","journal-title":"Int. Game Theory Rev."},{"issue":"02","key":"7060_CR13","doi-asserted-by":"publisher","first-page":"1540018","DOI":"10.1142\/S0219198915400186","volume":"17","author":"VV Singh","year":"2015","unstructured":"Singh, V. V., & Hemachandra, N. (2015). A characterization of stationary Nash equilibria of single controller constrained stochastic games. Int. Game Theory Rev., 17(02), 1540018.","journal-title":"Int. Game Theory Rev."},{"issue":"2","key":"7060_CR14","doi-asserted-by":"publisher","first-page":"365","DOI":"10.1287\/opre.1110.0931","volume":"59","author":"E Karde\u015f","year":"2011","unstructured":"Karde\u015f, E., Ord\u00f3\u00f1ez, F., & Hall, R. W. (2011). Discounted robust stochastic games and an application to queueing control. Oper. Res., 59(2), 365\u2013382.","journal-title":"Oper. Res."},{"issue":"1","key":"7060_CR15","doi-asserted-by":"publisher","first-page":"7","DOI":"10.1016\/j.orl.2013.10.005","volume":"42","author":"E Karde\u015f","year":"2014","unstructured":"Karde\u015f, E. (2014). On discounted stochastic games with incomplete information on payoffs and a security application. Oper. Res. Lett., 42(1), 7\u201311.","journal-title":"Oper. Res. Lett."},{"issue":"1","key":"7060_CR16","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1287\/opre.1080.0685","volume":"58","author":"E Delage","year":"2010","unstructured":"Delage, E., & Mannor, S. (2010). Percentile optimization for markov decision processes with parameter uncertainty. Oper. Res., 58(1), 203\u2013213.","journal-title":"Oper. Res."},{"issue":"2","key":"7060_CR17","doi-asserted-by":"publisher","first-page":"1013","DOI":"10.1007\/s10479-022-05025-3","volume":"322","author":"V Varagapriya","year":"2023","unstructured":"Varagapriya, V., Singh, V. V., & Lisser, A. (2023). Joint chance-constrained markov decision processes. Ann. Oper. Res., 322(2), 1013\u20131035.","journal-title":"Ann. Oper. Res."},{"issue":"3","key":"7060_CR18","doi-asserted-by":"publisher","first-page":"1703","DOI":"10.1137\/24M1660711","volume":"35","author":"V Varagapriya","year":"2025","unstructured":"Varagapriya, V., Singh, V. V., & Lisser, A. (2025). Convex approximations of random constrained markov decision processes. SIAM J. Optim., 35(3), 1703\u20131730.","journal-title":"SIAM J. Optim."},{"key":"7060_CR19","doi-asserted-by":"crossref","unstructured":"Verma, A., Singh, V.V., & Lisser, A. (2025). Single-controller chance-constrained stochastic games. Journal of Optimization Theory and Applications 207.","DOI":"10.1007\/s10957-025-02767-5"},{"issue":"5","key":"7060_CR20","doi-asserted-by":"publisher","first-page":"640","DOI":"10.1016\/j.orl.2016.07.013","volume":"44","author":"VV Singh","year":"2016","unstructured":"Singh, V. V., Jouini, O., & Lisser, A. (2016). Existence of Nash equilibrium for chance-constrained games. Oper. Res. Lett., 44(5), 640\u2013644.","journal-title":"Oper. Res. Lett."},{"key":"7060_CR21","doi-asserted-by":"publisher","first-page":"998","DOI":"10.1007\/s10957-018-1343-0","volume":"178","author":"VV Singh","year":"2018","unstructured":"Singh, V. V., & Lisser, A. (2018). A characterization of Nash equilibrium for the games with random payoffs. J. Optim. Theory Appl., 178, 998\u20131013.","journal-title":"J. Optim. Theory Appl."},{"key":"7060_CR22","doi-asserted-by":"publisher","first-page":"1385","DOI":"10.1007\/s11590-016-1077-6","volume":"11","author":"VV Singh","year":"2017","unstructured":"Singh, V. V., Jouini, O., & Lisser, A. (2017). Distributionally robust chance-constrained games: existence and characterization of Nash equilibrium. Optim. Lett., 11, 1385\u20131405.","journal-title":"Optim. Lett."},{"issue":"6","key":"7060_CR23","doi-asserted-by":"publisher","first-page":"1243","DOI":"10.1287\/opre.22.6.1243","volume":"22","author":"RA Blau","year":"1974","unstructured":"Blau, R. A. (1974). Random-payoff two-person zero-sum games. Oper. Res., 22(6), 1243\u20131251.","journal-title":"Oper. Res."},{"issue":"4","key":"7060_CR24","doi-asserted-by":"publisher","first-page":"628","DOI":"10.1137\/1113079","volume":"13","author":"A Charnes","year":"1968","unstructured":"Charnes, A., Kirby, M. J. L., & Raike, W. M. (1968). Zero-zero chance-constrained games. Theory of Probability & Its Appl., 13(4), 628\u2013646.","journal-title":"Theory of Probability & Its Appl."},{"key":"7060_CR25","doi-asserted-by":"crossref","unstructured":"Song, T. (1992). In: Phillips, F.Y., Rousseau, J.J. (eds.) On Random Payoff Matrix Games, pp. 291\u2013308. Springer, Boston, MA.","DOI":"10.1007\/978-1-4615-3600-0_19"},{"issue":"3","key":"7060_CR26","doi-asserted-by":"publisher","first-page":"266","DOI":"10.1287\/mnsc.19.3.266","volume":"19","author":"RG Cassidy","year":"1972","unstructured":"Cassidy, R. G., Field, C. A., & Kirby, M. J. L. (1972). Solution of a satisficing model for random payoff games. Management Sci., 19(3), 266\u2013271.","journal-title":"Management Sci."},{"issue":"1","key":"7060_CR27","doi-asserted-by":"publisher","first-page":"142","DOI":"10.1287\/opre.16.1.142","volume":"16","author":"A Charnes","year":"1968","unstructured":"Charnes, A., Kirby, M., & Raike, W. (1968). Chance-constrained games with partially controllable strategies. Oper. Res., 16(1), 142\u2013149.","journal-title":"Oper. Res."},{"key":"7060_CR28","unstructured":"Fang KT, Kotz S, Ng KW (2013) Symmetric Multivariate and Related Distributions. Monographs on Statistics and Applied Probability, pp. 1\u201368. Springer, New York"},{"issue":"1","key":"7060_CR29","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1137\/16M1069298","volume":"27","author":"S Hosseini","year":"2017","unstructured":"Hosseini, S., & Uschmajew, A. (2017). A Riemannian gradient sampling algorithm for nonsmooth optimization on manifolds. SIAM J. Optim., 27(1), 173\u2013189.","journal-title":"SIAM J. Optim."},{"key":"7060_CR30","unstructured":"Burke, J.V., Curtis, F.E., Lewis, A.S., Overton, M.L., & Sim\u00f5es, L.E.A. (2018). Gradient Sampling Methods for Nonsmooth Optimization."},{"key":"7060_CR31","doi-asserted-by":"crossref","unstructured":"Shapley, L.S., & Snow, R.N. (1951). In: Kuhn, H.W., Tucker, A.W. (eds.) Basic solutions of discrete games, pp. 27\u201336. Princeton University Press, Princeton.","DOI":"10.1515\/9781400881727-004"},{"issue":"2","key":"7060_CR32","doi-asserted-by":"publisher","first-page":"583","DOI":"10.1111\/1468-0262.00296","volume":"70","author":"P Milgrom","year":"2002","unstructured":"Milgrom, P., & Segal, I. (2002). Envelope theorems for arbitrary choice sets. Econometrica, 70(2), 583\u2013601.","journal-title":"Econometrica"},{"issue":"1","key":"7060_CR33","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1007\/BF01737572","volume":"2","author":"JC Harsanyi","year":"1973","unstructured":"Harsanyi, J. C. (1973). Oddness of the number of equilibrium points: A new proof. Int. J. Game Theory, 2(1), 235\u2013250.","journal-title":"Int. J. Game Theory"},{"issue":"1","key":"7060_CR34","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1007\/BF00970225","volume":"28","author":"SP Ponomarev","year":"1987","unstructured":"Ponomarev, S. P. (1987). Submersions and preimages of sets of measure zero. Siberian Math. J., 28(1), 153\u2013163.","journal-title":"Siberian Math. J."},{"key":"7060_CR35","volume-title":"Introduction to Minimax","author":"VF Dem\u2019janov","year":"1974","unstructured":"Dem\u2019janov, V. F., & Malozemov, V. N. (1974). Introduction to Minimax. New York: Wiley."},{"key":"7060_CR36","doi-asserted-by":"crossref","unstructured":"Pshenichnyj BN (1994) The Discrete Minimax Problem and Algorithms, pp. 99\u2013141. Springer, Berlin, Heidelberg","DOI":"10.1007\/978-3-642-57918-9_3"},{"issue":"4","key":"7060_CR37","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1016\/0041-5553(81)90031-8","volume":"21","author":"VA Daugavet","year":"1981","unstructured":"Daugavet, V. A., & Malozemov, V. N. (1981). Quadratic rate of convergence of a linearization method for solving discrete minimax problems. USSR Comput. Mathematics and Mathematical Phys., 21(4), 19\u201328.","journal-title":"USSR Comput. Mathematics and Mathematical Phys."},{"issue":"2","key":"7060_CR38","doi-asserted-by":"publisher","first-page":"158","DOI":"10.1016\/0377-2217(82)90110-2","volume":"11","author":"MS Bazaraa","year":"1982","unstructured":"Bazaraa, M. S., & Goode, J. J. (1982). An algorithm for solving linearly constrained minimax problems. European J. Oper. Res., 11(2), 158\u2013166.","journal-title":"European J. Oper. Res."},{"key":"7060_CR39","doi-asserted-by":"publisher","first-page":"208","DOI":"10.1007\/BF01588966","volume":"14","author":"K Madsen","year":"1978","unstructured":"Madsen, K., & Schj\u00e6r-Jacobsen, H. (1978). Linearly constrained minimax optimization. Math. Program., 14, 208\u2013223.","journal-title":"Math. Program."},{"key":"7060_CR40","doi-asserted-by":"crossref","unstructured":"Rustem, B., & Howe, M. (2002). Algorithms for Worst-Case Design and Applications to Risk Management, pp. 139\u2013178. Princeton University Press, Princeton.","DOI":"10.1515\/9781400825110"},{"key":"7060_CR41","unstructured":"Kumar, N., Wang, K., Pratiush, U., Levy, K.Y., & Mannor, S. (2024). Policy gradient for reinforcement learning with general utilities. In: The Second Tiny Papers Track at ICLR 2024."},{"key":"7060_CR42","first-page":"98","volume":"22","author":"A Agarwal","year":"2019","unstructured":"Agarwal, A., Kakade, S. M., Lee, J., & Mahajan, G. (2019). On the theory of policy gradient methods: Optimality, approximation, and distribution shift. J. Mach. Learn. Res., 22, 98\u201319876.","journal-title":"J. Mach. Learn. Res."}],"container-title":["Annals of Operations Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10479-026-07060-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10479-026-07060-w","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10479-026-07060-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,16]],"date-time":"2026-03-16T16:05:45Z","timestamp":1773677145000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10479-026-07060-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,1,24]]},"references-count":42,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2026,3]]}},"alternative-id":["7060"],"URL":"https:\/\/doi.org\/10.1007\/s10479-026-07060-w","relation":{},"ISSN":["0254-5330","1572-9338"],"issn-type":[{"value":"0254-5330","type":"print"},{"value":"1572-9338","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,1,24]]},"assertion":[{"value":"25 February 2025","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 January 2026","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 January 2026","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that there is no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of Interest"}}]}}