max planck institut
informatik
informatik
Xiaohui Bei and Thomas Kesselheim
| Time: |
Lectures: Mondays, 16:15–18:00 Tutorials: Tuesdays, 16:15–18:00 (biweekly, see schedule) |
|---|---|
| First meeting: | April 27, 2015 |
| Room: | 024 on the ground floor of the MPI building (E1.4) |
| 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. |
| 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
|
| Credits: | 5 |
| Exercise Sets: |
Exercise Set 1, due May 4, 2015 Exercise Set 2, due May 18, 2015 Exercise Set 3, due June 8, 2015 Exercise Set 4, due June 22, 2015 Exercise Set 5, due July 13, 2015 Exercise Set 6, due July 27, 2015 |
| Lecture Notes: |
Lecture 1, Game-Theory Basics, April 27, 2015 Lecture 2, Introduction to Congestion Games, May 4, 2015 Lecture 3, Complexity of Equilibria in Congestion Games, May 11, 2015 Lecture 4, Online Learning and Coarse Correlated Equilibria, May 18, 2015 Lecture 5, Price of Anarchy, June 1, 2015 Lecture 6, Price of Stability and Strong Nash Equilibria, June 8, 2015 Lecture 7, Social Choice, June 15, 2015 Lecture 8, Mechanism Design Basics, June 22, 2015 Lecture 9, Single-Parameter Mechanisms, June 29, 2015 Lecture 10, VCG, July 6, 2015 Lecture 11, Revenue-Maximizing Auctions, July 13, 2015 Lecture 12, Near-Optimal Auctions, July 20, 2015 (lecture note by Tim Roughgarden) Lecture 13, Mechanism Design without Money, July 27, 2015 |
| Tutorial Schedule: |
Tutorials will take place on May 5 May 19 June 9 June 23 July 14 July 28 |
| E-Mail Announcements: | |
| Literature: |
|