The last decades have seen an immense amount of research on the algorithmic content of game theory. On the one hand, a new subject called algorithmic game theory has emerged that is concerned with the study of the algorithmic theory of finite games with multiple players. On the other hand, infinite and, in particular, stochastic two-player zero-sum games have become an important tool for the verifiation of open systems, which interact with their environment.

The aim of this work is to bring together algorithmic game theory with the games that are used in verifiation by extending the algorithmic theory of stochastic two-player zero-sum games to incorporate multiple players, whose objectives are not necessarily conflcting. In particular, this work contains a comprehensive study of the complexity of the most prominent solution concepts that are applicable in this setting, namely Nash and subgame-perfect equilibria.

This book is the result of my doctoral studies at RWTH Aachen University. I am indebted to my primary supervisor Erich Grädel for giving me the opportunity to pursue these studies, for introducing me to the scientific community and for giving me advice just when I needed it. I am equally grateful to my secondary supervisor Wolfgang Thomas for his constant support and encouragement.