Publications
Publications › References ›
2011
Technical reports
Automatic Verification of Competitive Stochastic Systems
[CFK+11]
T. Chen, V. Forejt, M. Kwiatkowska, D. Parker and A. Simaitis.
Automatic Verification of Competitive Stochastic Systems.
Technical report RR-11-11, University of Oxford.
2011.
pdf bib
- Downloads
PDF 476 KB
BibTeX
- Notes
- This is an extended version, including proofs, of [CFK+12].
- Search for this paper
- Google · Google Scholar
Abstract
We present automatic verification techniques for the modelling and analysis of probabilistic systems that incorporate competitive behaviour. These systems are modelled as turn-based stochastic multi-player games, in which the players can either collaborate or compete in order to achieve a particular goal. We define a temporal logic called rPATL for expressing quantitative properties of stochastic multi-player games. This logic allows us to reason about the collective ability of a set of players to achieve a goal relating to the probability of an event's occurrence or the expected amount of cost/reward accumulated. We give a model checking algorithm for verifying properties expressed in this logic and implement the techniques in a probabilistic model checker, based on the PRISM tool. We demonstrate the applicability and efficiency of our methods by deploying them to analyse and detect potential weaknesses in a variety of large case studies, including algorithms for energy management and collective decision making for autonomous systems.