I7 Logo
Chair for Foundations of Software Reliability and Theoretical Computer Science
Informatik Logo TUM Logo
Courses

Spieltheorie
held by: Dr.-Ing. Jörg Kreiker
Dr. Stefan Kiefer
held in: WS 2008/2009
sws: 2
ects: 4
Inhalt

Spieltheorie (engl. game theory) beschäftigt sich mit der (formalen, mathematischen) Analyse von Situationen, in denen mehrere Entscheidungsträger ("Agenten") interagieren. Ein bekanntes Beispiel für eine derartige Situation ist das sogenannte Gefangenendilemma (prisoner's dilemma).

Spiele im herkömmlichen Sinn sind nur ein (sehr spezielles) Beispiel für solche Situationen. Spieltheorie findet darüber hinaus breite Anwendung bei der Analyse ökonomischer, gesellschaftlicher, politischer und biologischer Phänomene wie etwa der Konkurrenz zwischen Firmen, dem Wettstreit um Wählerstimmen, der Urteilsfindung in einem Prozess, dem Bieterverhalten in Auktionen oder dem Kampf um Nahrungsreserven.

Die Vortragsthemen dieses Proseminars sind in drei Gebiete aufgeteilt. Im ersten Teil geht es um die klassische Spieltheorie, basierend auf dem Buch von Osbourne. Danach widwen wir uns der komplexitätstheoretischen Analyse von Spielen. Schließlich schauen wir, was Computer tun, um Spiele (gegen Menschen oder andere Computer) gut spielen zu können.

Im Einzelnen werden folgende Themen behandelt:

  • Spieltheorie: Nash-Gleichgewichte, surreal numbers.
  • Komplexität von Spielen: Minesweeper, Tetris, Zero-Knowledge-Protokolle (Sudoku).
  • Wie Computer Spiele spielen: Adversarial Search, Computer Hex, Proof Number Search.