Special Topics in Algorithmic Game Theory (MA5226)

TUM, Department of Mathematics, WS 2020/21

Lecturer: Yiannis Giannakopoulos
Tutorials: Themistoklis Melissourgos
Weekly hours: 2+1 (4+2 over 7 weeks)
ECTS credits: 5

News

Schedule (tentative!)

Lectures: November 5, 2020 – December 18, 2020
Tutorials: November 12, 2020 – January 8, 2021

Class Type Day Time Group
Lectures Thursday 10:15 – 11.45 A
Friday 10:15 – 11.45 B
Tutorials Thursday 12:00 – 13.30 1
Friday 12:00 – 13.30 2

Description

The main goal of this course is to highlight the intriguing interplay between optimality, simplicity, efficiency and robustness in the design and analysis of systems involving many different selfish strategic players, with an emphasis in the intersection between Economics and Theoretical Computer Science. Can we predict the possible outcomes of such dynamic situations? Can we motivate the players and design specific rules, so that those outcomes are stable and desirable? How well and how efficiently can we approximate the above objectives? These questions are very important and relevant in many modern, real-life applications, where the Internet has been established as the main platform for agent-interaction and computing.

We will demonstrate the above by focusing in some of the prototypical topics in the field of Algorithmic Game Theory, such as Optimal (Revenue-Maximizing) Auctions, the Price of Anarchy, Selfish Routing, Congestion and Potential Games, and Learning in Games such as Best-Response and No-Regret Dynamics.

The ambition of this class is to provide a crash course for beginning graduate or advanced-undergraduate students interested in getting a glimpse into the toolbox and the necessary fundamentals of some of the most important research areas within the field of Algorithmic Game Theory, after which they should feel comfortable to start following the related work on their own.

Prerequisites

The overlap in the material of this course with that of other AGT courses offered at TUM, most notably IN2239 or IN2211, is minimal. In particular, this course is a natural follow-up to more fundamental Game Theory classes like IN2239, and can also complement nicely combinatorial Mechanism Design course like IN2211; if you have taken any of those courses in the past and enjoyed them, then this might be the right class for you! Also, as stated in the prerequisites above, some prior knowledge on the basics of Game Theory (as given, e.g., by IN2239), though not absolutely necessary (see below), will be an advantage.


Disclaimer: Prior knowledge of Game Theory is not essential for being able to follow this class. For example, game-theoretic primitives such as the notion of Nash equilibrium, are going to be introduced and used on-the-fly, on a need-to-know basis as part of the various topics described above. Nevertheless, this is still a theory course. As such, emphasis will be given in rigorousness and mathematical proofs, and the language and feel of algorithmic analysis and optimization will have a dominant presence throughout the lectures. So, mathematical maturity is essential and prior exposure or familiarity with the basic notions of subjects like the Design and Analysis of Algorithms, Discrete Mathematics and Optimization, Computational Complexity, Randomized/Approximation Algorithms, Probability and (Real) Analysis is highly recommended.

Please feel free to contact the lecturer beforehand to discuss any doubts you may have about your background.


Main References

The main textbook for our course will be:

TUM students can get free electronic access to the book here (from within the Library’s network or via eAccess)

The following, known as “the AGT book”, is a standard reference text in the field. It might be slightly outdated at certain topics by now, and mostly aimed towards researchers (rather than students), but it is still a classic, covers way more material and we will repeatedly point to it throughout this class.

The AGT book is available online here, free of charge.

Further references to additional texts and specific research papers will be given during the class, and supplementary lecture notes will be uploaded here when needed (see the detailed outline below after each lecture).