---
OA_type: closed access
_id: '17037'
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.
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].
article_processing_charge: No
article_type: original
author:
- first_name: Luc
  full_name: Attia, Luc
  last_name: Attia
- first_name: Miquel
  full_name: Oliu-Barton, Miquel
  last_name: Oliu-Barton
- first_name: Raimundo J
  full_name: Saona Urmeneta, Raimundo J
  id: BD1DF4C4-D767-11E9-B658-BC13E6697425
  last_name: Saona Urmeneta
  orcid: 0000-0001-5103-038X
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>.
  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.
  ista: Attia L, Oliu-Barton M, Saona Urmeneta RJ. 2025. Marginal values of a stochastic
    game. Mathematics of Operations Research. 50(1), 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>.
  short: L. Attia, M. Oliu-Barton, R.J. Saona Urmeneta, Mathematics of Operations
    Research 50 (2025) 482–505.
das_tickbox: '1'
date_created: 2024-05-22T11:41:14Z
date_published: 2025-02-01T00:00:00Z
date_updated: 2026-07-29T13:14:36Z
day: '01'
department:
- _id: GradSch
- _id: KrCh
doi: 10.1287/moor.2023.0297
ec_funded: 1
external_id:
  isi:
  - '001184648000001'
intvolume: '        50'
isi: 1
issue: '1'
language:
- iso: eng
month: '02'
oa_version: None
page: 482-505
project:
- _id: 0599E47C-7A3F-11EA-A408-12923DDC885E
  call_identifier: H2020
  grant_number: '863818'
  name: 'Formal Methods for Stochastic Models: Algorithms and Applications'
publication: Mathematics of Operations Research
publication_identifier:
  eissn:
  - 1526-5471
  issn:
  - 0364-765X
publication_status: published
publisher: Institute for Operations Research and the Management Sciences
quality_controlled: '1'
related_material:
  record:
  - id: '20234'
    relation: dissertation_contains
    status: public
scopus_import: '1'
status: public
title: Marginal values of a stochastic game
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 50
year: '2025'
...
---
OA_type: closed access
_id: '18266'
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.
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].
article_processing_charge: No
article_type: original
author:
- first_name: Krishnendu
  full_name: Chatterjee, Krishnendu
  id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
  last_name: Chatterjee
  orcid: 0000-0002-4561-241X
- first_name: Miquel
  full_name: Oliu-Barton, Miquel
  last_name: Oliu-Barton
- first_name: Raimundo J
  full_name: Saona Urmeneta, Raimundo J
  id: BD1DF4C4-D767-11E9-B658-BC13E6697425
  last_name: Saona Urmeneta
  orcid: 0000-0001-5103-038X
citation:
  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>
  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>.
  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.
  ista: Chatterjee K, Oliu-Barton M, Saona Urmeneta RJ. 2024. Value-positivity for
    matrix games. Mathematics of Operations Research. 50(4), 2433–3282.
  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.
corr_author: '1'
date_created: 2024-10-09T07:02:20Z
date_published: 2024-10-01T00:00:00Z
date_updated: 2026-07-29T13:14:36Z
day: '01'
department:
- _id: GradSch
- _id: KrCh
doi: 10.1287/moor.2022.0332
ec_funded: 1
external_id:
  isi:
  - '001328875900001'
intvolume: '        50'
isi: 1
issue: '4'
language:
- iso: eng
month: '10'
oa_version: None
page: 2433-3282
project:
- _id: 0599E47C-7A3F-11EA-A408-12923DDC885E
  call_identifier: H2020
  grant_number: '863818'
  name: 'Formal Methods for Stochastic Models: Algorithms and Applications'
publication: Mathematics of Operations Research
publication_identifier:
  eissn:
  - 1526-5471
  issn:
  - 0364-765X
publication_status: published
publisher: Institute for Operations Research and the Management Sciences
quality_controlled: '1'
related_material:
  record:
  - id: '20234'
    relation: dissertation_contains
    status: public
scopus_import: '1'
status: public
title: Value-positivity for matrix games
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 50
year: '2024'
...
---
_id: '9311'
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. '
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"
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Krishnendu
  full_name: Chatterjee, Krishnendu
  id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
  last_name: Chatterjee
  orcid: 0000-0002-4561-241X
- first_name: Raimundo J
  full_name: Saona Urmeneta, Raimundo J
  id: BD1DF4C4-D767-11E9-B658-BC13E6697425
  last_name: Saona Urmeneta
  orcid: 0000-0001-5103-038X
- first_name: Bruno
  full_name: Ziliotto, Bruno
  last_name: Ziliotto
citation:
  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>
  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>.
  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.
  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.
  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>.
  short: K. Chatterjee, R.J. Saona Urmeneta, B. Ziliotto, Mathematics of Operations
    Research 47 (2022) 100–119.
date_created: 2021-04-08T09:33:31Z
date_published: 2022-02-01T00:00:00Z
date_updated: 2026-07-29T13:14:36Z
day: '01'
department:
- _id: GradSch
- _id: KrCh
doi: 10.1287/moor.2020.1116
external_id:
  arxiv:
  - '1904.13360'
  isi:
  - '000731918100001'
intvolume: '        47'
isi: 1
issue: '1'
keyword:
- Management Science and Operations Research
- General Mathematics
- Computer Science Applications
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://arxiv.org/abs/1904.13360
month: '02'
oa: 1
oa_version: Preprint
page: 100-119
project:
- _id: 25863FF4-B435-11E9-9278-68D0E5697425
  call_identifier: FWF
  grant_number: S11407
  name: Game Theory
publication: Mathematics of Operations Research
publication_identifier:
  eissn:
  - 1526-5471
  issn:
  - 0364-765X
publication_status: published
publisher: Institute for Operations Research and the Management Sciences
quality_controlled: '1'
related_material:
  record:
  - id: '20234'
    relation: dissertation_contains
    status: public
scopus_import: '1'
status: public
title: Finite-memory strategies in POMDPs with long-run average objectives
type: journal_article
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 47
year: '2022'
...