MA-INF 1301: Algorithmic Game Theory

Please find further details in the eCampus course.

Lecture

When Where Start Lecturer
Two lectures per week online, prerecorded October 11 Kesselheim

Q&A - Session

When Where Start Lecturer
Wednesday, 12:15-12:45 online October 11 Kesselheim

Tutorials

When Where Start Lecturer
Thursday, 10:15-11:45 Meckenheimer Allee 176, Lecture Hall IV October 14 Braun
Thursday, 14:15-15:45 online October 14 Braun

Exams

The exams will be oral, about 25-30 minutes long, and take place as a video conference via Zoom. You will need to show and identify yourself on camera. It does not matter whether it is a computer or a smartphone. No other hardware is required. If you would like to take the exam but not in this form as a video conference, please contact us.

The first period will take place on February 14, 15 and 17. Please contact Alexander Braun by February 4 to be assigned a time slot. Please also state your first and second most preferred day for the exam. This year, you will receive a confirmation of the day of your exam immediately within a day or two, the exact time will only be announced a few days before the exam. If you do not plan to take the exam in the first period, you can also be assigned a time slot for the second period already, which will be on March 14, 15 and 16. Still, we also assign time slots for the second period later in February.

One more thing: If you have been assigned a time slot but then decide to not take the exam, please remember to cancel it. It is very important for us to know that you will not show up because otherwise we will be waiting for you. In this case, send an e-mail to Thomas Kesselheim or Alexander Braun. Even a last-minute cancellation is better than a no-show. Of course, make sure that you also follow the official procedures (if applicable).

Content

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.

Prerequisites

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 Sets - Tutorials

Problem Sets - Homework

Further Reading


Page Tools