Games and Their Application in Computer Science

SS 2002


Type Date Location   Organizer
V2 Di 10:00 – 11:30 AH I Beginn 16. April J. Duparc, E. Grädel


Lecture Notes

  • Chapter 0: Contents [ps]
  • Chapter 1: Introduction [ps]
  • Chapter 2: Finite Games [ps]
  • Chapter 3: Infinite Two-Player Games with Perfect Information [ps]
  • Chapter 4: Applications [ps]


This course yields a "close encounter of the third kind" with the fine structure of the Playful Universe.

Game Theory originates from Economical Sciences, where it involves players' preferences among outcomes. The aim is to predict or prescribe rational patterns of behaviours for agents in various situations and explain stable behaviours of groups of agents.

In Computer Science, this subject recently involves themes about controlling behaviour of unrelyable agents on the Web. But Game Theory has many other applications in Computer Science. It is a very efficient tool for describing and analyzing problems with regard to effectivity. Also, it is a powerful mathematical framework that captures the aspect of interaction in a very natural way. A software module, e.g., can be understood as an agent playing a possibly infinite game against its environment. Specifying a module amounts to formally describing a game, while synthesizing it comes to computing a winning strategy, and verifying it against specifications relies on checking that a strategy is winning.

This lecture will be given in English.


[1] P. Blackburn, M. de Rijke, and Y. Venema. Modal Logic. Cambridge University Press, 2001.
[2] J. H. Conway and R. K. Guy. The book of numbers. Copernicus, 1996.
[3] J. H. Conway. On numbers and games. Academic Press, 1976.
[4] K. Doets. Basic Model Theory. CSLI Publications, 1996.
[5] A. S. Kechris. Classical descriptive set theory. Springer, 1995.
[6] M. J. Osborne and A. Rubinstein. A course in game theory. MIT Press, 1994.
[7] C. Papadimitriou. Computational complexity. Addison-Wesley, 1994.
[8] K. Ritzberger. Foundations of Non-Cooperative Game Theory. Oxford University Press, 2002.
[9] J. van Benthem. Logic in games. Lecture notes of a course tought at Stanford, 2001.


  • Mathematische Logik


  • Informatiker: Theoretische Informatik, Vertiefungsfach, Anwendungsfach Mathematik
  • Mathematiker: Reine Mathematik, Angewandte Mathematik
  • Lehramtskandidaten: Angewandte Mathematik (D)
  • Software Systems Engineering (M.Sc.): Theoretical Computer Science