Faster and Smaller Solutions of Obliging Games
<|reference_start|>Faster and Smaller Solutions of Obliging Games: Obliging games have been introduced in the context of the game perspective on reactive synthesis in order to enforce a degree of cooperation between the to-be-synthesized system and the environment. Previous approaches to the analysis of obliging games have been small-step in the sense that they have been based on a reduction to standard (non-obliging) games in which single moves correspond to single moves in the original (obliging) game. Here, we propose a novel, large-step view on obliging games, reducing them to standard games in which single moves encode long-term behaviors in the original game. This not only allows us to give a meaningful definition of the environment winning in obliging games, but also leads to significantly improved bounds on both strategy sizes and the solution runtime for obliging games.<|reference_end|>
@article{hausmann2024faster,
    title={Faster and Smaller Solutions of Obliging Games},
    author={Daniel Hausmann and Nir Piterman},
    journal={arXiv preprint arXiv:2407.11856},
    year={2024},
    archivePrefix={arXiv},
    eprint={2407.11856},
    primaryClass={cs.GT cs.FL}
}