Pure Nash Equilibria in Concurrent Deterministic Games

Abstract

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.)

72 pages

References in corpus (1)

• Robust Equilibria in Concurrent Games

Cited by in corpus (17)

• Quantum games: a review of the history, current state, and interpretation
• Strategy Logic with Imperfect Information
• Constrained Existence Problem for Weak Subgame Perfect Equilibria with $\omega$-Regular Boolean Objectives
• Stochastic Equilibria under Imprecise Deviations in Terminal-Reward Concurrent Games
• Efficient Energy Distribution in a Smart Grid using Multi-Player Games
• Games on graphs with a public signal monitoring
• Nash equilibria in games over graphs equipped with a communication mechanism
• Nash Equilibrium and Bisimulation Invariance
• Existence and Verification of Nash Equilibria in Non-Cooperative Contribution Games with Resource Contention
• The Complexity of Pure Strategy Relevant Equilibria in Concurrent Games
• Designing Equilibria in Concurrent Games with Social Welfare and Temporal Logic Constraints
• Equilibria in Quantitative Concurrent Games
• Equilibria for Games with Combined Qualitative and Quantitative Objectives
• Deviator Detection under Imperfect Monitoring
• Automated Temporal Equilibrium Analysis: Verification and Synthesis of Multi-Player Games
• Computer aided synthesis: a game theoretic approach
• Reasoning about Temporary Coalitions and LTL-definable Ordered Objectives in Infinite Concurrent Multiplayer Games