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.