Algorithmic Game Theory (Summer 2026)
Topical
- Logbook, with details about schedule and material.
- There are no lectures on 18 May and 20 May.
- There are no lectures on 25 May and 27 May.
Organizational
- Lecturer: Prof. Dr. Martin Hoefer
- Exercises: Svenja Griesbach, Jakob Lindner
- RWTH Online: course page, exercise page
- Room in RWTH Moodle
- Lectures:
Mondays, 14:30 - 16:00h in 5056 (Informatikzentrum)
Wednesdays, 12:30 - 14:00h in 5056 (Informatikzentrum) - Exercises: TBD
- First Exam: Jul 30, 2026. (written exam)
- Second Exam: Sep 3, 2026. (written exam)
Material
Slides and Notes
| Chapter | Updates | Lectures | |
|---|---|---|---|
| Organizational | Slides | 12.04.2026 | 1 |
| Strategic Games and Nash Equilibrium | Slides | 12.04.2026 | 1-3 |
Lecture Notes
German lecture notes from a previous version of this course are available here.Exercise Sheets
Weekly exercise sheets will be published here. Solutions must be composed by groups of (initially) 3 students.
Your solutions must be submitted as a single PDF file via Moodle.
You must score at least 50% of the total number of points to be admitted to the exam. If you score at least 75%, you can obtain one grading step bonus for the exam. To receive the bonus, you must pass the exam, and at least one solution must be presented during an exercise session.
Content
The course provides an introduction to theoretical and algorithmic foundations of systems that involve strategic and economic interaction of rational agents. These systems arise frequently in modern computer networks -- service providers strive to route packets as quickly or cheap as possible, in cloud computing the resources (such as computing time or memory) are shared, rented or sold, advertisers want to place their ads as prominently as possible and pay as little as possible, etc. The business model of many companies relies on trade and marketing in computational markets on the Internet.
In algorithmic game theory we design and analyze algorithms for elementary allocation and pricing problems that are motivated by systems with many rational agents. The algorithms search for optimal strategies for single users, or they try to optimize social welfare in the system while addressing strategic behavior of users. The goals are a characterization of incentives, as well as provable bounds on running time and solution quality. In the course, we will introduce basic ideas from game theory and combine them with techniques from approximation algorithms, distributed computing, and complexity theory.
Literature
Directly related to the course material:
- [EK] Easley, Kleinberg. Networks, Crowds, and Markets. Cambridge University Press, 2010.
Access here. - [NRTV] Nisan, Roughgarden Tardos, Vazirani. Algorithmic Game Theory. Cambridge University Press, 2007.
Non-printable PDF here. - [R] Roughgarden. Twenty Lectures in Algorithmic Game Theory. Cambridge University Press, 2016.
- [RBLR] Rothe, Baumeister, Lindner, Rothe. Einführung in Computational Social Choice. Spektrum Verlag, 2012. Access with RWTH University license here.
Many textbooks cover background and context in game theory, e.g.,
- [M] Myerson. Game Theory: Analysis of Conflict. Harvard University Press, 1991.
- [O] Owen. Game Theory. Academic Press, 2001.
- [OR] Osborne, Runbinstein. A Course in Game Theory. MIT Press, 1995.
- etc...