Ummels M. Stochastic Multiplayer Games. Theory and Algorithms 2010

Textbook in PDF format

Stochastic games provide a versatile model for reactive systems that are affected by random events. This dissertation advances the algorithmic theory of stochastic games to incorporate multiple players, whose objectives are not necessarily conflicting. The basis of this work is a comprehensive complexity-theoretic analysis of the standard game-theoretic solution concepts in the context of stochastic games over a finite state space. One main result is that the constrained existence of a Nash equilibrium becomes undecidable in this setting. This impossibility result is accompanied by several positive results, including efficient algorithms for natural special cases.
Games and equilibria.
The stochastic dining philosophers problem.
Contributions.
Related work.
Outline.
Stochastic Games.
Arenas and objectives.
Strategies and strategy profiles.
Subarenas and end components.
Values, determinacy and optimal strategies.
Algorithmic problems.
Existence of residually optimal strategies.
Equilibria.
Definitions and basic properties.
Existence of Nash equilibria.
Existence of subgame-perfect equilibria.
Computing equilibria.
Decision problems.
Complexity of Equilibria.
Positional equilibria.
Stationary equilibria.
Pure and randomised equilibria.
Finite-state equilibria.
Summary of results.
Decidable Fragments.
The strictly qualitative fragment.
The positive-one fragment.
The qualitative fragment for deterministic games.
Summary of results.
Summary and open problems.
Perspectives.
Preliminaries.
Probability theory.
Computational complexity.
Markov Chains and Markov Decision Processes.
Markov chains.
Markov decision processes.
Notation