The Complexity of Games with Randomised Control

Bahmani, S ORCID: 0009-0002-4476-489X, Ibsen-Jensen, R ORCID: 0000-0003-4783-0389, Paul, S ORCID: 0000-0002-7233-2018, Schewe, S ORCID: 0000-0002-9093-9518, Slivovsky, F ORCID: 0000-0003-1784-2346, Tang, Q ORCID: 0000-0002-9265-3011, Wojtczak, D ORCID: 0000-0001-5560-0546 and Zhu, S ORCID: 0000-0002-5922-8750 (2026) The Complexity of Games with Randomised Control In: 29th International Conference on Foundations of Software Science and Computation Structures.

Text Soumyajit_Games (1).pdf - Author Accepted Manuscript Available under License Creative Commons Attribution. Download (667kB) | Preview

Abstract

We study the complexity of solving two-player infinite duration games played on a fixed finite graph, where the control of a node is not predetermined but rather assigned randomly. In classic random-turn games, control of each node is assigned randomly every time the node is visited during a play. In this work, we study two natural variants of this where control of each node is assigned only once: (i) control is assigned randomly during a play when a node is visited for the first time and does not change for the rest of the play and (ii) control is assigned a priori before the game starts for every node by independent coin tosses and then the game is played. We investigate the complexity of computing the winning probability with three kinds of objectives–reachability, parity, and energy. We show that the qualitative questions on all variants and all objectives are NL-complete. For the quantitative questions, we show that deciding whether the maximiser can win with probability at least a given threshold for every objective is PSPACE-complete under the first mechanism, and that computing the exact winning probability for every objective is #P-complete under the second. To complement our hardness results for the second mechanism, we propose randomised approximation schemes that efficiently estimate the winning probability for all three objectives, assuming a bounded number of parity colours and unary-encoded weights for energy objectives, and we empirically demonstrate their fast convergence.

Item Type:	Conference Item (Unspecified)
Uncontrolled Keywords:	46 Information and Computing Sciences, 7 Affordable and Clean Energy
Divisions:	Faculty of Science & Engineering Faculty of Science & Engineering > School of Computer Science & Informatics Faculty of Science & Engineering > School of Computer Science & Informatics > Trustworthy Computing
Depositing User:	Symplectic Admin
Date Deposited:	13 Jan 2026 09:23
Last Modified:	02 Jun 2026 16:43
DOI:	10.1007/978-3-032-22730-0_3
Related Websites:	Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3196559
Disclaimer:	The University of Liverpool is not responsible for content contained on other websites from links within repository metadata. Please contact us if you notice anything that appears incorrect or inappropriate.