Please find further details in the eCampus course.

There will be no lectures in the lecture hall. Instead we will upload 2 prerecorded lecture videos every week, which you can watch in your own time at home. Additionally there will be a Recap and Reflect Session every Wednesday. During these sessions, we'll briefly summarize the key points covered in the week's lectures, offer a platform for any questions you may have, and facilitate discussions around simple exercises to reinforce your understanding of the new topics.

The first exam period is scheduled for the week of July 15 as well as the week of August 5.

The second exam period is scheduled for the week of September 2.

The exams will be oral and about 25-30 minutes long. There is a requirement for participating in the exams. Once during the semester, you need to present a solution for one of the homework exercises to your fellow students in the tutorial sessions. If you would like to present a solution in one of the tutorials, please send an email to Anna Heuser until Tuesday 10:00 pm including the task you would like to present in which of the tutorial sessions. Of course, sending the email earlier than Monday evening is also possible and recommended. After you have received the confirmation, we will schedule a short meeting (10-15min) for a quick pre-discussion on your solution.

Throughout the world of modern computer networks, there are environments in which participants act strategically. Just consider internet service providers, which strive to route packets as cheaply as possible. Another example are cloud-based services: End-users and service providers rent remote infrastructure for storage or computations, giving rise to huge markets. Last but not least, advertisers want to reach their audience as cheaply as possible. This is the foundation of the business models of the world’s largest companies.

In all these settings, algorithms either act as selfish agents or have to cope with such. This brings about novel questions that are out of the scope of traditional algorithmic theory. Algorithmic game theory, a research direction at the intersection of game theory and algorithm design, has emerged to provide answers. On the one hand, this means to take analytical point of view and to strive to explain the performance of a given system. On the other hand, one also takes engineering perspective, asking how to design systems so that they can cope with selfishly acting agents.

In this course, we will introduce you to the foundations of algorithmic game theory, including

• basic game theory,
• computability and hardness of equilibria,
• convergence of dynamics of selfish agents,
• (bounds on the) loss of performance due to selfish behavior,
• designing incentive-compatible auctions
• maximizing revenue, and
• designing mechanisms for stable and fair allocations without money.

You should bring a solid background in algorithms and calculus. No prior knowledge on game theory is required. Specialized knowledge about certain algorithms is not necessary.

• Problem Set 1, due April 23
• Problem Set 2, due April 30
• Problem Set 3, due May 14
• Problem Set 4, due June 04
• Problem Set 5, due June 11
• Problem Set 6, due June 18
• Problem Set 7, due June 25
• Problem Set 8, due July 2
• Problem Set 9, due July 9
• Problem Set 10, due July 16

• Problem Set 0
• Problem Set 1
• Problem Set 2
• Problem Set 3
• Problem Set 4
• Problem Set 5
• Problem Set 6
• Problem Set 7
• Problem Set 8
• Problem Set 9
• Problem Set 10
• Problem Set 11

• Algorithmic Game Theory, edited by Nisan, Roughgarden, Tardos, and Vazirani, available online under “Resources”
• Twenty Lectures on Algorithmic Game Theory, by Tim Roughgarden; also see his original lecture notes that are available online
• Game Theory, Alive! by Karlin and Peres, available online
• Multiagent Systems by Shoham and Leyton-Brown, available online
• Lecture notes on Algorithmic Mechanism Design by Jason Hartline, available online