Skip to main content

Winter 2019/20

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:

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

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.

DateTopic
15/10/19Introduction: Games and equilibria
21/10/19Inclusion theorem and existence of equilibria
22/10/19Potential games, Exercise Set 1
28/10/19Efficiency of equilibria, Non-atomic routing games, Price of anarchy
29/10/19Exercise Set 2
04/11/19Price of anarchy bounds for (non-)atomic routing games
05/11/19Exercise Set 3
11/11/19Smooth games and POA bounds
12/11/19Coordination mechanisms for scheduling games
18/11/19Mechanism design
19/11/19NO LECTURE!!!
25/11/19VCG auctions, sponsored search
26/11/19Exercises
02/12/19Optimal auctions
03/12/19How to compute optimal auctions and more.
09/12/19Simple near-optimal auctions
10/12/19Exercise set 8
16/12/19Mechanisms without money
17/12/19Mechanisms without money part 2, exercise set 9
06/01/20Voting and ranking
07/01/20Voting and ranking cont., exercise set 10
13/01/20NO LECURE!!!
14/01/20NO LECURE!!!
20/01/20Student presentations, please be present
21/01/20Student presentations, please be present
27/01/20Cost-sharing, exercise set 11
28/01/20Final lecture: recap and exam preparation
24/02/20Exams