Robust verification of concurrent stochastic games

Conference item

Autonomous systems often operate in multi-agent settings and need to make concurrent, strategic decisions, typically in uncertain environments. Verification and control problems for these systems can be tackled with concurrent stochastic games (CSGs), but this model requires transition probabilities to be precisely specified — an unrealistic requirement in many real-world settings. We introduce robust CSGs and their subclass interval CSGs (ICSGs), which capture epistemic uncertainty about transition probabilities in CSGs. We propose a novel framework for robust verification of these models under worst-case assumptions about transition uncertainty. Specifically, we develop the underlying theoretical foundations and efficient algorithms, for finite- and infinite-horizon objectives in both zero-sum and nonzero-sum settings, the latter based on (social-welfare optimal) Nash equilibria. We build an implementation in the PRISM-games model checker and demonstrate the feasibility of robust verification of ICSGs across a selection of large benchmarks.

Authors: He, AY; Parker, D

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Springer
• Host title: Tools and Algorithms for the Construction and Analysis of Systems
• Pages: 505-525
• Series: Lecture Notes in Computer Science
• Series number: 16505
• Publication date: 2026-04-16
• Acceptance date: 2025-12-22
• Event title: 32nd International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS 2026)
• Event location: Turin, Italy
• Event website: https://etaps.org/2026/conferences/tacas/
• Event start date: 2026-04-11
• Event end date: 2026-04-16
• DOI: 10.1007/978-3-032-22752-2_26
• EISSN: 1611-3349
• ISSN: 0302-9743
• EISBN: 9783032227522
• ISBN: 9783032227515
• Language: English
• Keywords: robust quantitative verification; probabilistic model checking; concurrent stochastic games; epistemic uncertainty