---
OA_place: repository
OA_type: green
_id: '21722'
abstract:
- lang: eng
text: 'Partially observable Markov decision processes (POMDPs) are a central model
for uncertainty in sequential decision making. The most basic objective is the
reachability objective, where a target set must be eventually visited, and the
more general parity objectives can model all omega-regular specifications. For
such objectives, the computational analysis problems are the following: (a) qualitative
analysis that asks whether the objective can be satisfied with probability 1 (almost-sure
winning) or probability arbitrarily close to 1 (limit-sure winning); and (b) quantitative
analysis that asks for the approximation of the optimal probability of satisfying
the objective. For general POMDPs, almost-sure analysis for reachability objectives
is EXPTIME-complete, but limit-sure and quantitative analyses for reachability
objectives are undecidable; almost-sure, limit-sure, and quantitative analyses
for parity objectives are all undecidable. A special class of POMDPs, called revealing
POMDPs, has been studied recently in several works, and for this subclass the
almost-sure analysis for parity objectives was shown to be EXPTIME-complete. In
this work, we show that for revealing POMDPs the limit-sure analysis for parity
objectives is EXPTIME-complete, and even the quantitative analysis for parity
objectives can be achieved in EXPTIME.'
acknowledgement: "This work was partially supported by the ANRT under the French CIFRE
Ph.D program in collaboration between NyxAir and Paris-Dauphine University (Contract:
CIFRE N° 2022/0513), by the French Agence Nationale de la Recherche (ANR) under
reference ANR-21-CE40-\r\n0020 (CONVERGENCE project), by Austrian Science Fund (FWF)
10.55776/COE12, and by the ERC CoG 863818 (ForM-SMArt) grant."
article_processing_charge: No
arxiv: 1
author:
- first_name: Ali
full_name: Asadi, Ali
id: 02d96aae-000e-11ec-b801-cadd0a5eefbb
last_name: Asadi
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: David
full_name: Lurie, David
id: 579a6c20-34cf-11f1-acbd-8c2f19cdb4da
last_name: Lurie
- 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: 'Asadi A, Chatterjee K, Lurie D, Saona Urmeneta RJ. Revealing POMDPs: Qualitative
and quantitative analysis for parity objectives. In: Proceedings of the AAAI
Conference on Artificial Intelligence. Vol 40. Association for the Advancement
of Artificial Intelligence; 2026:36146-36154. doi:10.1609/aaai.v40i43.40932'
apa: 'Asadi, A., Chatterjee, K., Lurie, D., & Saona Urmeneta, R. J. (2026).
Revealing POMDPs: Qualitative and quantitative analysis for parity objectives.
In Proceedings of the AAAI Conference on Artificial Intelligence (Vol.
40, pp. 36146–36154). Singapore, Singapore: Association for the Advancement of
Artificial Intelligence. https://doi.org/10.1609/aaai.v40i43.40932'
chicago: 'Asadi, Ali, Krishnendu Chatterjee, David Lurie, and Raimundo J Saona Urmeneta.
“Revealing POMDPs: Qualitative and Quantitative Analysis for Parity Objectives.”
In Proceedings of the AAAI Conference on Artificial Intelligence, 40:36146–54.
Association for the Advancement of Artificial Intelligence, 2026. https://doi.org/10.1609/aaai.v40i43.40932.'
ieee: 'A. Asadi, K. Chatterjee, D. Lurie, and R. J. Saona Urmeneta, “Revealing POMDPs:
Qualitative and quantitative analysis for parity objectives,” in Proceedings
of the AAAI Conference on Artificial Intelligence, Singapore, Singapore, 2026,
vol. 40, no. 43, pp. 36146–36154.'
ista: 'Asadi A, Chatterjee K, Lurie D, Saona Urmeneta RJ. 2026. Revealing POMDPs:
Qualitative and quantitative analysis for parity objectives. Proceedings of the
AAAI Conference on Artificial Intelligence. AAAI: Conference on Artificial Intelligence
vol. 40, 36146–36154.'
mla: 'Asadi, Ali, et al. “Revealing POMDPs: Qualitative and Quantitative Analysis
for Parity Objectives.” Proceedings of the AAAI Conference on Artificial Intelligence,
vol. 40, no. 43, Association for the Advancement of Artificial Intelligence, 2026,
pp. 36146–54, doi:10.1609/aaai.v40i43.40932.'
short: A. Asadi, K. Chatterjee, D. Lurie, R.J. Saona Urmeneta, in:, Proceedings
of the AAAI Conference on Artificial Intelligence, Association for the Advancement
of Artificial Intelligence, 2026, pp. 36146–36154.
conference:
end_date: 2026-01-27
location: Singapore, Singapore
name: 'AAAI: Conference on Artificial Intelligence'
start_date: 2026-01-20
corr_author: '1'
date_created: 2026-04-12T22:01:52Z
date_published: 2026-03-14T00:00:00Z
date_updated: 2026-05-04T11:44:14Z
day: '14'
department:
- _id: KrCh
doi: 10.1609/aaai.v40i43.40932
ec_funded: 1
external_id:
arxiv:
- '2511.13134'
intvolume: ' 40'
issue: '43'
language:
- iso: eng
main_file_link:
- url: https://doi.org/10.48550/arXiv.2511.13134
month: '03'
oa_version: Preprint
page: 36146-36154
project:
- _id: 0599E47C-7A3F-11EA-A408-12923DDC885E
call_identifier: H2020
grant_number: '863818'
name: 'Formal Methods for Stochastic Models: Algorithms and Applications'
publication: Proceedings of the AAAI Conference on Artificial Intelligence
publication_identifier:
eissn:
- 2374-3468
issn:
- 2159-5399
publication_status: published
publisher: Association for the Advancement of Artificial Intelligence
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'Revealing POMDPs: Qualitative and quantitative analysis for parity objectives'
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 40
year: '2026'
...
---
OA_place: publisher
OA_type: gold
_id: '21320'
abstract:
- lang: eng
text: "Prophet inequalities are a central object of study in optimal stopping theory.
In the iid model, a gambler sees values in an online fashion, sampled independently
from a given distribution. Upon observing each value, the gambler either accepts
it as a reward, or irrevocably rejects it and proceeds to observe the next value.
The goal of the gambler, who cannot see the future, is to maximise the expected
value of the reward while competing against the expectation of a prophet (the
offline maximum). In other words, one seeks to maximise the gambler-to-prophet
ratio of the expectations. \r\nThis model has been studied with infinite, finite
and unknown number of values. When the gambler faces a random number of values,
the model is said to have a random horizon. We consider the model in which the
gambler is given a priori knowledge of the horizon’s distribution. Alijani et
al. (2020) designed a single-threshold algorithm achieving a ratio of 1/2 when
the random horizon has an increasing hazard rate and is independent of the values.
We prove that with a single threshold, a ratio of 1/2 is actually achievable for
several larger classes of horizon distributions, with the largest being known
as the \U0001D4A2 class in reliability theory. Moreover, we show that this does
not extend to its dual, the ̅\U0001D4A2 class (which includes the decreasing
hazard rate class), while it can be extended to low-variance horizons. Finally,
we construct the first example of a family of horizons, for which multiple thresholds
are necessary to achieve a nonzero ratio. We establish that the Secretary Problem
optimal stopping rule provides one such algorithm, paving the way towards the
study of the model beyond single-threshold algorithms."
acknowledgement: 'We would like to thank José Correa for his precious advice, Bruno
Ziliotto and Vasilis Livanos for early conversations. Giambartolomei, Giordano:
EPSRC grants EP/W005573/1 and EP/X021696/1. Mallmann-Trenn, Frederik: EPSRC grant
EP/W005573/1. Saona, Raimundo: ERC grant CoG 863818 (ForM-SMArt), ANID Chile grant
ACT210005, French Agence Nationale de la Recherche (ANR) grant ANR-21-CE40-0020
(CONVERGENCE), and Austrian Science Fund (FWF) grant 10.55776/COE12.'
alternative_title:
- LIPIcs
article_processing_charge: No
arxiv: 1
author:
- first_name: Giordano
full_name: Giambartolomei, Giordano
last_name: Giambartolomei
- first_name: Frederik
full_name: Mallmann-Trenn, Frederik
last_name: Mallmann-Trenn
- 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: 'Giambartolomei G, Mallmann-Trenn F, Saona Urmeneta RJ. IID prophet inequality
with random horizon: Going beyond increasing hazard rates. In: 52nd International
Colloquium on Automata, Languages, and Programming. Vol 334. Schloss Dagstuhl
- Leibniz-Zentrum für Informatik; 2025. doi:10.4230/LIPIcs.ICALP.2025.87'
apa: 'Giambartolomei, G., Mallmann-Trenn, F., & Saona Urmeneta, R. J. (2025).
IID prophet inequality with random horizon: Going beyond increasing hazard rates.
In 52nd International Colloquium on Automata, Languages, and Programming
(Vol. 334). Aarhus, Denmark: Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
https://doi.org/10.4230/LIPIcs.ICALP.2025.87'
chicago: 'Giambartolomei, Giordano, Frederik Mallmann-Trenn, and Raimundo J Saona
Urmeneta. “IID Prophet Inequality with Random Horizon: Going beyond Increasing
Hazard Rates.” In 52nd International Colloquium on Automata, Languages, and
Programming, Vol. 334. Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2025. https://doi.org/10.4230/LIPIcs.ICALP.2025.87.'
ieee: 'G. Giambartolomei, F. Mallmann-Trenn, and R. J. Saona Urmeneta, “IID prophet
inequality with random horizon: Going beyond increasing hazard rates,” in 52nd
International Colloquium on Automata, Languages, and Programming, Aarhus,
Denmark, 2025, vol. 334.'
ista: 'Giambartolomei G, Mallmann-Trenn F, Saona Urmeneta RJ. 2025. IID prophet
inequality with random horizon: Going beyond increasing hazard rates. 52nd International
Colloquium on Automata, Languages, and Programming. ICALP: Automata, Languages
and Programming, LIPIcs, vol. 334.'
mla: 'Giambartolomei, Giordano, et al. “IID Prophet Inequality with Random Horizon:
Going beyond Increasing Hazard Rates.” 52nd International Colloquium on Automata,
Languages, and Programming, vol. 334, Schloss Dagstuhl - Leibniz-Zentrum für
Informatik, 2025, doi:10.4230/LIPIcs.ICALP.2025.87.'
short: G. Giambartolomei, F. Mallmann-Trenn, R.J. Saona Urmeneta, in:, 52nd International
Colloquium on Automata, Languages, and Programming, Schloss Dagstuhl - Leibniz-Zentrum
für Informatik, 2025.
conference:
end_date: 2025-07-11
location: Aarhus, Denmark
name: 'ICALP: Automata, Languages and Programming'
start_date: 2025-07-08
date_created: 2026-02-18T10:44:14Z
date_published: 2025-06-30T00:00:00Z
date_updated: 2026-02-19T07:43:29Z
day: '30'
ddc:
- '000'
department:
- _id: KrCh
doi: 10.4230/LIPIcs.ICALP.2025.87
ec_funded: 1
external_id:
arxiv:
- '2407.11752'
file:
- access_level: open_access
checksum: 960110956c26a5cefadde8e47888bfbe
content_type: application/pdf
creator: dernst
date_created: 2026-02-19T07:41:55Z
date_updated: 2026-02-19T07:41:55Z
file_id: '21331'
file_name: 2025_ICALP_Giambartolomei.pdf
file_size: 876167
relation: main_file
success: 1
file_date_updated: 2026-02-19T07:41:55Z
has_accepted_license: '1'
intvolume: ' 334'
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
project:
- _id: 0599E47C-7A3F-11EA-A408-12923DDC885E
call_identifier: H2020
grant_number: '863818'
name: 'Formal Methods for Stochastic Models: Algorithms and Applications'
publication: 52nd International Colloquium on Automata, Languages, and Programming
publication_identifier:
isbn:
- '9783959773720'
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
status: public
title: 'IID prophet inequality with random horizon: Going beyond increasing hazard
rates'
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 334
year: '2025'
...
---
OA_place: publisher
OA_type: hybrid
PlanS_conform: '1'
_id: '19508'
abstract:
- lang: eng
text: We consider random two-player zero-sum dynamic games with perfect information
on a class of infinite directed graphs. Starting from a fixed vertex, the players
take turns to move a token along the edges of the graph. Every vertex is assigned
a payoff known in advance by both players. Every time the token visits a vertex,
Player 2 pays Player 1 the corresponding payoff. We consider a distribution over
such games by assigning i.i.d. payoffs to the vertices. On the one hand, for acyclic
directed graphs of bounded degree and sub-exponential expansion, we show that,
when the duration of the game tends to infinity, the value converges almost surely
to a constant at an exponential rate dominated in terms of the expansion. On the
other hand, for the infinite d-ary tree (that does not fall into the previous
class of graphs), we show convergence at a double-exponential rate.
acknowledgement: Open access funding provided by Institute of Science and Technology
(IST Austria). This work was supported by the French Agence Nationale de la Recherche
(ANR) under references ANR-21-CE40-0020 (CONVERGENCE project) and ANR-20-CE40-0002
(GrHyDy), by Fondecyt grant 1220174, by ANID Chile grant ACT210005, and by the ERC
CoG 863818 (ForM-SMArt) grant. This collaboration was mainly conducted during a
1-year visit of Bruno Ziliotto to the Center for Mathematical Modeling (CMM) at
University of Chile in 2023, under the IRL program of CNRS. This work was supported
by Fondation CFM pour la Recherche. This paper has also been funded by the Agence
Nationale de la Recherche under grant ANR-17-EURE-0010 (Investissements d’Avenir
program).
article_processing_charge: Yes (via OA deal)
article_type: original
author:
- first_name: Luc
full_name: Attia, Luc
last_name: Attia
- first_name: Lyuben
full_name: Lichev, Lyuben
id: 9aa8388e-d003-11ee-8458-c4c1d7447977
last_name: Lichev
- first_name: Dieter
full_name: Mitsche, Dieter
last_name: Mitsche
- 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: Attia L, Lichev L, Mitsche D, Saona Urmeneta RJ, Ziliotto B. Random zero-sum
dynamic games on infinite directed graphs. Dynamic Games and Applications.
2025;15:1517-1535. doi:10.1007/s13235-025-00636-4
apa: Attia, L., Lichev, L., Mitsche, D., Saona Urmeneta, R. J., & Ziliotto,
B. (2025). Random zero-sum dynamic games on infinite directed graphs. Dynamic
Games and Applications. Springer Nature. https://doi.org/10.1007/s13235-025-00636-4
chicago: Attia, Luc, Lyuben Lichev, Dieter Mitsche, Raimundo J Saona Urmeneta, and
Bruno Ziliotto. “Random Zero-Sum Dynamic Games on Infinite Directed Graphs.” Dynamic
Games and Applications. Springer Nature, 2025. https://doi.org/10.1007/s13235-025-00636-4.
ieee: L. Attia, L. Lichev, D. Mitsche, R. J. Saona Urmeneta, and B. Ziliotto, “Random
zero-sum dynamic games on infinite directed graphs,” Dynamic Games and Applications,
vol. 15. Springer Nature, pp. 1517–1535, 2025.
ista: Attia L, Lichev L, Mitsche D, Saona Urmeneta RJ, Ziliotto B. 2025. Random
zero-sum dynamic games on infinite directed graphs. Dynamic Games and Applications.
15, 1517–1535.
mla: Attia, Luc, et al. “Random Zero-Sum Dynamic Games on Infinite Directed Graphs.”
Dynamic Games and Applications, vol. 15, Springer Nature, 2025, pp. 1517–35,
doi:10.1007/s13235-025-00636-4.
short: L. Attia, L. Lichev, D. Mitsche, R.J. Saona Urmeneta, B. Ziliotto, Dynamic
Games and Applications 15 (2025) 1517–1535.
corr_author: '1'
date_created: 2025-04-06T22:01:32Z
date_published: 2025-11-01T00:00:00Z
date_updated: 2026-04-07T12:31:21Z
day: '01'
ddc:
- '000'
department:
- _id: MaKw
- _id: KrCh
doi: 10.1007/s13235-025-00636-4
ec_funded: 1
external_id:
isi:
- '001449708900001'
file:
- access_level: open_access
checksum: b3a1b7eef40c9ac2acf3fef563081694
content_type: application/pdf
creator: dernst
date_created: 2025-12-30T08:13:04Z
date_updated: 2025-12-30T08:13:04Z
file_id: '20891'
file_name: 2025_DynGamesAppl_Attia.pdf
file_size: 570994
relation: main_file
success: 1
file_date_updated: 2025-12-30T08:13:04Z
has_accepted_license: '1'
intvolume: ' 15'
isi: 1
language:
- iso: eng
month: '11'
oa: 1
oa_version: Published Version
page: 1517-1535
project:
- _id: 0599E47C-7A3F-11EA-A408-12923DDC885E
call_identifier: H2020
grant_number: '863818'
name: 'Formal Methods for Stochastic Models: Algorithms and Applications'
publication: Dynamic Games and Applications
publication_identifier:
eissn:
- 2153-0793
issn:
- 2153-0785
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
related_material:
record:
- id: '20234'
relation: dissertation_contains
status: public
scopus_import: '1'
status: public
title: Random zero-sum dynamic games on infinite directed graphs
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 15
year: '2025'
...
---
OA_place: repository
OA_type: green
_id: '19669'
abstract:
- lang: eng
text: 'We consider a class of optimization problems defined by a system of linear
equations with min and max operators. This class of optimization problems has
been studied under restrictive conditions, such as, (C1) the halting or stability
condition; (C2) the non-negative coefficients condition; (C3) the sum upto 1 condition;
and (C4) the only min or only max operator condition. Several seminal results
in the literature focus on special cases. For example, turn-based stochastic games
correspond to conditions C2 and C3; and Markov decision process to conditions
C2, C3, and C4. However, the systematic computational complexity study of all
the cases has not been explored, which we address in this work. Some highlights
of our results are: with conditions C2 and C4, and with conditions C3 and C4,
the problem is NP-complete, whereas with condition C1 only, the problem is in
UP intersects coUP. Finally, we establish the computational complexity of the
decision problem of checking the respective conditions.'
acknowledgement: This research was partially supported by the ERC CoG 863818 (ForM-SMArt)
grant and the Austrian Science Fund (FWF) 10.55776/COE12 grant.
article_processing_charge: No
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: Ruichen
full_name: Luo, Ruichen
id: b391db08-1ffe-11ee-8b67-d18ddcfb5a14
last_name: Luo
- 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: Jakub
full_name: Svoboda, Jakub
id: 130759D2-D7DD-11E9-87D2-DE0DE6697425
last_name: Svoboda
orcid: 0000-0002-1419-3267
citation:
ama: 'Chatterjee K, Luo R, Saona Urmeneta RJ, Svoboda J. Linear equations with min
and max operators: Computational complexity. In: Proceedings of the 39th AAAI
Conference on Artificial Intelligence. Vol 39. Association for the Advancement
of Artificial Intelligence; 2025:11150-11157. doi:10.1609/aaai.v39i11.33212'
apa: 'Chatterjee, K., Luo, R., Saona Urmeneta, R. J., & Svoboda, J. (2025).
Linear equations with min and max operators: Computational complexity. In Proceedings
of the 39th AAAI Conference on Artificial Intelligence (Vol. 39, pp. 11150–11157).
Philadelphia, PA, United States: Association for the Advancement of Artificial
Intelligence. https://doi.org/10.1609/aaai.v39i11.33212'
chicago: 'Chatterjee, Krishnendu, Ruichen Luo, Raimundo J Saona Urmeneta, and Jakub
Svoboda. “Linear Equations with Min and Max Operators: Computational Complexity.”
In Proceedings of the 39th AAAI Conference on Artificial Intelligence,
39:11150–57. Association for the Advancement of Artificial Intelligence, 2025.
https://doi.org/10.1609/aaai.v39i11.33212.'
ieee: 'K. Chatterjee, R. Luo, R. J. Saona Urmeneta, and J. Svoboda, “Linear equations
with min and max operators: Computational complexity,” in Proceedings of the
39th AAAI Conference on Artificial Intelligence, Philadelphia, PA, United
States, 2025, vol. 39, no. 11, pp. 11150–11157.'
ista: 'Chatterjee K, Luo R, Saona Urmeneta RJ, Svoboda J. 2025. Linear equations
with min and max operators: Computational complexity. Proceedings of the 39th
AAAI Conference on Artificial Intelligence. AAAI: Conference on Artificial Intelligence
vol. 39, 11150–11157.'
mla: 'Chatterjee, Krishnendu, et al. “Linear Equations with Min and Max Operators:
Computational Complexity.” Proceedings of the 39th AAAI Conference on Artificial
Intelligence, vol. 39, no. 11, Association for the Advancement of Artificial
Intelligence, 2025, pp. 11150–57, doi:10.1609/aaai.v39i11.33212.'
short: K. Chatterjee, R. Luo, R.J. Saona Urmeneta, J. Svoboda, in:, Proceedings
of the 39th AAAI Conference on Artificial Intelligence, Association for the Advancement
of Artificial Intelligence, 2025, pp. 11150–11157.
conference:
end_date: 2025-03-04
location: Philadelphia, PA, United States
name: 'AAAI: Conference on Artificial Intelligence'
start_date: 2025-02-25
corr_author: '1'
date_created: 2025-05-11T22:02:40Z
date_published: 2025-04-11T00:00:00Z
date_updated: 2025-05-12T09:42:09Z
day: '11'
department:
- _id: KrCh
doi: 10.1609/aaai.v39i11.33212
ec_funded: 1
external_id:
arxiv:
- '2412.12228'
intvolume: ' 39'
issue: '11'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.48550/arXiv.2412.12228
month: '04'
oa: 1
oa_version: Preprint
page: 11150-11157
project:
- _id: 0599E47C-7A3F-11EA-A408-12923DDC885E
call_identifier: H2020
grant_number: '863818'
name: 'Formal Methods for Stochastic Models: Algorithms and Applications'
publication: Proceedings of the 39th AAAI Conference on Artificial Intelligence
publication_identifier:
eissn:
- 2374-3468
issn:
- 2159-5399
publication_status: published
publisher: Association for the Advancement of Artificial Intelligence
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'Linear equations with min and max operators: Computational complexity'
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 39
year: '2025'
...
---
OA_place: publisher
OA_type: hybrid
_id: '19740'
abstract:
- lang: eng
text: Two standard models for probabilistic systems are Markov chains (MCs) and
Markov decision processes (MDPs). Classic objectives for such probabilistic models
for control and planning problems are reachability and stochastic shortest path.
The widely studied algorithmic approach for these problems is the Value Iteration
(VI) algorithm which iteratively applies local updates called Bellman updates.
There are many practical approaches for VI in the literature but they all require
exponentially many Bellman updates for MCs in the worst case. A preprocessing
step is an algorithm that is discrete, graph-theoretical, and requires linear
space. An important open question is whether, after a polynomial-time preprocessing,
VI can be achieved with sub-exponentially many Bellman updates. In this work,
we present a new approach for VI based on guessing values. Our theoretical contributions
are twofold. First, for MCs, we present an almost-linear-time preprocessing algorithm
after which, along with guessing values, VI requires only subexponentially many
Bellman updates. Second, we present an improved analysis of the speed of convergence
of VI for MDPs. Finally, we present a practical algorithm for MDPs based on our
new approach. Experimental results show that our approach provides a considerable
improvement over existing VI-based approaches on several benchmark examples from
the literature.
acknowledgement: This research was partially supported by the ERC CoG 863818 (ForM-SMArt)
grant and Austrian Science Fund (FWF) 10.55776/COE12 grant.
alternative_title:
- LNCS
article_processing_charge: No
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: Mahdi
full_name: Jafariraviz, Mahdi
last_name: Jafariraviz
- 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: Jakub
full_name: Svoboda, Jakub
id: 130759D2-D7DD-11E9-87D2-DE0DE6697425
last_name: Svoboda
orcid: 0000-0002-1419-3267
citation:
ama: 'Chatterjee K, Jafariraviz M, Saona Urmeneta RJ, Svoboda J. Value iteration
with guessing for Markov chains and Markov decision processes. In: 31st International
Conference on Tools and Algorithms for the Construction and Analysis of Systems.
Vol 15697. Springer Nature; 2025:217-236. doi:10.1007/978-3-031-90653-4_11'
apa: 'Chatterjee, K., Jafariraviz, M., Saona Urmeneta, R. J., & Svoboda, J.
(2025). Value iteration with guessing for Markov chains and Markov decision processes.
In 31st International Conference on Tools and Algorithms for the Construction
and Analysis of Systems (Vol. 15697, pp. 217–236). Hamilton, ON, Canada: Springer
Nature. https://doi.org/10.1007/978-3-031-90653-4_11'
chicago: Chatterjee, Krishnendu, Mahdi Jafariraviz, Raimundo J Saona Urmeneta, and
Jakub Svoboda. “Value Iteration with Guessing for Markov Chains and Markov Decision
Processes.” In 31st International Conference on Tools and Algorithms for the
Construction and Analysis of Systems, 15697:217–36. Springer Nature, 2025.
https://doi.org/10.1007/978-3-031-90653-4_11.
ieee: K. Chatterjee, M. Jafariraviz, R. J. Saona Urmeneta, and J. Svoboda, “Value
iteration with guessing for Markov chains and Markov decision processes,” in 31st
International Conference on Tools and Algorithms for the Construction and Analysis
of Systems, Hamilton, ON, Canada, 2025, vol. 15697, pp. 217–236.
ista: 'Chatterjee K, Jafariraviz M, Saona Urmeneta RJ, Svoboda J. 2025. Value iteration
with guessing for Markov chains and Markov decision processes. 31st International
Conference on Tools and Algorithms for the Construction and Analysis of Systems.
TACAS: Tools and Algorithms for the Construction and Analysis of Systems, LNCS,
vol. 15697, 217–236.'
mla: Chatterjee, Krishnendu, et al. “Value Iteration with Guessing for Markov Chains
and Markov Decision Processes.” 31st International Conference on Tools and
Algorithms for the Construction and Analysis of Systems, vol. 15697, Springer
Nature, 2025, pp. 217–36, doi:10.1007/978-3-031-90653-4_11.
short: K. Chatterjee, M. Jafariraviz, R.J. Saona Urmeneta, J. Svoboda, in:, 31st
International Conference on Tools and Algorithms for the Construction and Analysis
of Systems, Springer Nature, 2025, pp. 217–236.
conference:
end_date: 2025-05-08
location: Hamilton, ON, Canada
name: 'TACAS: Tools and Algorithms for the Construction and Analysis of Systems'
start_date: 2025-05-03
corr_author: '1'
date_created: 2025-05-25T22:17:06Z
date_published: 2025-05-01T00:00:00Z
date_updated: 2025-06-02T07:35:06Z
day: '01'
ddc:
- '000'
department:
- _id: KrCh
doi: 10.1007/978-3-031-90653-4_11
ec_funded: 1
external_id:
arxiv:
- '2505.06769'
file:
- access_level: open_access
checksum: 45da6efbcbed20aada16c48c8e55e2d6
content_type: application/pdf
creator: dernst
date_created: 2025-06-02T07:31:12Z
date_updated: 2025-06-02T07:31:12Z
file_id: '19767'
file_name: 2025_TACAS_Chatterjee.pdf
file_size: 557481
relation: main_file
success: 1
file_date_updated: 2025-06-02T07:31:12Z
has_accepted_license: '1'
intvolume: ' 15697'
language:
- iso: eng
month: '05'
oa: 1
oa_version: Published Version
page: 217-236
project:
- _id: 0599E47C-7A3F-11EA-A408-12923DDC885E
call_identifier: H2020
grant_number: '863818'
name: 'Formal Methods for Stochastic Models: Algorithms and Applications'
publication: 31st International Conference on Tools and Algorithms for the Construction
and Analysis of Systems
publication_identifier:
eissn:
- 1611-3349
isbn:
- '9783031906527'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Value iteration with guessing for Markov chains and Markov decision processes
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 15697
year: '2025'
...
---
OA_place: publisher
OA_type: diamond
_id: '20297'
abstract:
- lang: eng
text: "A standard model that arises in several applications in sequential decision-making
is partially observable Markov decision processes (POMDPs) where a decision-making
agent interacts with an uncertain environment. A basic objective in POMDPs is
the reachability objective, where given a target set of states, the goal is to
eventually arrive at one of them.\r\n\r\nThe limit-sure problem asks whether reachability
can be ensured with probability arbitrarily close to 1. In general, the limit-sure
reachability problem for POMDPs is undecidable. However, in many practical cases,
the most relevant question is the existence of policies with a small amount of
memory. In this work, we study the limit-sure reachability problem for POMDPs
with a fixed amount of memory. We establish that the computational complexity
of the problem is NP-complete."
acknowledgement: This research was partially supported by Austrian Science Fund (FWF)
10.55776/COE12, the support of the French Agence Nationale de la Recherche (ANR)
under reference ANR-21-CE40-0020 (CONVERGENCE project), and the ERC CoG 863818 (ForM-SMArt)
grant.
alternative_title:
- PMLR
article_processing_charge: No
arxiv: 1
author:
- first_name: Ali
full_name: Asadi, Ali
id: 02d96aae-000e-11ec-b801-cadd0a5eefbb
last_name: Asadi
- 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: Ali
full_name: Shafiee, Ali
id: 2783031a-7378-11f0-b2d0-f17f1db2ebad
last_name: Shafiee
citation:
ama: 'Asadi A, Chatterjee K, Saona Urmeneta RJ, Shafiee A. Limit-sure reachability
for small memory policies in POMDPs is NP-complete. In: The 41st Conference
on Uncertainty in Artificial Intelligence. Vol 286. ML Research Press; 2025:238-247.'
apa: 'Asadi, A., Chatterjee, K., Saona Urmeneta, R. J., & Shafiee, A. (2025).
Limit-sure reachability for small memory policies in POMDPs is NP-complete. In
The 41st Conference on Uncertainty in Artificial Intelligence (Vol. 286,
pp. 238–247). Rio de Janeiro, Brazil: ML Research Press.'
chicago: Asadi, Ali, Krishnendu Chatterjee, Raimundo J Saona Urmeneta, and Ali Shafiee.
“Limit-Sure Reachability for Small Memory Policies in POMDPs Is NP-Complete.”
In The 41st Conference on Uncertainty in Artificial Intelligence, 286:238–47.
ML Research Press, 2025.
ieee: A. Asadi, K. Chatterjee, R. J. Saona Urmeneta, and A. Shafiee, “Limit-sure
reachability for small memory policies in POMDPs is NP-complete,” in The 41st
Conference on Uncertainty in Artificial Intelligence, Rio de Janeiro, Brazil,
2025, vol. 286, pp. 238–247.
ista: 'Asadi A, Chatterjee K, Saona Urmeneta RJ, Shafiee A. 2025. Limit-sure reachability
for small memory policies in POMDPs is NP-complete. The 41st Conference on Uncertainty
in Artificial Intelligence. UAI: Conference on Uncertainty in Artificial Intelligence,
PMLR, vol. 286, 238–247.'
mla: Asadi, Ali, et al. “Limit-Sure Reachability for Small Memory Policies in POMDPs
Is NP-Complete.” The 41st Conference on Uncertainty in Artificial Intelligence,
vol. 286, ML Research Press, 2025, pp. 238–47.
short: A. Asadi, K. Chatterjee, R.J. Saona Urmeneta, A. Shafiee, in:, The 41st Conference
on Uncertainty in Artificial Intelligence, ML Research Press, 2025, pp. 238–247.
conference:
end_date: 2025-07-25
location: Rio de Janeiro, Brazil
name: 'UAI: Conference on Uncertainty in Artificial Intelligence'
start_date: 2025-07-21
corr_author: '1'
date_created: 2025-09-07T22:01:34Z
date_published: 2025-07-01T00:00:00Z
date_updated: 2025-09-09T08:21:45Z
day: '01'
ddc:
- '000'
department:
- _id: KrCh
- _id: GradSch
ec_funded: 1
external_id:
arxiv:
- '2412.00941'
file:
- access_level: open_access
checksum: 1a37ebe7ba73ab6985765bf0d17a0acc
content_type: application/pdf
creator: dernst
date_created: 2025-09-09T08:19:41Z
date_updated: 2025-09-09T08:19:41Z
file_id: '20315'
file_name: 2025_UAI_AsadiAli.pdf
file_size: 307458
relation: main_file
success: 1
file_date_updated: 2025-09-09T08:19:41Z
has_accepted_license: '1'
intvolume: ' 286'
language:
- iso: eng
month: '07'
oa: 1
oa_version: Published Version
page: 238-247
project:
- _id: 0599E47C-7A3F-11EA-A408-12923DDC885E
call_identifier: H2020
grant_number: '863818'
name: 'Formal Methods for Stochastic Models: Algorithms and Applications'
publication: The 41st Conference on Uncertainty in Artificial Intelligence
publication_identifier:
eissn:
- 2640-3498
publication_status: published
publisher: ML Research Press
quality_controlled: '1'
scopus_import: '1'
status: public
title: Limit-sure reachability for small memory policies in POMDPs is NP-complete
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 286
year: '2025'
...
---
OA_place: publisher
_id: '20234'
abstract:
- lang: eng
text: "Game Theory is the mathematical formalization of social dynamics - systems
where agents interact over time and the evolution of the state of the system depends
on the decisions of every player. \r\nThis thesis takes the perspective of a single
player and focuses on what they can guarantee in the worst case over the behavior
of other players.\r\nIn other words, we consider that the objective of every other
player in the game is exactly the opposite to the player.\r\nWe focus on sustained
interactions over time, where the players repeatedly obtain quantitative rewards
over time, and they are interested in maximizing their long-term performance.\t\r\nFormally,
this thesis focuses on zero-sum games with the liminf average objective.\r\nTwo
fundamental questions that Game Theory aims to answer are the following.\r\n\r\n1.
How much can a player guarantee to obtain after the interaction?\r\n\r\n2. How
to act in order to obtain the previously mentioned guarantee?\r\n\r\nThese questions
are formalized by the concepts of \"value\" and \"optimal strategies\". \t\r\nWe
study their properties on games that exhibit one or more of the following properties.
\r\n\r\n1. Partial Observation: \r\nthe players can not perfectly observe the
current state of the system during the game. We consider the model of (finite)
Partially Observable Markov Decision Processes and prove that finite-memory strategies
are sufficient to approximately guarantee the value.\r\n\r\n2. Perturbed Description:
\r\nthe formal description of the game is perturbed by a small parameter.\r\nWe
consider the model of (finite) Perturbed Matrix Games, and provide algorithms
to check various robustness properties and to compute the parameterized value
and optimal strategies.\r\n\r\n3. Stochastic Transitions: \r\nthe actions of the
players determine the behavior of the evolution of the system, described as a
probability distribution over the next state.\r\nWe consider the model of (finite)
Perturbed Stochastic Games and provide formulas for the marginal value.\r\n\r\n4.
Infinite States: \r\nthe system can be in infinitely many states.\r\nWe consider
the model of Random Dynamic Games on a class of infinite graphs, prove the existence
of the value, and quantify the concentration of finite-horizon values."
acknowledgement: "Funding sources The works included in this thesis were partially
supported by:\r\n• Austrian Science Fund (FWF), grants 10.55776/COE12 and No RiSE/SHiNE
S11407,\r\n• French Agence Nationale de la Recherche (ANR), grants ANR-21-CE40-0020
(CONVERGENCE) and ANR-20-CE40-0002 (GrHyDy),\r\n• Fondation Mathématique Jaques
Hadamard, grant PGMO RSG 2018-0031H,\r\n• European Research Council (ERC), Consolidator
grant 863818 (ForM-SMArt),\r\n• Agencia Nacional de Investigación y Desarrollo (ANID
Chile), grant ACT210005,\r\n• Fondo Nacional de Desarrollo Científico y Tecnológico
(Fondecyt Chile), grant 1220174,\r\n• Comisión Nacional de Investigación Científica
y Tecnológica (CONICYT Chile), grant\r\nPII 20150140,\r\n• Evaluation-orientation
de la Coopération Scientifique and Comisión Nacional de Investigación Científica
y Tecnológica (ECOS-CONICYT), grant C15E03,\r\n• European Cooperation in Science
and Technology (E-COST), grants CA16228 - European\r\nNetwork for Game Theory (GAMENET)
and E-COST-GRANT-CA16228-c5a69859.\r\n"
alternative_title:
- ISTA Thesis
article_processing_charge: No
author:
- 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: 'Saona Urmeneta RJ. Robustness of solutions in game theory : Values and strategies
in partially observable, perturbed, stochastic, and infinite games. 2025. doi:10.15479/AT-ISTA-20234'
apa: 'Saona Urmeneta, R. J. (2025). Robustness of solutions in game theory :
Values and strategies in partially observable, perturbed, stochastic, and infinite
games. Institute of Science and Technology Austria. https://doi.org/10.15479/AT-ISTA-20234'
chicago: 'Saona Urmeneta, Raimundo J. “Robustness of Solutions in Game Theory :
Values and Strategies in Partially Observable, Perturbed, Stochastic, and Infinite
Games.” Institute of Science and Technology Austria, 2025. https://doi.org/10.15479/AT-ISTA-20234.'
ieee: 'R. J. Saona Urmeneta, “Robustness of solutions in game theory : Values and
strategies in partially observable, perturbed, stochastic, and infinite games,”
Institute of Science and Technology Austria, 2025.'
ista: 'Saona Urmeneta RJ. 2025. Robustness of solutions in game theory : Values
and strategies in partially observable, perturbed, stochastic, and infinite games.
Institute of Science and Technology Austria.'
mla: 'Saona Urmeneta, Raimundo J. Robustness of Solutions in Game Theory : Values
and Strategies in Partially Observable, Perturbed, Stochastic, and Infinite Games.
Institute of Science and Technology Austria, 2025, doi:10.15479/AT-ISTA-20234.'
short: 'R.J. Saona Urmeneta, Robustness of Solutions in Game Theory : Values and
Strategies in Partially Observable, Perturbed, Stochastic, and Infinite Games,
Institute of Science and Technology Austria, 2025.'
corr_author: '1'
date_created: 2025-08-27T14:00:13Z
date_published: 2025-08-27T00:00:00Z
date_updated: 2026-07-22T06:37:12Z
day: '27'
ddc:
- '519'
degree_awarded: PhD
department:
- _id: GradSch
- _id: KrCh
doi: 10.15479/AT-ISTA-20234
ec_funded: 1
file:
- access_level: open_access
checksum: 394a651f7de7085e509ef856ffe7bd97
content_type: application/pdf
creator: rsaonaur
date_created: 2025-08-28T14:47:07Z
date_updated: 2025-08-28T14:47:07Z
file_id: '20240'
file_name: 2025_Saona_Raimundo_Thesis.pdf
file_size: 1503623
relation: main_file
success: 1
- access_level: closed
checksum: 09fb2633e66aac80433d373f4180c5b4
content_type: application/zip
creator: rsaonaur
date_created: 2025-08-28T14:47:12Z
date_updated: 2025-08-28T14:47:12Z
file_id: '20241'
file_name: 2025_Saona_Raimundo_Thesis.zip
file_size: 622747
relation: source_file
file_date_updated: 2025-08-28T14:47:12Z
has_accepted_license: '1'
language:
- iso: eng
month: '08'
oa: 1
oa_version: Published Version
page: '125'
project:
- _id: 25863FF4-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S11407
name: Game Theory
- _id: 0599E47C-7A3F-11EA-A408-12923DDC885E
call_identifier: H2020
grant_number: '863818'
name: 'Formal Methods for Stochastic Models: Algorithms and Applications'
publication_identifier:
issn:
- 2663-337X
publication_status: published
publisher: Institute of Science and Technology Austria
related_material:
record:
- id: '9311'
relation: part_of_dissertation
status: public
- id: '18266'
relation: part_of_dissertation
status: public
- id: '19508'
relation: part_of_dissertation
status: public
- id: '17037'
relation: part_of_dissertation
status: public
status: public
supervisor:
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
title: 'Robustness of solutions in game theory : Values and strategies in partially
observable, perturbed, stochastic, and infinite games'
type: dissertation
user_id: ba8df636-2132-11f1-aed0-ed93e2281fdd
year: '2025'
...
---
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. Mathematics of Operations Research. 2025;50(1):482-505. doi:10.1287/moor.2023.0297
apa: Attia, L., Oliu-Barton, M., & Saona Urmeneta, R. J. (2025). Marginal values
of a stochastic game. Mathematics of Operations Research. Institute for
Operations Research and the Management Sciences. https://doi.org/10.1287/moor.2023.0297
chicago: Attia, Luc, Miquel Oliu-Barton, and Raimundo J Saona Urmeneta. “Marginal
Values of a Stochastic Game.” Mathematics of Operations Research. Institute
for Operations Research and the Management Sciences, 2025. https://doi.org/10.1287/moor.2023.0297.
ieee: L. Attia, M. Oliu-Barton, and R. J. Saona Urmeneta, “Marginal values of a
stochastic game,” Mathematics of Operations Research, 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.” Mathematics of
Operations Research, vol. 50, no. 1, Institute for Operations Research and
the Management Sciences, 2025, pp. 482–505, doi:10.1287/moor.2023.0297.
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-22T06:37:13Z
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'
...
---
_id: '17098'
abstract:
- lang: eng
text: Turn-based discounted-sum games are two-player zero-sum games played on finite
directed graphs. The vertices of the graph are partitioned between player 1 and
player 2. Plays are infinite walks on the graph where the next vertex is decided
by a player that owns the current vertex. Each edge is assigned an integer weight
and the payoff of a play is the discounted-sum of the weights of the play. The
goal of player 1 is to maximize the discounted-sum payoff against the adversarial
player 2. These games lie in NP ∩ coNP and are among the rare combinatorial problems
that belong to this complexity class and the existence of a polynomial-time algorithm
is a major open question. Since breaking the general exponential barrier has been
a challenging problem, faster parameterized algorithms have been considered. If
the discount factor is expressed in unary, then discounted-sum games can be solved
in polynomial time. However, if the discount factor is arbitrary (or expressed
in binary), but the weights are in unary, none of the existing approaches yield
a sub-exponential bound. Our main result is a new analysis technique for a classical
algorithm (namely, the strategy iteration algorithm) that present a new runtime
bound which is [EQUATION] for game graphs with n vertices and absolute weights
of at most W. In particular, our result yields a deterministic sub-exponential
bound for games with weights that are constant or represented in unary.
acknowledgement: "This research was partially supported by the ERC CoG 863818 (ForM-SMArt)
grant.\r\n"
article_number: '6'
article_processing_charge: No
arxiv: 1
author:
- first_name: Ali
full_name: Asadi, Ali
id: 02d96aae-000e-11ec-b801-cadd0a5eefbb
last_name: Asadi
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Jakub
full_name: Svoboda, Jakub
id: 130759D2-D7DD-11E9-87D2-DE0DE6697425
last_name: Svoboda
orcid: 0000-0002-1419-3267
- 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: 'Asadi A, Chatterjee K, Svoboda J, Saona Urmeneta RJ. Deterministic sub-exponential
algorithm for discounted-sum games with unary weights. In: 39th Annual ACM/IEEE
Symposium on Logic in Computer Science. Association for Computing Machinery;
2024. doi:10.1145/3661814.3662080'
apa: 'Asadi, A., Chatterjee, K., Svoboda, J., & Saona Urmeneta, R. J. (2024).
Deterministic sub-exponential algorithm for discounted-sum games with unary weights.
In 39th Annual ACM/IEEE Symposium on Logic in Computer Science. Tallinn,
Estonia: Association for Computing Machinery. https://doi.org/10.1145/3661814.3662080'
chicago: Asadi, Ali, Krishnendu Chatterjee, Jakub Svoboda, and Raimundo J Saona
Urmeneta. “Deterministic Sub-Exponential Algorithm for Discounted-Sum Games with
Unary Weights.” In 39th Annual ACM/IEEE Symposium on Logic in Computer Science.
Association for Computing Machinery, 2024. https://doi.org/10.1145/3661814.3662080.
ieee: A. Asadi, K. Chatterjee, J. Svoboda, and R. J. Saona Urmeneta, “Deterministic
sub-exponential algorithm for discounted-sum games with unary weights,” in 39th
Annual ACM/IEEE Symposium on Logic in Computer Science, Tallinn, Estonia,
2024.
ista: 'Asadi A, Chatterjee K, Svoboda J, Saona Urmeneta RJ. 2024. Deterministic
sub-exponential algorithm for discounted-sum games with unary weights. 39th Annual
ACM/IEEE Symposium on Logic in Computer Science. LICS: Logic in Computer Science,
6.'
mla: Asadi, Ali, et al. “Deterministic Sub-Exponential Algorithm for Discounted-Sum
Games with Unary Weights.” 39th Annual ACM/IEEE Symposium on Logic in Computer
Science, 6, Association for Computing Machinery, 2024, doi:10.1145/3661814.3662080.
short: A. Asadi, K. Chatterjee, J. Svoboda, R.J. Saona Urmeneta, in:, 39th Annual
ACM/IEEE Symposium on Logic in Computer Science, Association for Computing Machinery,
2024.
conference:
end_date: 2024-07-11
location: Tallinn, Estonia
name: 'LICS: Logic in Computer Science'
start_date: 2024-07-08
corr_author: '1'
date_created: 2024-06-03T07:43:15Z
date_published: 2024-07-08T00:00:00Z
date_updated: 2025-09-08T07:44:29Z
day: '08'
department:
- _id: KrCh
doi: 10.1145/3661814.3662080
ec_funded: 1
external_id:
arxiv:
- '2405.02479'
isi:
- '001275042100006'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.48550/arXiv.2405.02479
month: '07'
oa: 1
oa_version: Preprint
project:
- _id: 0599E47C-7A3F-11EA-A408-12923DDC885E
call_identifier: H2020
grant_number: '863818'
name: 'Formal Methods for Stochastic Models: Algorithms and Applications'
publication: 39th Annual ACM/IEEE Symposium on Logic in Computer Science
publication_identifier:
eissn:
- 1043-6871
isbn:
- '9798400706608'
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
scopus_import: '1'
status: public
title: Deterministic sub-exponential algorithm for discounted-sum games with unary
weights
type: conference
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
year: '2024'
...
---
OA_place: publisher
OA_type: gold
_id: '17099'
abstract:
- lang: eng
text: "We study two-player zero-sum concurrent stochastic games with finite state
and action space played for an infinite number of steps. In every step, the two
players simultaneously and independently choose an action. Given the current state
and the chosen actions, the next state is obtained according to a stochastic transition
function. An objective is a measurable function on plays (or infinite trajectories)
of the game, and the value for an objective is the maximal expectation that the
player can guarantee against the adversarial player. We consider: (a) stateful-discounted
objectives, which are similar to the classical discounted-sum objectives, but
states are associated with different discount factors rather than a single discount
factor; and (b) parity objectives, which are a canonical representation for ω-regular
objectives. For stateful-discounted objectives, given an ordering of the discount
factors, the limit value is the limit of the value of the stateful-discounted
objectives, as the discount factors approach zero according to the given order.\r\nThe
computational problem we consider is the approximation of the value within an
arbitrary\r\nadditive error. The above problem is known to be in EXPSPACE for
the limit value of statefuldiscounted objectives and in PSPACE for parity objectives.
The best-known algorithms for both the above problems are at least exponential
time, with an exponential dependence on the number of states and actions. Our
main results for the value approximation problem for the limit value of stateful-discounted
objectives and parity objectives are as follows: (a) we establish TFNP[NP] complexity;
and (b) we present algorithms that improve the dependency on the number of actions
in the exponent from linear to logarithmic. In particular, if the number of states
is constant, our algorithms run in polynomial time."
acknowledgement: "This research was partially supported by ERC CoG 863818 (ForM-SMArt),
Austrian\r\nScience Fund (FWF) 10.55776/COE12, and French Agence Nationale de la
Recherche (ANR)\r\nANR-21-CE40-0020 (CONVERGENCE project)"
alternative_title:
- LIPIcs
article_number: '5'
article_processing_charge: No
arxiv: 1
author:
- first_name: Ali
full_name: Asadi, Ali
id: 02d96aae-000e-11ec-b801-cadd0a5eefbb
last_name: Asadi
- 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: Jakub
full_name: Svoboda, Jakub
id: 130759D2-D7DD-11E9-87D2-DE0DE6697425
last_name: Svoboda
orcid: 0000-0002-1419-3267
citation:
ama: 'Asadi A, Chatterjee K, Saona Urmeneta RJ, Svoboda J. Concurrent stochastic
games with stateful-discounted and parity objectives: Complexity and algorithms.
In: 44th IARCS Annual Conference on Foundations of Software Technology and
Theoretical Computer Science. Vol 323. Schloss Dagstuhl - Leibniz-Zentrum
für Informatik; 2024. doi:10.4230/LIPIcs.FSTTCS.2024.5'
apa: 'Asadi, A., Chatterjee, K., Saona Urmeneta, R. J., & Svoboda, J. (2024).
Concurrent stochastic games with stateful-discounted and parity objectives: Complexity
and algorithms. In 44th IARCS Annual Conference on Foundations of Software
Technology and Theoretical Computer Science (Vol. 323). Gujarat, India: Schloss
Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.FSTTCS.2024.5'
chicago: 'Asadi, Ali, Krishnendu Chatterjee, Raimundo J Saona Urmeneta, and Jakub
Svoboda. “Concurrent Stochastic Games with Stateful-Discounted and Parity Objectives:
Complexity and Algorithms.” In 44th IARCS Annual Conference on Foundations
of Software Technology and Theoretical Computer Science, Vol. 323. Schloss
Dagstuhl - Leibniz-Zentrum für Informatik, 2024. https://doi.org/10.4230/LIPIcs.FSTTCS.2024.5.'
ieee: 'A. Asadi, K. Chatterjee, R. J. Saona Urmeneta, and J. Svoboda, “Concurrent
stochastic games with stateful-discounted and parity objectives: Complexity and
algorithms,” in 44th IARCS Annual Conference on Foundations of Software Technology
and Theoretical Computer Science, Gujarat, India, 2024, vol. 323.'
ista: 'Asadi A, Chatterjee K, Saona Urmeneta RJ, Svoboda J. 2024. Concurrent stochastic
games with stateful-discounted and parity objectives: Complexity and algorithms.
44th IARCS Annual Conference on Foundations of Software Technology and Theoretical
Computer Science. FSTTCS: Foundations of Software Technology and Theoretical Computer
Science, LIPIcs, vol. 323, 5.'
mla: 'Asadi, Ali, et al. “Concurrent Stochastic Games with Stateful-Discounted and
Parity Objectives: Complexity and Algorithms.” 44th IARCS Annual Conference
on Foundations of Software Technology and Theoretical Computer Science, vol.
323, 5, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024, doi:10.4230/LIPIcs.FSTTCS.2024.5.'
short: A. Asadi, K. Chatterjee, R.J. Saona Urmeneta, J. Svoboda, in:, 44th IARCS
Annual Conference on Foundations of Software Technology and Theoretical Computer
Science, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024.
conference:
end_date: 2024-12-18
location: Gujarat, India
name: 'FSTTCS: Foundations of Software Technology and Theoretical Computer Science'
start_date: 2024-12-16
corr_author: '1'
date_created: 2024-06-03T07:44:27Z
date_published: 2024-12-05T00:00:00Z
date_updated: 2025-12-02T13:40:52Z
day: '05'
ddc:
- '000'
department:
- _id: KrCh
doi: 10.4230/LIPIcs.FSTTCS.2024.5
ec_funded: 1
external_id:
arxiv:
- '2405.02486'
isi:
- '001537516500005'
file:
- access_level: open_access
checksum: 5b544ab4692b93300b404435c036ddd4
content_type: application/pdf
creator: dernst
date_created: 2025-01-08T09:49:31Z
date_updated: 2025-01-08T09:49:31Z
file_id: '18777'
file_name: 2024_LIPIcs_Asadi.pdf
file_size: 847960
relation: main_file
success: 1
file_date_updated: 2025-01-08T09:49:31Z
has_accepted_license: '1'
intvolume: ' 323'
isi: 1
language:
- iso: eng
month: '12'
oa: 1
oa_version: Published Version
project:
- _id: 0599E47C-7A3F-11EA-A408-12923DDC885E
call_identifier: H2020
grant_number: '863818'
name: 'Formal Methods for Stochastic Models: Algorithms and Applications'
publication: 44th IARCS Annual Conference on Foundations of Software Technology and
Theoretical Computer Science
publication_identifier:
isbn:
- '9783959773553'
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'Concurrent stochastic games with stateful-discounted and parity objectives:
Complexity and algorithms'
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 323
year: '2024'
...
---
_id: '17101'
abstract:
- lang: eng
text: "This paper considers a class of two-player zero-sum games on directed graphs
whose vertices are equipped with random payoffs of bounded support known by both
players.\r\nStarting from a fixed vertex, players take turns to move a token along
the edges of the graph.\r\nOn the one hand, for acyclic directed graphs of bounded
degree and sub-exponential expansion, we show that the value of the game converges
almost surely to a constant at an exponential rate dominated in terms of the expansion.\r\nOn
the other hand, for the infinite d-ary tree that does not fall into the previous
class of graphs, we show convergence at a double-exponential rate in terms of
the expansion."
acknowledgement: "This work was supported by the French Agence Nationale de la Recherche
(ANR) under references ANR-21-CE40-0020 (CONVERGENCE project) and ANR-20-CE40-0002
(GrHyDy), and by Fondecyt grant 1220174. This collaboration was mainly conducted
during a 1-year visit of Bruno Ziliotto to the Center for Mathematical Modeling
(CMM) at University of Chile in 2023,\r\nunder the IRL program of CNRS."
article_number: '2401.16252'
article_processing_charge: No
arxiv: 1
author:
- first_name: Luc
full_name: Attia, Luc
last_name: Attia
- first_name: Lyuben
full_name: Lichev, Lyuben
last_name: Lichev
- first_name: Dieter
full_name: Mitsche, Dieter
last_name: Mitsche
- 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: Attia L, Lichev L, Mitsche D, Saona Urmeneta RJ, Ziliotto B. Zero-sum random
games on directed graphs. arXiv. doi:10.48550/arXiv.2401.16252
apa: Attia, L., Lichev, L., Mitsche, D., Saona Urmeneta, R. J., & Ziliotto,
B. (n.d.). Zero-sum random games on directed graphs. arXiv. https://doi.org/10.48550/arXiv.2401.16252
chicago: Attia, Luc, Lyuben Lichev, Dieter Mitsche, Raimundo J Saona Urmeneta, and
Bruno Ziliotto. “Zero-Sum Random Games on Directed Graphs.” ArXiv, n.d.
https://doi.org/10.48550/arXiv.2401.16252.
ieee: L. Attia, L. Lichev, D. Mitsche, R. J. Saona Urmeneta, and B. Ziliotto, “Zero-sum
random games on directed graphs,” arXiv. .
ista: Attia L, Lichev L, Mitsche D, Saona Urmeneta RJ, Ziliotto B. Zero-sum random
games on directed graphs. arXiv, 2401.16252.
mla: Attia, Luc, et al. “Zero-Sum Random Games on Directed Graphs.” ArXiv,
2401.16252, doi:10.48550/arXiv.2401.16252.
short: L. Attia, L. Lichev, D. Mitsche, R.J. Saona Urmeneta, B. Ziliotto, ArXiv
(n.d.).
date_created: 2024-06-03T07:45:22Z
date_published: 2024-01-29T00:00:00Z
date_updated: 2024-06-03T07:50:29Z
day: '29'
department:
- _id: KrCh
doi: 10.48550/arXiv.2401.16252
external_id:
arxiv:
- '2401.16252'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.48550/arXiv.2401.16252
month: '01'
oa: 1
oa_version: Preprint
publication: arXiv
publication_status: submitted
status: public
title: Zero-sum random games on directed graphs
type: preprint
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2024'
...
---
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. Mathematics of Operations Research. 2024;50(4):2433-3282. doi:10.1287/moor.2022.0332
apa: Chatterjee, K., Oliu-Barton, M., & Saona Urmeneta, R. J. (2024). Value-positivity
for matrix games. Mathematics of Operations Research. Institute for Operations
Research and the Management Sciences. https://doi.org/10.1287/moor.2022.0332
chicago: Chatterjee, Krishnendu, Miquel Oliu-Barton, and Raimundo J Saona Urmeneta.
“Value-Positivity for Matrix Games.” Mathematics of Operations Research.
Institute for Operations Research and the Management Sciences, 2024. https://doi.org/10.1287/moor.2022.0332.
ieee: K. Chatterjee, M. Oliu-Barton, and R. J. Saona Urmeneta, “Value-positivity
for matrix games,” Mathematics of Operations Research, 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.” Mathematics
of Operations Research, vol. 50, no. 4, Institute for Operations Research
and the Management Sciences, 2024, pp. 2433–3282, doi:10.1287/moor.2022.0332.
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-04-07T12:31:21Z
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: '12676'
abstract:
- lang: eng
text: Turn-based stochastic games (aka simple stochastic games) are two-player zero-sum
games played on directed graphs with probabilistic transitions. The goal of player-max
is to maximize the probability to reach a target state against the adversarial
player-min. These games lie in NP ∩ coNP and are among the rare combinatorial
problems that belong to this complexity class for which the existence of polynomial-time
algorithm is a major open question. While randomized sub-exponential time algorithm
exists, all known deterministic algorithms require exponential time in the worst-case.
An important open question has been whether faster algorithms can be obtained
parametrized by the treewidth of the game graph. Even deterministic sub-exponential
time algorithm for constant treewidth turn-based stochastic games has remain elusive.
In this work our main result is a deterministic algorithm to solve turn-based
stochastic games that, given a game with n states, treewidth at most t, and the
bit-complexity of the probabilistic transition function log D, has running time
O ((tn2 log D)t log n). In particular, our algorithm is quasi-polynomial time
for games with constant or poly-logarithmic treewidth.
acknowledgement: This research was partially supported by the ERC CoG 863818 (ForM-SMArt)
grant.
article_processing_charge: No
author:
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Tobias
full_name: Meggendorfer, Tobias
id: b21b0c15-30a2-11eb-80dc-f13ca25802e1
last_name: Meggendorfer
orcid: 0000-0002-1712-2165
- 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: Jakub
full_name: Svoboda, Jakub
id: 130759D2-D7DD-11E9-87D2-DE0DE6697425
last_name: Svoboda
orcid: 0000-0002-1419-3267
citation:
ama: 'Chatterjee K, Meggendorfer T, Saona Urmeneta RJ, Svoboda J. Faster algorithm
for turn-based stochastic games with bounded treewidth. In: Proceedings of
the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial
and Applied Mathematics; 2023:4590-4605. doi:10.1137/1.9781611977554.ch173'
apa: 'Chatterjee, K., Meggendorfer, T., Saona Urmeneta, R. J., & Svoboda, J.
(2023). Faster algorithm for turn-based stochastic games with bounded treewidth.
In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms
(pp. 4590–4605). Florence, Italy: Society for Industrial and Applied Mathematics.
https://doi.org/10.1137/1.9781611977554.ch173'
chicago: Chatterjee, Krishnendu, Tobias Meggendorfer, Raimundo J Saona Urmeneta,
and Jakub Svoboda. “Faster Algorithm for Turn-Based Stochastic Games with Bounded
Treewidth.” In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete
Algorithms, 4590–4605. Society for Industrial and Applied Mathematics, 2023.
https://doi.org/10.1137/1.9781611977554.ch173.
ieee: K. Chatterjee, T. Meggendorfer, R. J. Saona Urmeneta, and J. Svoboda, “Faster
algorithm for turn-based stochastic games with bounded treewidth,” in Proceedings
of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms, Florence, Italy,
2023, pp. 4590–4605.
ista: 'Chatterjee K, Meggendorfer T, Saona Urmeneta RJ, Svoboda J. 2023. Faster
algorithm for turn-based stochastic games with bounded treewidth. Proceedings
of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms. SODA: Symposium
on Discrete Algorithms, 4590–4605.'
mla: Chatterjee, Krishnendu, et al. “Faster Algorithm for Turn-Based Stochastic
Games with Bounded Treewidth.” Proceedings of the 2023 Annual ACM-SIAM Symposium
on Discrete Algorithms, Society for Industrial and Applied Mathematics, 2023,
pp. 4590–605, doi:10.1137/1.9781611977554.ch173.
short: K. Chatterjee, T. Meggendorfer, R.J. Saona Urmeneta, J. Svoboda, in:, Proceedings
of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial
and Applied Mathematics, 2023, pp. 4590–4605.
conference:
end_date: 2023-01-25
location: Florence, Italy
name: 'SODA: Symposium on Discrete Algorithms'
start_date: 2023-01-22
corr_author: '1'
date_created: 2023-02-24T12:20:47Z
date_published: 2023-02-01T00:00:00Z
date_updated: 2026-06-18T17:28:38Z
day: '01'
ddc:
- '000'
department:
- _id: GradSch
- _id: KrCh
doi: 10.1137/1.9781611977554.ch173
ec_funded: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.1137/1.9781611977554.ch173
month: '02'
oa: 1
oa_version: Published Version
page: 4590-4605
project:
- _id: 0599E47C-7A3F-11EA-A408-12923DDC885E
call_identifier: H2020
grant_number: '863818'
name: 'Formal Methods for Stochastic Models: Algorithms and Applications'
publication: Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms
publication_identifier:
isbn:
- '9781611977554'
publication_status: published
publisher: Society for Industrial and Applied Mathematics
quality_controlled: '1'
status: public
title: Faster algorithm for turn-based stochastic games with bounded treewidth
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2023'
...
---
_id: '17100'
abstract:
- lang: eng
text: "Prophet inequalities are a central object of study in optimal stopping theory.
A gambler is sent values online, sampled from an instance of independent distributions,
in an adversarial, random or selected order, depending on the model. When observing
each value, the gambler either accepts it as a reward or irrevocably rejects it
and proceeds to observe the next value. The goal of the gambler, who cannot see
the future, is maximising the expected value of the reward while competing against
the expectation of a prophet (the offline maximum). In other words, one seeks
to maximise the gambler-to-prophet ratio of the expectations.\r\nThe model, in
which the gambler selects the arrival order first, and then observes the values,
is known as Order Selection. In this model a ratio of 0.7251 has been proved to
be attainable for any instance. In very recent work, this has been improved up
to 0.7258. If the gambler chooses the arrival order (uniformly) at random, we
obtain the Random Order model. The worst case ratio over all possible instances
has been extensively studied for at least 40 years. In the recent work aforementioned,
through simulations, this ratio has been shown to be at most 0.7254 for the Random
Order model, thus establishing for the first time that carefully choosing the
order, instead of simply taking it at random, benefits the gambler. We give an
alternative, more rigorous proof of this fact, by showing mathematically that
in the Random Order model, no algorithm can achieve a ratio larger than 0.7235.
This sets a new state-of-the-art hardness for this model, and establishes more
formally that there is a real benefit in choosing the order."
acknowledgement: This research was partially supported by the EPSRC grant EP/W005573/1,
the ERC CoG 863818 (ForM-SMArt) grant, and the ANID Chile grant ACT210005. We would
like to thank Jos´e Correa and Bruno Zilotto for their precious advice, and Mona
Mohammadi and Roodabeh Safavi for early conversations.
article_number: '2304.04024'
article_processing_charge: No
arxiv: 1
author:
- first_name: Giordano
full_name: Giambartolomei, Giordano
last_name: Giambartolomei
- first_name: Frederik Mallmann-Trenn
full_name: Frederik Mallmann-Trenn, Frederik Mallmann-Trenn
last_name: Frederik Mallmann-Trenn
- 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: 'Giambartolomei G, Frederik Mallmann-Trenn FM-T, Saona Urmeneta RJ. Prophet
inequalities: Separating random order from order selection. arXiv. doi:10.48550/arXiv.2304.04024'
apa: 'Giambartolomei, G., Frederik Mallmann-Trenn, F. M.-T., & Saona Urmeneta,
R. J. (n.d.). Prophet inequalities: Separating random order from order selection.
arXiv. https://doi.org/10.48550/arXiv.2304.04024'
chicago: 'Giambartolomei, Giordano, Frederik Mallmann-Trenn Frederik Mallmann-Trenn,
and Raimundo J Saona Urmeneta. “Prophet Inequalities: Separating Random Order
from Order Selection.” ArXiv, n.d. https://doi.org/10.48550/arXiv.2304.04024.'
ieee: 'G. Giambartolomei, F. M.-T. Frederik Mallmann-Trenn, and R. J. Saona Urmeneta,
“Prophet inequalities: Separating random order from order selection,” arXiv.
.'
ista: 'Giambartolomei G, Frederik Mallmann-Trenn FM-T, Saona Urmeneta RJ. Prophet
inequalities: Separating random order from order selection. arXiv, 2304.04024.'
mla: 'Giambartolomei, Giordano, et al. “Prophet Inequalities: Separating Random
Order from Order Selection.” ArXiv, 2304.04024, doi:10.48550/arXiv.2304.04024.'
short: G. Giambartolomei, F.M.-T. Frederik Mallmann-Trenn, R.J. Saona Urmeneta,
ArXiv (n.d.).
date_created: 2024-06-03T07:44:54Z
date_published: 2023-04-08T00:00:00Z
date_updated: 2025-04-14T07:52:47Z
day: '08'
department:
- _id: KrCh
doi: 10.48550/arXiv.2304.04024
ec_funded: 1
external_id:
arxiv:
- '2304.04024'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.48550/arXiv.2304.04024
month: '04'
oa: 1
oa_version: Preprint
project:
- _id: 0599E47C-7A3F-11EA-A408-12923DDC885E
call_identifier: H2020
grant_number: '863818'
name: 'Formal Methods for Stochastic Models: Algorithms and Applications'
publication: arXiv
publication_status: submitted
status: public
title: 'Prophet inequalities: Separating random order from order selection'
type: preprint
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2023'
...
---
_id: '11447'
abstract:
- lang: eng
text: Empirical essays of fitness landscapes suggest that they may be rugged, that
is having multiple fitness peaks. Such fitness landscapes, those that have multiple
peaks, necessarily have special local structures, called reciprocal sign epistasis
(Poelwijk et al. in J Theor Biol 272:141–144, 2011). Here, we investigate the
quantitative relationship between the number of fitness peaks and the number of
reciprocal sign epistatic interactions. Previously, it has been shown (Poelwijk
et al. in J Theor Biol 272:141–144, 2011) that pairwise reciprocal sign epistasis
is a necessary but not sufficient condition for the existence of multiple peaks.
Applying discrete Morse theory, which to our knowledge has never been used in
this context, we extend this result by giving the minimal number of reciprocal
sign epistatic interactions required to create a given number of peaks.
acknowledgement: We are grateful to Herbert Edelsbrunner and Jeferson Zapata for helpful
discussions. Open access funding provided by Austrian Science Fund (FWF). Partially
supported by the ERC Consolidator (771209–CharFL) and the FWF Austrian Science Fund
(I5127-B) grants to FAK.
article_number: '74'
article_processing_charge: Yes (via OA deal)
article_type: original
author:
- 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: Fyodor
full_name: Kondrashov, Fyodor
id: 44FDEF62-F248-11E8-B48F-1D18A9856A87
last_name: Kondrashov
orcid: 0000-0001-8243-4694
- first_name: Kseniia
full_name: Khudiakova, Kseniia
id: 4E6DC800-AE37-11E9-AC72-31CAE5697425
last_name: Khudiakova
orcid: 0000-0002-6246-1465
citation:
ama: Saona Urmeneta RJ, Kondrashov F, Khudiakova K. Relation between the number
of peaks and the number of reciprocal sign epistatic interactions. Bulletin
of Mathematical Biology. 2022;84(8). doi:10.1007/s11538-022-01029-z
apa: Saona Urmeneta, R. J., Kondrashov, F., & Khudiakova, K. (2022). Relation
between the number of peaks and the number of reciprocal sign epistatic interactions.
Bulletin of Mathematical Biology. Springer Nature. https://doi.org/10.1007/s11538-022-01029-z
chicago: Saona Urmeneta, Raimundo J, Fyodor Kondrashov, and Kseniia Khudiakova.
“Relation between the Number of Peaks and the Number of Reciprocal Sign Epistatic
Interactions.” Bulletin of Mathematical Biology. Springer Nature, 2022.
https://doi.org/10.1007/s11538-022-01029-z.
ieee: R. J. Saona Urmeneta, F. Kondrashov, and K. Khudiakova, “Relation between
the number of peaks and the number of reciprocal sign epistatic interactions,”
Bulletin of Mathematical Biology, vol. 84, no. 8. Springer Nature, 2022.
ista: Saona Urmeneta RJ, Kondrashov F, Khudiakova K. 2022. Relation between the
number of peaks and the number of reciprocal sign epistatic interactions. Bulletin
of Mathematical Biology. 84(8), 74.
mla: Saona Urmeneta, Raimundo J., et al. “Relation between the Number of Peaks and
the Number of Reciprocal Sign Epistatic Interactions.” Bulletin of Mathematical
Biology, vol. 84, no. 8, 74, Springer Nature, 2022, doi:10.1007/s11538-022-01029-z.
short: R.J. Saona Urmeneta, F. Kondrashov, K. Khudiakova, Bulletin of Mathematical
Biology 84 (2022).
corr_author: '1'
date_created: 2022-06-17T16:16:15Z
date_published: 2022-06-17T00:00:00Z
date_updated: 2026-06-12T12:43:34Z
day: '17'
ddc:
- '510'
- '570'
department:
- _id: GradSch
- _id: NiBa
- _id: JaMa
doi: 10.1007/s11538-022-01029-z
ec_funded: 1
external_id:
isi:
- '000812509800001'
pmid:
- '35713756'
file:
- access_level: open_access
checksum: 05a1fe7d10914a00c2bca9b447993a65
content_type: application/pdf
creator: dernst
date_created: 2022-06-20T07:51:32Z
date_updated: 2022-06-20T07:51:32Z
file_id: '11455'
file_name: 2022_BulletinMathBiology_Saona.pdf
file_size: 463025
relation: main_file
success: 1
file_date_updated: 2022-06-20T07:51:32Z
has_accepted_license: '1'
intvolume: ' 84'
isi: 1
issue: '8'
keyword:
- Computational Theory and Mathematics
- General Agricultural and Biological Sciences
- Pharmacology
- General Environmental Science
- General Biochemistry
- Genetics and Molecular Biology
- General Mathematics
- Immunology
- General Neuroscience
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
pmid: 1
project:
- _id: 26580278-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '771209'
name: Characterizing the fitness landscape on population and global scales
- _id: 34e076d6-11ca-11ed-8bc3-aec76c41a181
grant_number: I05127
name: Evolutionary analysis of gene regulation
publication: Bulletin of Mathematical Biology
publication_identifier:
eissn:
- 1522-9602
issn:
- 0092-8240
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
related_material:
link:
- relation: erratum
url: https://doi.org/10.1007/s11538-022-01118-z
record:
- id: '21918'
relation: dissertation_contains
status: public
scopus_import: '1'
status: public
title: Relation between the number of peaks and the number of reciprocal sign epistatic
interactions
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 84
year: '2022'
...
---
_id: '12677'
abstract:
- lang: eng
text: "In modern sample-driven Prophet Inequality, an adversary chooses a sequence
of n items with values v1,v2,…,vn to be presented to a decision maker (DM). The
process follows in two phases. In the first phase (sampling phase), some items,
possibly selected at random, are revealed to the DM, but she can never accept
them. In the second phase, the DM is presented with the other items in a random
order and online fashion. For each item, she must make an irrevocable decision
to either accept the item and stop the process or reject the item forever and
proceed to the next item. The goal of the DM is to maximize the expected value
as compared to a Prophet (or offline algorithm) that has access to all information.
In this setting, the sampling phase has no cost and is not part of the optimization
process. However, in many scenarios, the samples are obtained as part of the decision-making
process.\r\nWe model this aspect as a two-phase Prophet Inequality where an adversary
chooses a sequence of 2n items with values v1,v2,…,v2n and the items are randomly
ordered. Finally, there are two phases of the Prophet Inequality problem with
the first n-items and the rest of the items, respectively. We show that some basic
algorithms achieve a ratio of at most 0.450. We present an algorithm that achieves
a ratio of at least 0.495. Finally, we show that for every algorithm the ratio
it can achieve is at most 0.502. Hence our algorithm is near-optimal."
acknowledgement: This research was partially supported by the ERC CoG 863818 (ForM-SMArt)
grant.
article_number: '2209.14368'
article_processing_charge: No
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: Mona
full_name: Mohammadi, Mona
id: 4363614d-b686-11ed-a7d5-ac9e4a24bc2e
last_name: Mohammadi
- 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, Mohammadi M, Saona Urmeneta RJ. Repeated prophet inequality with
near-optimal bounds. arXiv. doi:10.48550/ARXIV.2209.14368
apa: Chatterjee, K., Mohammadi, M., & Saona Urmeneta, R. J. (n.d.). Repeated
prophet inequality with near-optimal bounds. arXiv. https://doi.org/10.48550/ARXIV.2209.14368
chicago: Chatterjee, Krishnendu, Mona Mohammadi, and Raimundo J Saona Urmeneta.
“Repeated Prophet Inequality with Near-Optimal Bounds.” ArXiv, n.d. https://doi.org/10.48550/ARXIV.2209.14368.
ieee: K. Chatterjee, M. Mohammadi, and R. J. Saona Urmeneta, “Repeated prophet inequality
with near-optimal bounds,” arXiv. .
ista: Chatterjee K, Mohammadi M, Saona Urmeneta RJ. Repeated prophet inequality
with near-optimal bounds. arXiv, 2209.14368.
mla: Chatterjee, Krishnendu, et al. “Repeated Prophet Inequality with Near-Optimal
Bounds.” ArXiv, 2209.14368, doi:10.48550/ARXIV.2209.14368.
short: K. Chatterjee, M. Mohammadi, R.J. Saona Urmeneta, ArXiv (n.d.).
corr_author: '1'
date_created: 2023-02-24T12:21:40Z
date_published: 2022-09-28T00:00:00Z
date_updated: 2025-04-14T07:52:48Z
day: '28'
department:
- _id: GradSch
- _id: KrCh
doi: 10.48550/ARXIV.2209.14368
ec_funded: 1
external_id:
arxiv:
- '2209.14368'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: ' https://doi.org/10.48550/arXiv.2209.14368'
month: '09'
oa: 1
oa_version: Preprint
project:
- _id: 0599E47C-7A3F-11EA-A408-12923DDC885E
call_identifier: H2020
grant_number: '863818'
name: 'Formal Methods for Stochastic Models: Algorithms and Applications'
publication: arXiv
publication_status: submitted
status: public
title: Repeated prophet inequality with near-optimal bounds
type: preprint
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2022'
...
---
_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. Mathematics of Operations Research. 2022;47(1):100-119.
doi:10.1287/moor.2020.1116
apa: Chatterjee, K., Saona Urmeneta, R. J., & Ziliotto, B. (2022). Finite-memory
strategies in POMDPs with long-run average objectives. Mathematics of Operations
Research. Institute for Operations Research and the Management Sciences. https://doi.org/10.1287/moor.2020.1116
chicago: Chatterjee, Krishnendu, Raimundo J Saona Urmeneta, and Bruno Ziliotto.
“Finite-Memory Strategies in POMDPs with Long-Run Average Objectives.” Mathematics
of Operations Research. Institute for Operations Research and the Management
Sciences, 2022. https://doi.org/10.1287/moor.2020.1116.
ieee: K. Chatterjee, R. J. Saona Urmeneta, and B. Ziliotto, “Finite-memory strategies
in POMDPs with long-run average objectives,” Mathematics of Operations Research,
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.” Mathematics of Operations Research, vol. 47, no. 1,
Institute for Operations Research and the Management Sciences, 2022, pp. 100–19,
doi:10.1287/moor.2020.1116.
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-04-07T12:31:21Z
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'
...