Algorithmic game theory
Advanced course in Winter 2019/20
Classic optimization theory assumes complete knowledge of the parameters of a problem and complete control over the outcome. In reality, these assumptions might fail and both information and decisions may be divided over different agents, each with their own objectives. These are the types of problems that we treat in algorithmic game theory.
This course offers an introduction into the field of algorithmic game theory. We develop an understanding of the core concepts in algorithmic game theory, such as equilibria, price of anarchy and price of stability, coordination mechanisms and auctions.
The core proficiencies that you will learn are
- identification of different types of equilibria,
- proving existence of pure Nash equilibria,
- proving upper and lower bounds on the price of anarchy for non-atomic routing games and smooth games,
- analyzing the second price and VCG auctions,
- analyzing revenue maximizing auctions.
Time & Room:
- Mon 12-14 in room MZH 1110
- Tue 12-14 in room MZH 6190
No lectures on:
- 19.11.2019 and 13-14.01.2020
- Tuesday, October 15, 2019
Examination: is through a regular oral exam (Mündliche Prüfung).
Exercises: Exercises are not mandatory, yet highly recommended. Those students who obtain at least 60 percent of the points from the exercises receive an extra 0.3/0.4 on top of their grade from the oral exam. The final grade cannot be improved beyond 1.0 and a grade of 5.0 cannot be improved.
Literature: The below literature serves as a great source for further reading. The course was based on parts of some of these.
-  Noam Nisan, Tim Roughgarden, Eva Tardos, and Vijay V. Vazirani. Algorithmic Game Theory
(Go to "Resources" → "General Resources" → "Algorithmic Game Theory" → "Algorithmic Game Theory")
-  Jason D. Hartline. Mechanism Design and Approximation
-  Tim Roughgarden. Lecture notes - Incentives in Computer Science (CS269I, fall 2016)
-  Tim Roughgarden. Lecture notes - Algorithmic Game Theory (CS364A, fall 2013)
-  Thomas Kesselheim. Lecture notes - Algorithmic Game Theory, Summer 2019
|15/10/19||Introduction: Games and equilibria|
|21/10/19||Inclusion theorem and existence of equilibria|
|22/10/19||Potential games, Exercise Set 1|
|28/10/19||Efficiency of equilibria, Non-atomic routing games, Price of anarchy|
|29/10/19||Exercise Set 2|
|04/11/19||Price of anarchy bounds for (non-)atomic routing games|
|05/11/19||Exercise Set 3|
|11/11/19||Smooth games and POA bounds|
|12/11/19||Coordination mechanisms for scheduling games|
|25/11/19||VCG auctions, sponsored search|
|03/12/19||How to compute optimal auctions and more.|
|09/12/19||Simple near-optimal auctions|
|10/12/19||Exercise set 8|
|16/12/19||Mechanisms without money|
|17/12/19||Mechanisms without money part 2, exercise set 9|
|06/01/20||Voting and ranking|
|07/01/20||Voting and ranking cont., exercise set 10|
|20/01/20||Student presentations, please be present|
|21/01/20||Student presentations, please be present|
|27/01/20||Cost-sharing, exercise set 11|
|28/01/20||Final lecture: recap and exam preparation|