Pure Nash equilibria in concurrent deterministic games
From MaRDI portal
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.)
Recommendations
Cited in
(40)- Extending finite-memory determinacy to multi-player games
- Quantum games: a review of the history, current state, and interpretation
- Constrained existence problem for weak subgame perfect equilibria with \(\omega \)-regular Boolean objectives
- Multi-player equilibria verification for concurrent stochastic games
- Automated temporal equilibrium analysis: verification and synthesis of multi-player games
- Dynamic resource allocation games
- From model checking to equilibrium checking: reactive modules for rational verification
- A Tool for the Automated Verification of Nash Equilibria in Concurrent Games
- Nash equilibria in concurrent priced games
- Concurrent games with ordered objectives
- Nash equilibria in concurrent games with Büchi objectives
- Synthesis with rational environments
- Deterministic Negotiations: Concurrency for Free
- A Note on Game Theory and Verification
- Constrained existence problem for weak subgame perfect equilibria with -regular Boolean objectives
- Computing equilibria in two-player timed games via turn-based finite games
- Finding Pure Nash Equilibrium of Graphical Game Via Constraints Satisfaction Approach
- scientific article; zbMATH DE number 1880284 (Why is no real title available?)
- scientific article; zbMATH DE number 7136658 (Why is no real title available?)
- The complexity of rational synthesis for concurrent games
- Stochastic equilibria under imprecise deviations in terminal-reward concurrent games
- scientific article; zbMATH DE number 7559372 (Why is no real title available?)
- Nash equilibria in games over graphs equipped with a communication mechanism
- On oblivious PTAS's for nash equilibrium
- Nash equilibria in symmetric graph games with partial observation
- Equilibrium design for concurrent games
- Stackelberg-Pareto synthesis
- Existence and verification of Nash equilibria in non-cooperative contribution games with resource contention
- Synthesizing safe coalition strategies
- Arena-independent memory bounds for Nash equilibria in reachability games
- Concurrent stochastic lossy channel games
- Characterising and verifying the core in concurrent multi-player mean-payoff games
- Arena-independent memory bounds for Nash equilibria in reachability games
- Regularity of the minmax value and equilibria in multiplayer Blackwell games
- Designing equilibria in concurrent games with social welfare and temporal logic constraints
- Verifying equilibria in finite-horizon probabilistic concurrent game systems
- Finitely defined preference and preference indiscernibility in ATL with strategy contexts
- Games with -automatic preference relations
- The non-cooperative rational synthesis problem for SPEs and -regular objectives
- Equilibria for games with combined qualitative and quantitative objectives
This page was built for publication: Pure Nash equilibria in concurrent deterministic games
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2941757)
