Teaching

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.

Lecturer:

Dr. Ruben Hoeksma (Email)
Time & Room:

Mon 12-14 in room MZH 1110
Tue 12-14 in room MZH 6190
Start:
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.

Date Topic Material & suggested reading Exercises
15/10/19 Introduction: Games and equilibria Slides, notes Set 1
21/10/19 Inclusion theorem and existence of equilibria Slides, notes Set 2
22/10/19 Potential games, Exercise Set 1 See slides and notes of 21.10
28/10/19 Efficiency of equilibria, Non-atomic routing games, Price of anarchy Slides, notes Set 3
29/10/19 Exercise Set 2
04/11/19 Price of anarchy bounds for (non-)atomic routing games Slides, notes Set 4
05/11/19 Exercise Set 3
11/11/19 Smooth games and POA bounds Slides, proofs
12/11/19 Coordination mechanisms for scheduling games Slides, proofs Set 5