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).


Dr. Ruben Hoeksma (Email)
Time & Room:

Mon 14-16 in room MZH 1470
Tue 12-14 in room MZH 4140
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 below literature serve as a great source for further reading. The course was based on parts of some of these.

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
19/11/18 Coordination mechanisms in scheduling games Slides, Proofs
13/11/18 Exercise set 5 Set 6
26/11/18 Mechanism design Slides, Notes
27/11/18 Exercise set 6 Set 7
03/12/18 VCG auctions Slides, Notes
04/12/18 Exercise set 7 Set 8
10/12/18 Revenue optimal auctions Slides
11/12/18 Computing revenue optimal auctions, Exercise set 8 Set 9
17/12/18 Simple near-optimal auctions Slides
18/12/18 Exercise set 9 Set 10
07/01/19 Mechanisms without money, house allocation, stable matching Slides
08/01/19 Exercise set 10 Set 11
14/01/19   — 22/01/19 NO LECTURE: reading assignment on voting + exercises (set 11 - due AT THE START of the lecture of 28/01/19!!) L25* and L26 (Voting I and II) of [5] and Section 4 from l3 (Strategic voting) of [3]
28/01/19 Exercise set 11
29/01/19 Last lecture: recap and exam preparation Slides
*: There are two minor though important typos in L25. On page 2: "...who they prefer to B." should be "...who they prefer to A." On page 4, in the proof of Lemma 25.11: "...moving B to the same position as in \(\succ_{i'}\)..." should be "...moving B to the same position as in \(\succ_{i'}^*\)..."