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 subgame-perfect 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.


    Zugriff

    Download


    Exportieren, teilen und zitieren



    Titel :

    Multi-player equilibria verification for concurrent stochastic games


    Beteiligte:
    Kwiatkowska, M (Autor:in) / Norman, G (Autor:in) / Parker, D (Autor:in) / Santos, G (Autor:in)

    Erscheinungsdatum :

    06.08.2020



    Medientyp :

    Aufsatz (Konferenz)


    Format :

    Elektronische Ressource


    Sprache :

    Englisch


    Klassifikation :

    DDC:    629



    Learning enables adaptation in cooperation for multi-player stochastic games

    Huang, Feng / Cao, Ming / Wang, Long | BASE | 2020

    Freier Zugriff

    Risk-Averse Equilibria for Vehicle Navigation in Stochastic Congestion Games

    Yekkehkhany, Ali / Nagi, Rakesh | IEEE | 2022

    Freier Zugriff

    The Mechanics of n-Player Differentiable Games

    Balduzzi, D / Racaniere, S / Martens, J et al. | BASE | 2018

    Freier Zugriff

    Optimal Player Policies for Continuous Ambush Games

    Boidot, Emmanuel / Marzuoli, Aude / Feron, Eric | AIAA | 2018


    Neural Auto-Curricula in Two-Player Zero-Sum Games

    Feng, X / Slumbers, O / Wan, Z et al. | BASE | 2021

    Freier Zugriff