Modulcode:	Inf-AGT
Englische Bezeichnung:	Algorithmic Game Theory
Modulverantwortliche(r):	Dr. Lasse Kliemann
Turnus:	jedes Jahr im SS (SS13 SS14)
Präsenzzeiten:	2V 2Ü
ECTS:	6
Workload:	30 h lectures, 80 h self study, 40 h exercise preparation, 30 h exercise sessions
Dauer:	ein Semester
Modulkategorien:	WI (BSc Inf (15)) WIAlg (BSc Inf) INF-Math (Inf. als NF) WI (MEd Inf) WPI (MEd Inf)
Lehrsprache:	Englisch
Voraussetzungen:	Inf-Math-A Inf-Math-B

Kurzfassung:

Algorithmic Game Theory plays at the intersection of Game Theory and Computer Science. On the one hand, we consider algorithmic questions from Game Theory, such as the computation of equilibria. On the other hand, we consider a game theoretic analysis of questions arising in Computer Science, such as how a computer system will perform when utilized by multiple non-cooperative users.

Lernziele:

This module will enable the student to understand current research literature in Algorithmic Game Theory and thus to write a Bachelor's or Master's thesis in this field.

Lehrinhalte:

• Pure and mixed Nash equilibria, existence results
• Computation of Nash equilibria in general strategic-form games, complexity theory
• Congestion games: structural properties, computation of equilibria, quantitative analysis of the inefficiency of equilibria (price of anarchy)
• Network formation: modelling, existence and computation of equilibria, price of anarchy
• Infinitely many players: variational inequalities, potential function, price of anarchy in point-to-point and multicast routing
• Extended equilibrium concepts

Weitere Voraussetzungen:

(Mathematics for Computer Scientists A and B) or (Analysis I, II and Linear Algebra I). Basic skills in Probability Theory, Complexity Theory, and Graph Theory are helpful but not required. The necessary basics will be taught on demand in this course.

Prüfungsleistung:

Oral exam. Exams can be taken as usual at the end of the current lecture period and at the beginning of the next lecture period.

Regular, active participation in exercise sessions is required in order to be admitted for an exam. Good performance in the exercise sessions will be taken into account for the final grade.

Lehr- und Lernmethoden:

Comprehensive lecture notes are provided. The relevant chapters should be read as a preparation for each lecture. The lectures provide a high-level overview how everything is interconnected; and most mathematical proofs are presented step by step in full detail. Written notes made during lectures are recorded electronically and provided for download.

In the exercise sessions, students are requested to present solutions. Solutions are also provided in beforehand via the lecture notes. Students may use these example solutions for the presentation.

Students are invited to ask questions and to engage in discussions during the exercise sessions and also during the lectures.

Verwendbarkeit:

This is an optional compulsory module (Wahlpflichtmodul) for BSc Computer Science. It is also suitable for MSc Computer Science in the field "Vertiefende theoretische Grundlagen".

Literatur:

• Lecture Notes, provided at the website of the module.
• Algorithmic Game Theory by Nisan, Roughgarden, Tardos, Vazirani. Freely available as PDF.
• A Course in Game Theory by Osborne und Rubinstein. Freely available as PDF (after registration).
• Multiagent Systems by Shoham und Leyton-Brown. Freely available as PDF.
• Theory Of Games And Economic Behavior by von Neumann and Morgenstern. Freely available as PDF.
• Essentials of Game Theory: A Concise Multidisciplinary Introduction by Leyton-Brown und Shoham. For $5 available as PDF.

Verweise:

Kommentar:

The language of this module is English. It can also be held in German, provided that all of the participants agree. The lecture notes will always be in English only.