10.2168/LMCS-7(3:20)2011
https://lmcs.episciences.org/1209
Ummels, Michael
Michael
Ummels
Wojtczak, Dominik
Dominik
Wojtczak
0000-0001-5560-0546
The Complexity of Nash Equilibria in Stochastic Multiplayer Games
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.
episciences.org
Computer Science - Computer Science and Game Theory
Computer Science - Computational Complexity
F.1.2, G.1.6, G.3
arXiv.org - Non-exclusive license to distribute
2015-06-25
2011-09-28
2011-09-28
eng
journal article
arXiv:1109.4017
10.48550/arXiv.1109.4017
1860-5974
10.4230/lipics.mfcs.2020.45
https://lmcs.episciences.org/1209/pdf
VoR
application/pdf
Logical Methods in Computer Science
Volume 7, Issue 3
Researchers
Students