Teaching

Algorithmic game theory

Advanced course in Winter 2018/19


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.

Optionally, the seminar Highlights of Algorithms supplements this course very well by offering the chance to study in depth one specific result within the field of algorithmic game theory.

Students that want to extend the course to 8 ECTS (normally 6), should be present at the first meeting of the Highlights of Algorithms seminar (Thu 18.10 14:00 MZH 3150).

Lecturer:

Dr. Ruben Hoeksma (Email)
Time & Room:

Mon 14-16 in room MZH 1470
Tue 12-14 in room MZH 4140
Start:
Tuesday, October 16, 2018

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 half of the points from the exercises receive an extra 0.3/0.4 on top of their grade from the oral exam. Those students who obtain at least 90 percent of the points from the exercises receive an extra 0.6/0.7 (total) on top of their grade from the oral exam. That is, for example, from 3.0 to 2.7 or 2.3, or from 2.7 to 2.3 or 2.0. The final grade cannot be improved beyond 1.0 and a grade of 5.0 cannot be improved.

Literature: The course is based on parts of the literature below and recent research articles that will be added later.

Date Topic Material & suggested reading Exercises
16/10/18 Introduction: Games and equilibria Slides, Notes Set 1
22/10/18 Relation between equilibria, Finding MNE, Potential games Notes
23/10/18 Atomic routing games, Exercise set 1 See notes of 22/10 Set 2
29/10/18 Efficiency of equilibria, Non-atomic routing games, Price of anarchy Slides
30/10/18 Exercise set 2 Set 3
05/11/18 Bounds on POA for (non-)atomic routing games Slides, Notes
06/11/18 Exercise set 3 Set 4
12/11/18 Smoothness, Robust price of anarchy, Scheduling games Slides, Proofs
13/11/18 Exercise set 4 Set 5