University of Bonn · Institute of Computer Science · Algorithms and Complexity

Sidebar

Current Semester (WiSe 2024/25)

Bachelor
Master

MA-INF 1301: Algorithmic Game Theory and the Internet

Next Semester

Next semester, there will be a Seminar on Algorithmic Game Theory. Please contact us if you are interested. We will agree on a weekly time with all participants.

There will also be a lecture on Algorithms and Uncertainty. Drop by if you are interested.

Exam

The first round of exams will take place one July 31, August 1, August 2 and August 3. Please contact Matthias to be assigned a slot.

Some more notes regarding the exam

Getting to know concepts is an important learning objective. Therefore, it is crucial to know the definitions well and being able explain them. It is also important to be able to explain connections, which theorems we showed, and how we proceeded.

Some proofs const of longer, tedious calculations (especially in lectures 4, 7, 11, …). In the exam, you will not be asked to reproduce these. Instead, you should be able to explain the idea, where we started from, where ended up, which steps we took on the way.

You can take the exam in English, German, or any mix of these languages. As with any oral exam, it is an ideal preparation to practice responding to questions with fellow student. Especially, if you prefer to prepare the exam on your own, you should try explaining concepts. It really helps to askew typical questions aloud — even if no one listens.

Lecture

When Where Start Lecturer
Monday, 10:15-11:45
Friday, 12:15-13:45 		CP1-HSZ / HS 3
CP1-HSZ / HS 3 		April 9th Kesselheim

Tutorials

When Where Start Lecturer
Thursday, 10:15-11:45 2.050 April 19 Buttkus
Thursday, 14:15-15:45 2.050 April 19 Buttkus

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, and
  • maximizing revenue.

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.

Materials

Exercises

Further Reading

Page Tools

Imprint/Impressum