The complexity of Nash equilibria in stochastic multiplayer games

DOI10.2168/LMCS-7(3:20)2011zbMATH Open1238.91025arXiv1109.4017MaRDI QIDQ3224686FDOQ3224686

Authors: Michael Ummels, Dominik Wojtczak 

Publication date: 2 April 2012

Published in: Logical Methods in Computer Science (Search for Journal in Brave)

Abstract: We analyse the computational complexity of finding Nash equilibria in turn-based stochastic multiplayer games with omega-regular objectives. We show that restricting the search space to equilibria whose payoffs fall into a certain interval may lead to undecidability. In particular, we prove that the following problem is undecidable: Given a game G, does there exist a Nash equilibrium of G where Player 0 wins with probability 1? Moreover, this problem remains undecidable when restricted to pure strategies or (pure) strategies with finite memory. One way to obtain a decidable variant of the problem is to restrict the strategies to be positional or stationary. For the complexity of these two problems, we obtain a common lower bound of NP and upper bounds of NP and PSPACE respectively. Finally, we single out a special case of the general problem that, in many cases, admits an efficient solution. In particular, we prove that deciding the existence of an equilibrium in which each player either wins or loses with probability 1 can be done in polynomial time for games where the objective of each player is given by a parity condition with a bounded number of priorities.

Full work available at URL: https://arxiv.org/abs/1109.4017

Recommendations

• The Complexity of Nash Equilibria in Simple Stochastic Multiplayer Games
• Decision Problems for Nash Equilibria in Stochastic Games
• Computer Science Logic
• The Complexity of Nash Equilibria in Infinite Multiplayer Games
• The Complexity of Nash Equilibria in Limit-Average Games

zbMATH Keywords

computational complexityNash equilibriastochastic games

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) (n)-person games, (n>2) (91A06) Stochastic games, stochastic differential games (91A15)

Cited In (30)

• Equilibria for games with combined qualitative and quantitative objectives
• The Complexity of Nash Equilibria in Infinite Multiplayer Games
• Optimal strategies for selecting coordinators
• Computer Science Logic
• The Game World Is Flat: The Complexity of Nash Equilibria in Succinct Games
• Robust equilibria in mean-payoff games
• Decision Problems for Nash Equilibria in Stochastic Games
• Multiplayer cost games with simple Nash equilibria
• Nash equilibrium in multiparty competition with ``stochastic voters
• CONCUR 2005 – Concurrency Theory
• The Complexity of Nash Equilibria in Limit-Average Games
• Nash Equilibrium for Upward-Closed Objectives
• A game-theoretic approach to indistinguishability of winning objectives as user privacy
• The complexity of stochastic Müller games
• Title not available (Why is that?)
• Automated temporal equilibrium analysis: verification and synthesis of multi-player games
• On the Complexity of Equilibria Problems in Angel-Daemon Games
• Nash equilibria in symmetric games with partial observation
• Quantitative verification and strategy synthesis for stochastic games
• Title not available (Why is that?)
• Cooperative concurrent games
• Reasoning about equilibria in game-like concurrent systems
• Invariance and randomness in the Nash program for coalitional games
• Computing Nash Equilibria in Multiplayer DAG-Structured Stochastic Games with Persistent Imperfect Information
• Stochastic equilibria under imprecise deviations in terminal-reward concurrent games
• Pure Nash equilibria in concurrent deterministic games
• On pure Nash equilibria in stochastic games
• The Complexity of Nash Equilibria in Simple Stochastic Multiplayer Games
• Efficient GPU algorithms for parallel decomposition of graphs into strongly connected and maximal end components
• Nash equilibria in symmetric graph games with partial observation

This page was built for publication: The complexity of Nash equilibria in stochastic multiplayer games

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3224686)