Complexity results for some classes of strategic games [Elektronische Ressource] / vorgelegt von Felix Fischer

Complexity Results for Some Classesof Strategic GamesDissertation an derFakultät für Mathematik, Informatik und Statistik derLudwig-Maximilians-Universität Münchenvorgelegt von Felix Fischeram 11.03.2009Complexity Results for Some Classesof Strategic GamesDissertation an derFakultät für Mathematik, Informatik und Statistik derLudwig-Maximilians-Universität Münchenvorgelegt von Felix Fischeram 11.03.2009Betreuer: Dr. Felix BrandtLudwig-Maximilians-Universität MünchenErster Berichterstatter: Prof. Martin Hofmann, Ph.D.ersität MünchenZweiter Berichterstatter: Prof. Lane A. Hemaspaandra, Ph.D.University of Rochester, NY, USADatum des Rigorosums: 03.07.2009to youContentsAbstract xiZusammenfassung xiiiAcknowledgements xv1 Introduction 12 Games, Solutions, and Complexity 52.1 Strategic Games . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52.2 Solution Concepts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72.3 Elements of Complexity Theory . . . . . . . . . . . . . . . . . . . . . . . . . 102.4 A Few Words on Encodings . . . . . . . . . . . . . . . . . . . . . . . . . . . 203 State of the Art and Our Contribution 234 Ranking Games 294.1 An Introductory Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . 304.2 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 314.3 The Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 324.