Deterministic sub-exponential algorithm for discounted-sum games with unary weights
Asadi A, Chatterjee K, Saona Urmeneta RJ, Svoboda J. Deterministic sub-exponential algorithm for discounted-sum games with unary weights. arXiv, 2405.02479.
Download (ext.)
https://doi.org/10.48550/arXiv.2405.02479
[Preprint]
Preprint
| Submitted
| English
Department
Abstract
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 and 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 $n^{O ( W^{1/4} \sqrt{n} )}$, for game graphs with $n$ vertices and
maximum absolute weight 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.
Publishing Year
Date Published
2024-05-20
Journal Title
arXiv
Acknowledgement
This research was partially supported by the ERC CoG 863818 (ForM-SMArt) grant.
Article Number
2405.02479
IST-REx-ID
Cite this
Asadi A, Chatterjee K, Saona Urmeneta RJ, Svoboda J. Deterministic sub-exponential algorithm for discounted-sum games with unary weights. arXiv. doi:10.48550/arXiv.2405.02479
Asadi, A., Chatterjee, K., Saona Urmeneta, R. J., & Svoboda, J. (n.d.). Deterministic sub-exponential algorithm for discounted-sum games with unary weights. arXiv. https://doi.org/10.48550/arXiv.2405.02479
Asadi, Ali, Krishnendu Chatterjee, Raimundo J Saona Urmeneta, and Jakub Svoboda. “Deterministic Sub-Exponential Algorithm for Discounted-Sum Games with Unary Weights.” ArXiv, n.d. https://doi.org/10.48550/arXiv.2405.02479.
A. Asadi, K. Chatterjee, R. J. Saona Urmeneta, and J. Svoboda, “Deterministic sub-exponential algorithm for discounted-sum games with unary weights,” arXiv. .
Asadi A, Chatterjee K, Saona Urmeneta RJ, Svoboda J. Deterministic sub-exponential algorithm for discounted-sum games with unary weights. arXiv, 2405.02479.
Asadi, Ali, et al. “Deterministic Sub-Exponential Algorithm for Discounted-Sum Games with Unary Weights.” ArXiv, 2405.02479, doi:10.48550/arXiv.2405.02479.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]
Link(s) to Main File(s)
Access Level
Open Access
Export
Marked PublicationsOpen Data ISTA Research Explorer
Sources
arXiv 2405.02479