Equilibria-based probabilistic model checking for concurrent stochastic games

Marta Kwiatkowska, Gethin Norman, David Parker, Gabriel Santos

Research output: Chapter in Book/Report/Conference proceedingConference contribution

3 Citations (Scopus)
225 Downloads (Pure)

Abstract

Probabilistic model checking for stochastic games enables formal verification of systems where competing or collaborating entities operate in a stochastic environment. While good progress has been made in the area, existing approaches focus on zero-sum goals and cannot reason about distinct entities collaborating whilst working to different objectives. In this paper, we propose probabilistic model checking techniques for concurrent stochastic games based on Nash equilibria. We extend the temporal logic rPATL (probabilistic alternating-time temporal logic with rewards) for reasoning about players with distinct quantitative goals which relate to either the probability of an event occurring or a reward measure. We present algorithms to synthesise strategies that are subgame perfect social welfare optimal Nash equilibria, i.e., where there is no incentive for any players to unilaterally change their strategy in any state of the game, whilst the combined probabilities or rewards are maximised. We implement our techniques in an extension of the PRISM-games tool and demonstrate their application to several case studies, including network protocols and robot navigation.
Original languageEnglish
Title of host publicationFormal Methods – The Next 30 Years
Subtitle of host publicationThird World Congress, FM 2019, Porto, Portugal, October 7–11, 2019, Proceedings
EditorsMaurice H. ter Beek, Annabelle McIver, José N. Oliveira
PublisherSpringer
Pages298-315
Number of pages18
ISBN (Electronic)978-3-030-30942-8
ISBN (Print)978-3-030-30941-1
Publication statusPublished - 23 Sept 2019
Event23rd International Symposium on Formal Methods (FM'19) - Porto, Portugal
Duration: 7 Oct 201911 Oct 2019

Publication series

NameLecture Notes in Computer Science
Volume11800
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349
NameProgramming and Software Engineering
Volume11800

Conference

Conference23rd International Symposium on Formal Methods (FM'19)
Country/TerritoryPortugal
CityPorto
Period7/10/1911/10/19

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint

Dive into the research topics of 'Equilibria-based probabilistic model checking for concurrent stochastic games'. Together they form a unique fingerprint.

Cite this