Next semester, we will offer a seminar and a lab, which are both on topics of algorithmic game theory. Please contact Thomas Kesselheim if you are interested. The lab will probably much more fun with many participants.

When | Where | Start | Lecturer |
---|---|---|---|

Monday, 10:15-11:45 Wednesday, 12:15-13:45 | CP1-HSZ / HS 3 CP1-HSZ / HS 3 | April 1 | Kesselheim |

To be assigned a time slot for the exam, please send an e-mail to Thomas Kesselheim.

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. Even a last-minute cancellation is better than a no-show. Of course, make sure that you also follow the official procedures (if applicable).

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.

- Lecture Notes Apr 8, 2019 (Normal-Form Games and Mixed Nash Equilibria) (update Apr 11: Added a step in proof of Lemma 3.10)
- Lecture Notes Apr 17, 2019 (Correlated Equilibria) (update Apr 23: Corrected another typo in definition)
- Lecture Notes Apr 24, 2019 (Minimizing External Regret) (update May 16: fixed typo in proof of Proposition 7.6)
- Lecture Notes Jul 10, 2019 (Cost Sharing) (Corrected proof of Lemma 25.7 in comparison to lecture.)

- Exercise Set 8, due May 29 (update May 21: fixed reference in exercise 5b)
- Exercise Set 10, due June 19 (updated due date)

- 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