Patricia Bouyer ; Romain Brenguier ; Nicolas Markey ; Michael Ummels - Pure Nash Equilibria in Concurrent Deterministic Games

lmcs:1569 - Logical Methods in Computer Science, June 19, 2015, Volume 11, Issue 2 - https://doi.org/10.2168/LMCS-11(2:9)2015
Pure Nash Equilibria in Concurrent Deterministic GamesArticle

Authors: Patricia Bouyer ; Romain Brenguier ; Nicolas Markey ORCID; Michael Ummels

    We study pure-strategy Nash equilibria in multi-player concurrent deterministic games, for a variety of preference relations. We provide a novel construction, called the suspect game, which transforms a multi-player concurrent game into a two-player turn-based game which turns Nash equilibria into winning strategies (for some objective that depends on the preference relations of the players in the original game). We use that transformation to design algorithms for computing Nash equilibria in finite games, which in most cases have optimal worst-case complexity, for large classes of preference relations. This includes the purely qualitative framework, where each player has a single omega-regular objective that she wants to satisfy, but also the larger class of semi-quantitative objectives, where each player has several omega-regular objectives equipped with a preorder (for instance, a player may want to satisfy all her objectives, or to maximise the number of objectives that she achieves.)


    Volume: Volume 11, Issue 2
    Published on: June 19, 2015
    Submitted on: June 27, 2012
    Keywords: Computer Science - Logic in Computer Science,Computer Science - Computer Science and Game Theory
    Funding:
      Source : OpenAIRE Graph
    • EQualIS : Enhancing the Quality of Interacting Systems; Funder: European Commission; Code: 308087
    • Collective Adaptive System SynThesIs with Non-zero-sum Games; Funder: European Commission; Code: 601148
    • inVEST: Foundations for a Shift from Verification to Synthesis; Funder: European Commission; Code: 279499

    21 Documents citing this article

    Consultation statistics

    This page has been seen 1330 times.
    This article's PDF has been downloaded 509 times.