
Stochastic Multiplayer Games
Theory and Algorithms
Michael M. Ummels(Author)
Pallas Publications (Publisher)
Published on 14. December 2010
Book
Paperback/Softback
174 pages
978-90-8555-040-2 (ISBN)
Description
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 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 efficient algorithms for natural special cases.
More details
Series
Language
English
Place of publication
Amsterdam
Netherlands
Target group
Professional and scholarly
Dimensions
Height: 234 mm
Width: 156 mm
Weight
304 gr
ISBN-13
978-90-8555-040-2 (9789085550402)
DOI
10.5117/9789085550402
Copyright in bibliographic data and cover images is held by Nielsen Book Services Limited or by the publishers or by their respective licensors: all rights reserved.
Schweitzer Classification
Person
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 Graedel and Prof. Dr. Dr.h.c. Wolfgang Thomas. As ofFebruary 2010, the author is a postdoctoral researcher at ENS Cachan.
Content
Preface, List of Figures, List of Tables, List of Algorithms, 1 Introduction, 2 Stochastic Games, 3 Equilibria, 4 Complexity of Equilibria, 7 5 Decidable Fragments, 6 Conclusion, Appendix A Preliminaries, Appendix B Markov Chains and Markov Decision Processes, Bibliography, Notation, Index