---
_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
date_created: 2023-02-24T12:20:47Z
date_published: 2023-02-01T00:00:00Z
date_updated: 2025-07-14T09:09:50Z
day: '01'
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: '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).
date_created: 2022-06-17T16:16:15Z
date_published: 2022-06-17T00:00:00Z
date_updated: 2023-08-03T07:20:53Z
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'
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
license: https://creativecommons.org/licenses/by/4.0/
month: '06'
oa: 1
oa_version: Published Version
project:
- _id: 26580278-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '771209'
name: Characterizing the fitness landscape on population and global scales
- _id: c098eddd-5a5b-11eb-8a69-abe27170a68f
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
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: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 84
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: 2023-09-05T13:16:11Z
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'
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'
...
---
_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.).
date_created: 2023-02-24T12:21:40Z
date_published: 2022-09-28T00:00:00Z
date_updated: 2025-07-14T09:09:51Z
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'
...