The Complexity of Nash Equilibria in Stochastic Multiplayer Games

DOI10.2168/LMCS-7(3:20)2011zbMath1238.91025arXiv1109.4017MaRDI QIDQ3224686

Michael Ummels, Dominik Wojtczak

Publication date: 2 April 2012

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

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

zbMATH Keywords

computational complexityNash equilibriastochastic games

Mathematics Subject Classification ID

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

Related Items (12)

Quantitative verification and strategy synthesis for stochastic games ⋮ Reasoning about equilibria in game-like concurrent systems ⋮ Cooperative concurrent games ⋮ Unnamed Item ⋮ Automated temporal equilibrium analysis: verification and synthesis of multi-player games ⋮ Optimal strategies for selecting coordinators ⋮ Efficient GPU algorithms for parallel decomposition of graphs into strongly connected and maximal end components ⋮ Nash equilibria in symmetric graph games with partial observation ⋮ Doomsday equilibria for omega-regular games ⋮ Unnamed Item ⋮ Unnamed Item ⋮ The Complexity of Nash Equilibria in Limit-Average Games

This page was built for publication: The Complexity of Nash Equilibria in Stochastic Multiplayer Games