Stochastic Multiplayer Games
Stochastic Multiplayer Games
Theory and Algorithms
€ 37,95
Number of pages
Publication date
15.6 x 23.4 cm
Table of Contents
Show Table of ContentsHide Table of Contents
Preface - 6 Contents - 8 List of Figures - 10 List of Tables - 12 List of Algorithms - 14 1 Introduction - 16 2 Stochastic Games - 32 3 Equilibria - 56 4 Complexity of Equilibria - 78 5 Decidable Fragments - 100 6 Conclusion - 136 Appendix A Preliminaries - 142 Appendix B Markov Chains and Markov Decision Processes - 150 Bibliography - 158 Notation - 170 Index - 172

M. Ummels

Stochastic Multiplayer Games

Theory and Algorithms

Stochastic games provide a versatile model for reactive systems that are a'ected 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 complexitytheoretic 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 e(cient algorithms for natural special cases.
As of 1 November 2022, we are moving our UK and ROW distributor. During this cross-over period, our web shop is unavailable for these regions. To order, please email or call +44 (0)1243 843291 (open 8.00-17:15 GMT)
Order from North America External Link

M. Ummels

Michael Ummels received his diploma degree in computer science from RWTH Aachen University. He started his doctoral studies at the same university in 2006, supervised by Prof. Dr. Erich Grädel and Prof. Dr. Dr.h.c. Wolfgang Thomas. As ofFebruary 2010, the author is a postdoctoral researcher at ENS Cachan.