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.
Author(s): Michael Ummels
Series: Pallas Proefschriften
Publisher: Pallas Publications
Year: 2010
Language: English
Pages: 175
Tags: Математика;Теория игр;
Games and equilibria......Page 16
The stochastic dining philosophers problem......Page 22
Contributions......Page 26
Related work......Page 28
Outline......Page 29
Arenas and objectives......Page 32
Strategies and strategy profiles......Page 38
Subarenas and end components......Page 42
Values, determinacy and optimal strategies......Page 43
Algorithmic problems......Page 48
Existence of residually optimal strategies......Page 52
Definitions and basic properties......Page 56
Existence of Nash equilibria......Page 60
Existence of subgame-perfect equilibria......Page 65
Computing equilibria......Page 70
Decision problems......Page 74
Positional equilibria......Page 78
Stationary equilibria......Page 83
Pure and randomised equilibria......Page 89
Finite-state equilibria......Page 97
Summary of results......Page 99
The strictly qualitative fragment......Page 100
The positive-one fragment......Page 114
The qualitative fragment for deterministic games......Page 123
Summary of results......Page 134
Summary and open problems......Page 136
Perspectives......Page 139
Probability theory......Page 142
Computational complexity......Page 145
Markov chains......Page 150
Markov decision processes......Page 153
Bibliography......Page 158
Notation......Page 170
Index......Page 172
