Non-cooperative rational synthesis problem for probabilistic strategies
<|reference_start|>Non-cooperative rational synthesis problem for probabilistic strategies: 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.<|reference_end|>
@article{koide2024non-cooperative,
    title={Non-cooperative rational synthesis problem for probabilistic strategies},
    author={So Koide, Yoshiaki Takata and Hiroyuki Seki},
    journal={arXiv preprint arXiv:2409.18155},
    year={2024},
    archivePrefix={arXiv},
    eprint={2409.18155},
    primaryClass={cs.GT cs.FL}
}