Multi-player Equilibria Verification for Concurrent Stochastic Games

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

Authors

Colleges, School and Institutes

External organisations

  • University of Oxford
  • University of Glasgow
  • University of Oxford

Abstract

Concurrent stochastic games (CSGs) are an ideal formalism for modelling probabilistic systems that feature multiple players or components with distinct objectives making concurrent, rational decisions. Examples include communication or security protocols and multi-robot navigation. Verification methods for CSGs exist but are limited to scenarios where agents or players are grouped into two coalitions, with those in the same coalition sharing an identical objective. In this paper, we propose multi-coalitional verification techniques for CSGs. We use subgameperfect social welfare (or social cost) optimal Nash equilibria, which are strategies where there is no incentive for any coalition to unilaterally change its strategy in any game state, and where the total combined objectives are maximised (or minimised). We present an extension of the temporal logic rPATL (probabilistic alternating-time temporal logic with rewards) to specify equilibria-based properties for any number of distinct coalitions, and a corresponding model checking algorithm for a variant of stopping games. We implement our techniques in the PRISM-games tool and apply them to several case studies, including a secret sharing protocol and a public good game.

Details

Original languageEnglish
Title of host publicationProceedings of the 17th International Conference on Quantitative Evaluation of SysTems (QEST'20)
Publication statusAccepted/In press - 19 Jun 2020
Event17th International Conference on Quantitative Evaluation of SysTems (QEST'20) - Virtual Event
Duration: 31 Aug 20203 Sep 2020

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference17th International Conference on Quantitative Evaluation of SysTems (QEST'20)
CityVirtual Event
Period31/08/203/09/20