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:

• Dr. Ruben Hoeksma

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.

• [1] Noam Nisan, Tim Roughgarden, Eva Tardos, and Vijay V. Vazirani. Algorithmic Game Theory
  (Go to "Resources" → "General Resources" → "Algorithmic Game Theory" → "Algorithmic Game Theory")
• [2] Jason D. Hartline. Mechanism Design and Approximation
• [3] Tim Roughgarden. Lecture notes - Incentives in Computer Science (CS269I, fall 2016)
• [4] Tim Roughgarden. Lecture notes - Algorithmic Game Theory (CS364A, fall 2013)
• [5] Thomas Kesselheim. Lecture notes - Algorithmic Game Theory, Summer 2019