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.

Deadlines

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

Schedule

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

Topics

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]

Content

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.

Literature

[BBFK06a]	T. Brázdil, V. Brožek, V. Forejt, and A. Kučera. Stochastic Games with Branching-Time Winning Objectives. Technical Report. Faculty of Informatics, Masaryk University, Brno, Czech Republic, 2006.
[BBFK06b]	T. Brázdil, V. Brožek, V. Forejt, and A. Kučera. Stochastic Games with Branching-Time Winning Objectives. In Proceedings of the 21st IEEE Symposium on Logic in Computer Science, LICS 2006, pp. 349–358. IEEE Computer Society Press, 2006.
[CAH06]	K. Chatterjee, L. de Alfaro, and T. A. Henzinger. The complexity of quantitative concurrent parity games. In Proceedings of the 17th ACM-SIAM Symposium on Discrete Algorithms, SODA '06, pp. 678–687. ACM Press, 2006.
[CJH04]	K. Chatterjee, M. Jurdziński, and T. A. Henzinger. Quantitative stochastic parity games. In Proceedings of the 15th ACM-SIAM Symposium on Discrete Algorithms, SODA '04, pp. 121–130. ACM Press, 2004.
[CJM04]	K. Chatterjee, M. Jurdziński, and R. Majumdar. On Nash Equilibria in Stochastic Games. In Proceedings of the 13th Annual Conference of the Europan Association for Computer Science Logic, CSL '04, vol. 3210 of Lecture Notes in Computer Science, pp. 26–40. Springer-Verlag, 2004.
[Cha05a]	K. Chatterjee. Concurrent Games with Tail Objectives. Technical Report. EECS Department, University of California, Berkeley, USA, 2005.
[Cha05b]	K. Chatterjee. Two-Player Nonzero-Sum $\omega$-Regular Games. In Proceedings of the 16th International Conference on Concurrency Theory, CONCUR '05, vol. 3653 of Lecture Notes in Computer Science, pp. 413–427. Springer-Verlag, 2005.
[Con92]	A. Condon. The complexity of stochastic games. Information and Computation, vol. 96(2), pp. 203–224, 1992.
[Con93]	A. Condon. On Algorithms for Simple Stochastic Games. In Advances in Computational Complexity Theory (J. Cai, Ed.), vol. 13 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science, pp. 51–73. American Mathematical Society, 1993.
[EY05]	K. Etessami and M. Yannakakis. Recursive Markov Decision Processes and Recursive Stochastic Games. In Proceedings of the 32nd International Colloquium on Automata, Languages and Programming, ICALP '05, vol. 3580 of Lecture Notes in Computer Science, pp. 891–903. Springer-Verlag, 2005.
[EY06a]	K. Etessami and M. Yannakakis. Efficient Qualitative Analysis of Classes of Recursive Markov Decision Processes and Simple Stochastic Games. In Proceedings of the 23rd Annual Symposium on Theoretical Aspects of Computer Science, STACS '06, vol. 3884 of Lecture Notes in Computer Science, pp. 634–645. Springer-Verlag, 2006.
[EY06b]	K. Etessami and M. Yannakakis. Recursive Concurrent Stochastic Games. In Proceedings of the 33rd International Colloquium on Automata, Languages and Programming, ICALP '06, Part II, vol. 4052 of Lecture Notes in Computer Science, pp. 324–335. Springer-Verlag, 2006.
[JKH02]	M. Jurdziński, O. Kupferman, and T. A. Henzinger. Trading Probability for Fairness. In Proceedings of the 16th International Workshop on Computer Science Logic, CSL '02, vol. 2471 of Lecture Notes in Computer Science, pp. 292–305. Springer-Verlag, 2002.
[Zie04]	W. Zielonka. Perfect-Information Stochastic Parity Games. In Proceedings of the 7th International Conference on Foundations of Software Science and Computation Structures, FOSSACS '04, vol. 2987 of Lecture Notes in Computer Science, pp. 499–513. Springer-Verlag, 2004.
[dAH00]	L. de Alfaro and T. A. Henzinger. Concurrent Omega-Regular Games. In Proceedings of the 15th IEEE Symposium on Logic in Computer Science, LICS 2000, pp. 141–154. IEEE Computer Society Press, 2000.
[dAHK98]	L. de Alfaro, T. A. Henzinger, and O. Kupferman. Concurrent Reachability Games. In Proceedings of the 39th Annual Symposium on Foundations of Computer Science, FOCS '98, pp. 564–575. IEEE Computer Society Press, 1998.
[dAM01]	L. de Alfaro and R. Majumdar. Quantitative solution of omega-regular games. In Proceedings of the 33th Annual ACM Symposium on Theory of Computing, STOC '01, pp. 675–683. ACM Press, 2001.
[dAM04]	L. de Alfaro and R. Majumdar. Quantitative solution of omega-regular games. Journal of Computer and Systems Sciences, vol. 68(2), pp. 374–397, 2004.

Classification

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

Prerequisites

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

Contact

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