[{"abstract":[{"lang":"eng","text":"Zero-sum stochastic games are parameterized by payoffs, transitions, and possibly a discount rate. In this article, we study how the main solution concepts, the discounted and undiscounted values, vary when these parameters are perturbed. We focus on the marginal values, introduced by Mills in 1956 in the context of matrix games—that is, the directional derivatives of the value along any fixed perturbation. We provide a formula for the marginal values of a discounted stochastic game. Further, under mild assumptions on the perturbation, we provide a formula for their limit as the discount rate vanishes and for the marginal values of an undiscounted stochastic game. We also show, via an example, that the two latter differ in general."}],"volume":50,"quality_controlled":"1","external_id":{"isi":["001184648000001"]},"department":[{"_id":"GradSch"},{"_id":"KrCh"}],"date_created":"2024-05-22T11:41:14Z","language":[{"iso":"eng"}],"publication_status":"published","acknowledgement":"This work was supported by Fondation CFM pour la Recherche; the European Research Council [Grant ERC-CoG-863818 (ForM-SMArt)]; and Agence Nationale de la Recherche [Grant ANR-21-CE40-0020].","publication_identifier":{"issn":["0364-765X"],"eissn":["1526-5471"]},"publication":"Mathematics of Operations Research","author":[{"first_name":"Luc","last_name":"Attia","full_name":"Attia, Luc"},{"full_name":"Oliu-Barton, Miquel","last_name":"Oliu-Barton","first_name":"Miquel"},{"last_name":"Saona Urmeneta","full_name":"Saona Urmeneta, Raimundo J","id":"BD1DF4C4-D767-11E9-B658-BC13E6697425","first_name":"Raimundo J","orcid":"0000-0001-5103-038X"}],"scopus_import":"1","ec_funded":1,"isi":1,"intvolume":"        50","article_processing_charge":"No","citation":{"ama":"Attia L, Oliu-Barton M, Saona Urmeneta RJ. Marginal values of a stochastic game. <i>Mathematics of Operations Research</i>. 2025;50(1):482-505. doi:<a href=\"https://doi.org/10.1287/moor.2023.0297\">10.1287/moor.2023.0297</a>","apa":"Attia, L., Oliu-Barton, M., &#38; Saona Urmeneta, R. J. (2025). Marginal values of a stochastic game. <i>Mathematics of Operations Research</i>. Institute for Operations Research and the Management Sciences. <a href=\"https://doi.org/10.1287/moor.2023.0297\">https://doi.org/10.1287/moor.2023.0297</a>","chicago":"Attia, Luc, Miquel Oliu-Barton, and Raimundo J Saona Urmeneta. “Marginal Values of a Stochastic Game.” <i>Mathematics of Operations Research</i>. Institute for Operations Research and the Management Sciences, 2025. <a href=\"https://doi.org/10.1287/moor.2023.0297\">https://doi.org/10.1287/moor.2023.0297</a>.","ista":"Attia L, Oliu-Barton M, Saona Urmeneta RJ. 2025. Marginal values of a stochastic game. Mathematics of Operations Research. 50(1), 482–505.","short":"L. Attia, M. Oliu-Barton, R.J. Saona Urmeneta, Mathematics of Operations Research 50 (2025) 482–505.","mla":"Attia, Luc, et al. “Marginal Values of a Stochastic Game.” <i>Mathematics of Operations Research</i>, vol. 50, no. 1, Institute for Operations Research and the Management Sciences, 2025, pp. 482–505, doi:<a href=\"https://doi.org/10.1287/moor.2023.0297\">10.1287/moor.2023.0297</a>.","ieee":"L. Attia, M. Oliu-Barton, and R. J. Saona Urmeneta, “Marginal values of a stochastic game,” <i>Mathematics of Operations Research</i>, vol. 50, no. 1. Institute for Operations Research and the Management Sciences, pp. 482–505, 2025."},"related_material":{"record":[{"id":"20234","relation":"dissertation_contains","status":"public"}]},"_id":"17037","title":"Marginal values of a stochastic game","month":"02","doi":"10.1287/moor.2023.0297","article_type":"original","type":"journal_article","day":"01","publisher":"Institute for Operations Research and the Management Sciences","issue":"1","status":"public","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","page":"482-505","date_published":"2025-02-01T00:00:00Z","project":[{"_id":"0599E47C-7A3F-11EA-A408-12923DDC885E","grant_number":"863818","call_identifier":"H2020","name":"Formal Methods for Stochastic Models: Algorithms and Applications"}],"year":"2025","oa_version":"None","date_updated":"2026-04-07T12:31:21Z"},{"author":[{"full_name":"Chatterjee, Krishnendu","last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu","orcid":"0000-0002-4561-241X"},{"first_name":"Miquel","full_name":"Oliu-Barton, Miquel","last_name":"Oliu-Barton"},{"orcid":"0000-0001-5103-038X","first_name":"Raimundo J","id":"BD1DF4C4-D767-11E9-B658-BC13E6697425","last_name":"Saona Urmeneta","full_name":"Saona Urmeneta, Raimundo J"}],"scopus_import":"1","publication":"Mathematics of Operations Research","ec_funded":1,"isi":1,"intvolume":"        50","acknowledgement":"This research was supported by Fondation CFM pour la Recherche, the H2020 European Research Council [Grant ERC-CoG-863818 (ForM-SMArt)], the Austrian Science Fund [Grant 10.55776/COE12], ANID Chile [Grant ACT210005], and Agence Nationale de la Recherche [Grant ANR-21-CE40-0020].","publication_identifier":{"issn":["0364-765X"],"eissn":["1526-5471"]},"external_id":{"isi":["001328875900001"]},"department":[{"_id":"GradSch"},{"_id":"KrCh"}],"date_created":"2024-10-09T07:02:20Z","language":[{"iso":"eng"}],"corr_author":"1","publication_status":"published","abstract":[{"lang":"eng","text":"Matrix games are the most basic model in game theory, and yet robustness with respect to small perturbations of the matrix entries is not fully understood. In this paper, we introduce value positivity and uniform value positivity, two properties that refine the notion of optimality in the context of polynomially perturbed matrix games. The first concept captures how the value depends on the perturbation parameter, and the second consists of the existence of a fixed strategy that guarantees the value of the unperturbed matrix game for every sufficiently small positive parameter. We provide polynomial-time algorithms to check whether a polynomially perturbed matrix game satisfies these properties. We further provide the functional form for a parameterized optimal strategy and the value function. Finally, we translate our results to linear programming and stochastic games, where value positivity is related to the existence of robust solutions."}],"volume":50,"quality_controlled":"1","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","page":"2433-3282","date_published":"2024-10-01T00:00:00Z","project":[{"name":"Formal Methods for Stochastic Models: Algorithms and Applications","call_identifier":"H2020","_id":"0599E47C-7A3F-11EA-A408-12923DDC885E","grant_number":"863818"}],"oa_version":"None","year":"2024","date_updated":"2026-04-07T12:31:21Z","type":"journal_article","publisher":"Institute for Operations Research and the Management Sciences","day":"01","issue":"4","status":"public","doi":"10.1287/moor.2022.0332","OA_type":"closed access","article_type":"original","article_processing_charge":"No","citation":{"chicago":"Chatterjee, Krishnendu, Miquel Oliu-Barton, and Raimundo J Saona Urmeneta. “Value-Positivity for Matrix Games.” <i>Mathematics of Operations Research</i>. Institute for Operations Research and the Management Sciences, 2024. <a href=\"https://doi.org/10.1287/moor.2022.0332\">https://doi.org/10.1287/moor.2022.0332</a>.","ista":"Chatterjee K, Oliu-Barton M, Saona Urmeneta RJ. 2024. Value-positivity for matrix games. Mathematics of Operations Research. 50(4), 2433–3282.","ama":"Chatterjee K, Oliu-Barton M, Saona Urmeneta RJ. Value-positivity for matrix games. <i>Mathematics of Operations Research</i>. 2024;50(4):2433-3282. doi:<a href=\"https://doi.org/10.1287/moor.2022.0332\">10.1287/moor.2022.0332</a>","apa":"Chatterjee, K., Oliu-Barton, M., &#38; Saona Urmeneta, R. J. (2024). Value-positivity for matrix games. <i>Mathematics of Operations Research</i>. Institute for Operations Research and the Management Sciences. <a href=\"https://doi.org/10.1287/moor.2022.0332\">https://doi.org/10.1287/moor.2022.0332</a>","ieee":"K. Chatterjee, M. Oliu-Barton, and R. J. Saona Urmeneta, “Value-positivity for matrix games,” <i>Mathematics of Operations Research</i>, vol. 50, no. 4. Institute for Operations Research and the Management Sciences, pp. 2433–3282, 2024.","mla":"Chatterjee, Krishnendu, et al. “Value-Positivity for Matrix Games.” <i>Mathematics of Operations Research</i>, vol. 50, no. 4, Institute for Operations Research and the Management Sciences, 2024, pp. 2433–3282, doi:<a href=\"https://doi.org/10.1287/moor.2022.0332\">10.1287/moor.2022.0332</a>.","short":"K. Chatterjee, M. Oliu-Barton, R.J. Saona Urmeneta, Mathematics of Operations Research 50 (2024) 2433–3282."},"related_material":{"record":[{"status":"public","relation":"dissertation_contains","id":"20234"}]},"_id":"18266","title":"Value-positivity for matrix games","month":"10"},{"status":"public","issue":"1","publisher":"Institute for Operations Research and the Management Sciences","day":"01","type":"journal_article","date_updated":"2026-04-07T12:31:21Z","year":"2022","oa_version":"Preprint","project":[{"name":"Game Theory","call_identifier":"FWF","_id":"25863FF4-B435-11E9-9278-68D0E5697425","grant_number":"S11407"}],"date_published":"2022-02-01T00:00:00Z","page":"100-119","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","month":"02","title":"Finite-memory strategies in POMDPs with long-run average objectives","_id":"9311","related_material":{"record":[{"id":"20234","status":"public","relation":"dissertation_contains"}]},"citation":{"chicago":"Chatterjee, Krishnendu, Raimundo J Saona Urmeneta, and Bruno Ziliotto. “Finite-Memory Strategies in POMDPs with Long-Run Average Objectives.” <i>Mathematics of Operations Research</i>. Institute for Operations Research and the Management Sciences, 2022. <a href=\"https://doi.org/10.1287/moor.2020.1116\">https://doi.org/10.1287/moor.2020.1116</a>.","ista":"Chatterjee K, Saona Urmeneta RJ, Ziliotto B. 2022. Finite-memory strategies in POMDPs with long-run average objectives. Mathematics of Operations Research. 47(1), 100–119.","ama":"Chatterjee K, Saona Urmeneta RJ, Ziliotto B. Finite-memory strategies in POMDPs with long-run average objectives. <i>Mathematics of Operations Research</i>. 2022;47(1):100-119. doi:<a href=\"https://doi.org/10.1287/moor.2020.1116\">10.1287/moor.2020.1116</a>","apa":"Chatterjee, K., Saona Urmeneta, R. J., &#38; Ziliotto, B. (2022). Finite-memory strategies in POMDPs with long-run average objectives. <i>Mathematics of Operations Research</i>. Institute for Operations Research and the Management Sciences. <a href=\"https://doi.org/10.1287/moor.2020.1116\">https://doi.org/10.1287/moor.2020.1116</a>","ieee":"K. Chatterjee, R. J. Saona Urmeneta, and B. Ziliotto, “Finite-memory strategies in POMDPs with long-run average objectives,” <i>Mathematics of Operations Research</i>, vol. 47, no. 1. Institute for Operations Research and the Management Sciences, pp. 100–119, 2022.","short":"K. Chatterjee, R.J. Saona Urmeneta, B. Ziliotto, Mathematics of Operations Research 47 (2022) 100–119.","mla":"Chatterjee, Krishnendu, et al. “Finite-Memory Strategies in POMDPs with Long-Run Average Objectives.” <i>Mathematics of Operations Research</i>, vol. 47, no. 1, Institute for Operations Research and the Management Sciences, 2022, pp. 100–19, doi:<a href=\"https://doi.org/10.1287/moor.2020.1116\">10.1287/moor.2020.1116</a>."},"article_processing_charge":"No","arxiv":1,"article_type":"original","doi":"10.1287/moor.2020.1116","publication_identifier":{"eissn":["1526-5471"],"issn":["0364-765X"]},"oa":1,"acknowledgement":"Partially supported by Austrian Science Fund (FWF) NFN Grant No RiSE/SHiNE S11407, by CONICYT Chile through grant PII 20150140, and by ECOS-CONICYT through grant C15E03.\r\n","main_file_link":[{"url":"https://arxiv.org/abs/1904.13360","open_access":"1"}],"intvolume":"        47","isi":1,"scopus_import":"1","publication":"Mathematics of Operations Research","keyword":["Management Science and Operations Research","General Mathematics","Computer Science Applications"],"author":[{"orcid":"0000-0002-4561-241X","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu","last_name":"Chatterjee","full_name":"Chatterjee, Krishnendu"},{"full_name":"Saona Urmeneta, Raimundo J","last_name":"Saona Urmeneta","id":"BD1DF4C4-D767-11E9-B658-BC13E6697425","first_name":"Raimundo J","orcid":"0000-0001-5103-038X"},{"last_name":"Ziliotto","full_name":"Ziliotto, Bruno","first_name":"Bruno"}],"quality_controlled":"1","volume":47,"abstract":[{"lang":"eng","text":"Partially observable Markov decision processes (POMDPs) are standard models for dynamic systems with probabilistic and nondeterministic behaviour in uncertain environments. We prove that in POMDPs with long-run average objective, the decision maker has approximately optimal strategies with finite memory. This implies notably that approximating the long-run value is recursively enumerable, as well as a weak continuity property of the value with respect to the transition function. "}],"publication_status":"published","language":[{"iso":"eng"}],"date_created":"2021-04-08T09:33:31Z","external_id":{"arxiv":["1904.13360"],"isi":["000731918100001"]},"department":[{"_id":"GradSch"},{"_id":"KrCh"}]}]