Logic and Games

WS 2015

News

  • Zum zweiten Prüfungstermin werden mündliche Prüfungen abgehalten. Zur Terminvereinbarung wenden Sie sich bitte an Erich Grädel.
  • Die vorläufigen Klausurergebnisse können hier eingesehen werden. Die Einsicht findet am Donnerstag, den 25.02., zwischen 13 und 14 Uhr im Seminarraum des Lehrstuhls (Raum 4116, E1, Informatikzentrum) statt.
  • Das Skript ist nun in der aktualisierten Fassung verfügbar.
  • Weitere Informationen zu iterierter Regret-Minimierung sind im Abschnitt Literatur zu finden.
  • Die Klausur findet am 22.02. um 14:30 Uhr im AH V statt.
  • Ab dem 06.11. findet die Übung regulär um 10:15 Uhr statt.
  • Studierende im Bachelor Informatik, die die Prüfung für den Bachelor anrechnen lassen, können sich nicht in Campus für die Veranstaltung anmelden. Eine Anmeldung zur Vorlesung und zur Übung ist in diesem Fall nicht notwendig, die Anmeldung zur Prüfung erfolgt per E-Mail an Svenja Schalthöfer. Studierende im Bachelor Mathematik können die Veranstaltung nur als vorgezogene Masterprüfung belegen. Um die Veranstaltung im Anwendungsfach Mathematik für den Master Informatik zu belegen, ist ein Antrag an den Prüfungsausschuss Informatik notwendig.
  • Exercises: You can hand in your exercises in groups of max. 3 students wednesdays in the box at our department or in the lecture. New exercise sheets will also be available wednesdays.

Schedule

Type Date Location   Organizer
V4 Mo 10:15 – 11:45 III Beginn 19. Oktober E. Grädel
Mi 12:00 – 13:30 AH III Beginn 28. Oktober E. Grädel
Ü2 Fr 10:15 – 11:45 AH I Beginn 30. Oktober S. Schalthöfer, M. Hoelzel, W. Pakusa

Coursework

Lecture Notes

Content

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.

Literature

[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] J. Y. Halpern and R. Pass. Iterated regret minimization: A new solution concept. Games and Economic Behavior, vol. 74(1), pp. 184–207, 2012.
[9] M. J. Holler and G. Illing. Einführung in die Spieltheorie. Springer-Verlag, 2000.
[10] P. Morris. Introduction to Game Theory. Springer-Verlag, 1994.
[11] R. B. Myerson. Game Theory: Analysis of Conflict. Harvard University Press, 1991.
[12] J. von Neumann and O. Morgenstern. Theory of Games and Economic Behavior. John Wiley and Sons, 1944.
[13] M. J. Osborne. An Introduction to Game Theory. Oxford University Press, 2003.
[14] M. J. Osborne and A. Rubinstein. A Course in Game Theory. MIT Press, 1994.
[15] G. Owen. Game Theory. Academic Press, 1995.
[16] D. Perrin and J. Pin. Infinite Words (Automata, Semigroups, Logic and Games). Elsevier, 2004.

Prerequisites

  • Mathematische Logik

Classification

  • Mathematik (M.Sc.): Reine Mathematik
  • Informatik (M.Sc.): Theoretische Informatik
  • Lehramtskandidaten Informatik: Mathematische Methoden der Informatik (C)
  • Software Systems Engineering (M.Sc.): Theoretical Computer Science

Contact

Erich Grädel, Matthias Hoelzel, Svenja Schalthöfer, Wied Pakusa