% IMPORTANT: The following is UTF-8 encoded. This means that in the presence
% of non-ASCII characters, it will not work with BibTeX 0.99 or older.
% Instead, you should use an up-to-date BibTeX implementation like “bibtex8” or
% “biber”.
@PHDTHESIS{Ummels:63898,
author = {Ummels, Michael},
othercontributors = {Grädel, Erich},
title = {{S}tochastic multiplayer games : theory and algorithms},
address = {Amsterdam},
publisher = {Pallas Publ.},
reportid = {RWTH-CONV-125305},
isbn = {978-90-8555-040-2},
pages = {174 S. : graph. Darst.},
year = {2010},
note = {Druckausgabe: 2010. - Onlineausgabe: 2011; Zugl.: Aachen,
Techn. Hochsch., Diss., 2010},
abstract = {Stochastic games provide a versatile model for reactive
systems that are affected by random events. Intuitively, a
play of such a game evolves by moving a token along the
edges of a directed graph. Each vertex of the graph is
either controlled by one of the players, or it is a
stochastic vertex. Whenever the token arrives at a
non-stochastic vertex, the player who controls this vertex
must move the token to a successor vertex; when the token
arrives at a stochastic vertex, a fixed probability
distribution determines the next vertex. At the end of a
play, every player receives a payoff. In our case, the
possible payoffs of a single play for one player are just 0
and 1: each player either wins or loses a play. However, due
to the presence of stochastic vertices, a player's expected
payoff, i.e. her probability of winning, can be an arbitrary
number between 0 and 1. This dissertation develops the
algorithmic theory of stochastic multiplayer games. In
particular, we analyse the computational complexity of
finding Nash equilibria in these games. On the conceptual
side, we argue that the computational complexity of
equilibria should not only be measured by the complexity of
finding an arbitrary equilibrium, but also by the complexity
of finding equilibria with certain payoffs. Specifically, we
single out the following decision problem, which we call NE,
as a yardstick for the complexity of equilibria: Given a
game as well as an upper and a lower threshold on the
payoff, decide whether the game has an equilibrium whose
payoff lies in-between the given thresholds. The main result
of this thesis is that NE is undecidable, regardless whether
one looks for an equilibrium in pure or randomised
strategies. In practice, equilibria in simpler strategies
are more desirable than equilibria in arbitrary pure or
randomised strategies, whose behaviour may depend on the
whole sequence of vertices seen so far. In particular,
strategies that only depend on the current vertex, so-called
stationary strategies (which might again be pure or
randomised) are very appealing. We prove that, for many
typical payoff functions, NE with respect to stationary
strategies is both NP-hard and contained in PSPACE, whereas
NE with respect to pure stationary strategies is
NP-complete. Our analysis is completed by providing
algorithms for several fragments of NE. For instance, we
show that NE becomes decidable when one searches for an
equilibrium where the expected payoff for each player is
either 0 or 1, or when one searches for an equilibrium where
all but one player receive expected payoff 1. Our algorithms
are accompanied by hardness proofs, which provide (almost
always matching) lower bounds on the complexities of the
problems we consider.},
keywords = {Stochastisches Spiel (SWD) / Unendliches Spiel (SWD) /
Nash-Gleichgewicht (SWD) / Komplexitätstheorie (SWD) /
Unentscheidbarkeit (SWD)},
cin = {117220 / 110000},
ddc = {004},
cid = {$I:(DE-82)117220_20140620$ / $I:(DE-82)110000_20140620$},
shelfmark = {68Q10 * 68Q1},
typ = {PUB:(DE-HGF)11},
urn = {urn:nbn:de:hbz:82-opus-34512},
url = {https://publications.rwth-aachen.de/record/63898},
}
guest ::