max planck institut
mpii logo Minerva of the Max Planck Society

Algorithmic Game Theory (SS 2011)

Basic Information

Lecture time: Monday 14-16
Lecture room: 024, Campus E 1.4
Lecturers: Kurt Mehlhorn,Rob van Stee
Tutorial time: Friday 14-15
Tutorial room: 024, Campus E 1.4
Tutor: Vincent van der Weele
Audience: The course counts as computer science lecture (4 SWS, 6 CP). The lecture will be given in English.

Schedule: The first lecture will take place on Monday, April 11.
Exercises: We will hand out exercises every week and each student should score at least 50% in the first half of the course and 50% in the second half in order to be allowed to take the exam.
Final Exam: Oral exams took place on July 26-28, 2011, see the schedule. The exam consists of two parts. In the first part of the exam, we ask you to present a topic of your choice, in the second half we will ask questions. Certificates (Scheine) are available in Room 302.
Re-Exam: October 6-7, 2011. Contact Rob van Stee for an appointment.
Book: Algorithmic Game Theory


The Internet is a structure that has not been created by a single entity, but rather emerged from the interaction of many agents, individuals or companies. Agents normally aim at maximizing their individual benefits. For example, an individual might want to minimize the cost he pays for an item from an online store, or to maximize the bandwidth they get from a service provider. These agents can be viewed as players in a large, distributed game that aim at maximizing their individual utilities, possibly at the cost of other players.

This class will focus on algorithmic aspects of economics and game theory as they arise in modern information networks. We will cover a range of topics at the intersection of classical game theory and algorithm design, such as equilibrium concepts, mechanism design, auctions, non-cooperative and cooperative games, inefficiency of equilibria.


Date Topic Reference Homework Solutions Lecturer
Apr 11 Introduction to game theory Chapter 1 1 1 van Stee
Apr 18 Two-player zero-sum games, best responses 1.4, 2.1 2 2 van Stee
May 2 Lemke-Howson 2.2-3 3 3 van Stee
May 9 VCG-mechanisms 9.1-3 4 4 Mehlhorn
May 16 Combinatorial auctions 11.1-2 5 5 van Stee
May 23 Single-minded bidders 11.2-3 6 6 van Stee
May 30 Walras equilibria, inefficiency of equilibria 11.3, 17.1-2 7 (NEW!) 7 van Stee
June 6 The price of anarchy for load balancing 20 8 8 Sauerwald
June 20 Combinatorial Auctions, Revisited 11.1 -- 11.3 -- -- Mehlhorn
June 27 Cost Sharing 15 9 9 Mehlhorn
July 4 Cost Sharing 15 10 10 Mehlhorn
July 11 Cost Sharing 10 10 Mehlhorn
July 18 Maximizing Ad-Auctions Revenue Notes 11 11 Mehlhorn
---- Note: no exercise sheet on June 20th. ----

Results of Exercises

In the score table, the scores for the exercises so far are given. Every assignment is worth 20 points (5 per exercise, there are some exceptions...).


October 7, room 309a (corner office on third floor of MPI building).

14:00 2536235
14:30 2535467
15:00 2536254
15:30 2521481

More Courses of the Algorithms and Complexity Group
Search MPII (type ? for help)