Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2409.18155 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916413465165824 |
|---|---|
| author | Koide, So Takata, Yoshiaki Seki, Hiroyuki |
| author_facet | Koide, So Takata, Yoshiaki Seki, Hiroyuki |
| contents | We study the decidability and complexity of non-cooperative rational synthesis problem (abbreviated as NCRSP) for some classes of probabilistic strategies. We show that NCRSP for stationary strategies and Muller objectives is in 3-EXPTIME, and if we restrict the strategies of environment players to be positional, NCRSP becomes NEXPSPACE solvable. On the other hand, NCRSP_>, which is a variant of NCRSP, is shown to be undecidable even for pure finite-state strategies and terminal reachability objectives. Finally, we show that NCRSP becomes EXPTIME solvable if we restrict the memory of a strategy to be the most recently visited t vertices where t is linear in the size of the game. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_18155 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Non-cooperative rational synthesis problem for probabilistic strategies Koide, So Takata, Yoshiaki Seki, Hiroyuki Computer Science and Game Theory Formal Languages and Automata Theory We study the decidability and complexity of non-cooperative rational synthesis problem (abbreviated as NCRSP) for some classes of probabilistic strategies. We show that NCRSP for stationary strategies and Muller objectives is in 3-EXPTIME, and if we restrict the strategies of environment players to be positional, NCRSP becomes NEXPSPACE solvable. On the other hand, NCRSP_>, which is a variant of NCRSP, is shown to be undecidable even for pure finite-state strategies and terminal reachability objectives. Finally, we show that NCRSP becomes EXPTIME solvable if we restrict the memory of a strategy to be the most recently visited t vertices where t is linear in the size of the game. |
| title | Non-cooperative rational synthesis problem for probabilistic strategies |
| topic | Computer Science and Game Theory Formal Languages and Automata Theory |
| url | https://arxiv.org/abs/2409.18155 |