# Deterministic sub-exponential algorithm for discounted-sum games with unary weights

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: Symposium on Logic in Computer Science, 6.

Download (ext.)

https://doi.org/10.48550/arXiv.2405.02479
[Preprint]

*Conference Paper*|

*Published*|

*English*

**Scopus indexed**

Author

Corresponding author has ISTA affiliation

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 ∩ 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.

Publishing Year

Date Published

2024-07-08

Proceedings Title

39th Annual ACM/IEEE Symposium on Logic in Computer Science

Publisher

Association for Computing Machinery

Acknowledgement

This research was partially supported by the ERC CoG 863818 (ForM-SMArt) grant.

Article Number

6

Conference

LICS: Symposium on Logic in Computer Science

Conference Location

Tallinn, Estonia

Conference Date

2024-07-08 – 2024-07-11

ISBN

eISSN

IST-REx-ID

### Cite this

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.3662080Asadi, 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.3662080Asadi, 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.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.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.**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