Seminar Nebenläufige und Stochastische Spiele

WS 2006/07

Organisation

Die Veranstaltung wird als Blockseminar angeboten, eine Vorbesprechung findet am Mittwoch, den 13. September 2006 um 11 Uhr in Raum 4116 (Seminarraum des Lehrstuhls) statt. Die Vorträge finden voraussichtlich Ende Januar statt und können wahlweise auf deutsch oder englisch gehalten werden.

Zeitplan

17.10. Konzept
30.10. Gliederung
27.11. Ausarbeitung
18.12. Endgültige Fassung
8.01. Folien
25./26.01. Vorträge

Programm

Donnerstag, 25. Januar
10:30 11:15 Jonas Dieckelmann The Complexity of Simple Stochastic Games
11:15 12:00 Thomas Kurpick Perfect-Information Stochastic Parity Games
12:00 13:30 Mittagspause
13:30 14:15 Daniela Eßer Concurrent Reachability Games
14:15 15:00 Frank Fiedler Concurrent ω-regular Games
15:15 16:00 Wenyun Quan Quantitative Solutions of ω-regular Games
Freitag, 26. Januar
9:45 10:30 André Fischer Trading Probability for Fairness
10:45 11:30 Christopher Manthei Recursive Markov Decision Processes and Recursive Stochastic Games
11:30 12:15 Michael Köllejan Recursive Concurrent Stochastic Games
12:00 13:30 Mittagspause
13:45 14:30 Tom Goeckel Nash Equilibria in Stochastic Games
14:30 15:15 Roman Rabinovich Antichains: A New Algorithm for Checking Universality of Non-Deterministic Finite Automata

Themen

Thema Vortragende(r) Betreuer(in) Literatur
The Complexity of Simple Stochastic Games Jonas Dieckelmann T. Ganzow [Con92, Con93]
Concurrent Reachability Games Daniela Eßer L. Kaiser [dAHK98]
Concurrent ω-regular Games Frank Fiedler L. Kaiser [dAH00]
Perfect-Information Stochastic Parity Games Thomas Kurpick V. Bárány [Zie04, CJH04]
Quantitative Solutions of ω-regular Games Wenyun Quan T. Ganzow [dAM01, dAM04]
The Complexity of Quantitative Concurrent Parity Games Thomas Klapdor V. Bárány [CdAH06]
Trading Probability for Fairness André Fischer T. Ganzow [JKH02]
Stochastic Games with Branching-Time Winning Objectives Sebastian Bitzen V. Bárány [BBFK06a, BBFK06b]
Recursive Markov Decision Processes and Recursive Stochastic Games Christopher Manthei M. Ummels [EY05, EY06a]
Recursive Concurrent Stochastic Games Michael Köllejan M. Ummels [EY06b]
Nash Equilibria in Stochastic Games Tom Goeckel M. Ummels [CJM04, Cha05b]
Concurrent Games with Tail Objectives Christoph Güdelhöfer L. Kaiser [Cha05a]

Inhalt

Nebenläufige und stochastische Spiele sind ein fundamtentales Hilfsmittel im Bereich der Systemmodellierung und Controller-Optimierung. Im Unterschied zu zugbasierten Spielen, bei denen jeweils ein Spieler am Zug ist und eine Aktion wählt, wählen die Spieler in nebenläufigen Spielen gleichzeitig ihre Aktionen. In stochastischen Spielen legen diese gewählten Aktionen keinen eindeutigen Nachfolgezustand fest, sondern bestimmen eine Wahrscheinlichkeitsverteilung über möglichen Nachfolgezuständen.

Untersucht werden sollen verschiedene Spielmodelle (zugbasiert/nebenläufig, 1-/2-/n-Spieler) mit unterschiedlichen Gewinnbedingungen auf verschiedenen Spielgraphen im Hinblick auf Determiniertheit (hat immer ein Spieler eine Gewinnstrategie?), Art der Gewinnstrategien (positional, mit endlichem Speicher, randomisiert) und Komplexität des Entscheidungsproblems "welcher Spieler gewinnt von einer Position aus?" sowie des Berechnungsproblems der zugehörigen Gewinnstrategie.

Literatur

Zuordnung

  • Informatik (D)/Hauptstudium/Theoretische Informatik
  • Mathematik (D)/Hauptstudium/Reine Mathematik
  • Informatik (S II)
  • Mathematik (S II)/Hauptstudium/D: Angewandte Mathematik

Voraussetzungen

  • Vorlesung Mathematische Logik, Bewerber mit Vorkenntnissen in entsprechenden Themengebieten werden bevorzugt berücksichtigt.

Rückfragen

Erich Grädel, Vince Bárány, Tobias Ganzow, Łukasz Kaiser, Michael Ummels