Logik und Spiele

SS 2007

Aktuelles

  • Die Folien zur Vorlesung am 6. Juli stehen zum Herunterladen zur Verfügung.
  • Übungsbetrieb: Die Übungen können in Gruppen bearbeitet werden (max. 3 Studenten) und sind spätestens dienstags um 12 Uhr im Kasten am Lehrstuhl (bzw. zuvor in der Vorlesung) abzugeben. Neue Aufgabenblätter werden in der Regel ab dienstags auf der Homepage verfügbar sein. Das erste Aufgabenblatt muss erst bis zum Beginn der Übung am Mittwoch (17:15 Uhr) abgegeben werden.

Termine

Art Termin Ort   Veranstalter
V4 Di 10:00 - 11:30 AH I Beginn 17. April E. Grädel
Fr 10:00 - 11:30 AH I Beginn 20. April E. Grädel
Ü2 Mi 17:15 - 18:45 5056 Beginn 25. April E. Grädel

Übungen

Materialien

  • Folien zu den Vorlesungen vom 17. bis 27. April [pdf]
  • Folien zu der Vorlesung am 6. Juli [pdf]

Inhalt

Lernziele

Verständnis der grundlegenden Begriffe und Probleme der algorithmischen Spieltheorie und der Zusammenhänge von Logik und Spieltheorie. Kenntnis der logischen und algorithmischen Methoden zur Behandlung unendlicher Spiele. Verständnis der Anwendungen unendlicher Spiele als Modell reaktiver Systeme und zur Auswertung logischer Formeln.

Themen

Fundamentale Modelle und Begriffe der Spieltheorie. Endliche und unendliche Spiele. Model-Checking-Spiele. Determinierte und nichtdeterminierte Spiele. Borel-Spiele, Muller-Spiele und Paritätsspiele. Komplexität und Definierbarkeit von Gewinnregionen. Algorithmische Synthese und Optimierung von Gewinnstrategien. Mehrpersonenspiele.

Literatur

[1] K. Binmore. Fun and Games: A Text on Game Theory. D.C. Heath, 1992.
[2] R. Fagin, J. Y. Halpern, Y. Moses, and M. Y. Vardi. Reasoning about Knowledge. MIT Press, 1995.
[3] J. Filar and K. Vrieze. Competitive Markov decision processes. Springer-Verlag, 1996.
[4] D. Fudenberg and J. Tirole. Game Theory. MIT Press, 1991.
[5] E. Grädel. Finite Model Theory and Descriptive Complexity. In Finite Model Theory and Its Applications, pp. 125–230. Springer-Verlag, 2007.
[6] E. Grädel, W. Thomas, and T. Wilke (Eds.). Automata, Logics, and Infinite Games. Springer-Verlag, 2002.
[7] J. Y. Halpern. Reasoning about Uncertainty. MIT Press, 2003.
[8] M. J. Holler and G. Illing. Einführung in die Spieltheorie. Springer-Verlag, 2000.
[9] P. Morris. Introduction to Game Theory. Springer-Verlag, 1994.
[10] R. B. Myerson. Game Theory: Analysis of Conflict. Harvard University Press, 1991.
[11] J. von Neumann and O. Morgenstern. Theory of Games and Economic Behavior. John Wiley and Sons, 1944.
[12] M. J. Osborne. An Introduction to Game Theory. Oxford University Press, 2003.
[13] M. J. Osborne and A. Rubinstein. A Course in Game Theory. MIT Press, 1994.
[14] G. Owen. Game Theory. Academic Press, 1995.
[15] D. Perrin and J. Pin. Infinite Words (Automata, Semigroups, Logic and Games). Elsevier, 2004.

Voraussetzungen

  • Mathematische Logik

Zuordnung

  • Informatiker: Theoretische Informatik, Vertiefungsfach, Anwendungsfach Mathematik
  • Mathematiker: Reine Mathematik
  • Lehramtskandidaten Informatik: Mathematische Methoden der Informatik (C)
  • Software Systems Engineering (M.Sc.): Theoretical Computer Science
  • Sonstige: Informatik

Leistungsnachweis

  • Informatiker und Mathematiker: Übungsschein bei aktiver Teilnahme an den Übungen
  • Software Systems Engineering (M.Sc.): active participation in exercises and final examination

Rückfragen

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