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

Description

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.

Lectures

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

Re-exam

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