Special Topics in Algorithmic Game Theory (MA5226)

TUM, Department of Mathematics, SS 2018

Lecturer: Yiannis Giannakopoulos Teaching Assistant: Diogo Poças Weekly hours: 2+1 (4+2 over 7 weeks) ECTS credits: 5

News

Schedule

Duration: April 11, 2018 – May 25, 2018 (Tutorials start on April 20)

Class Type Day Time Room Lecturer
Lecture Wednesday 10:15 – 11.45 MI 02.04.011 Υ. Giannakopoulos
Friday 10:15 – 11.45 MI 02.04.011 Υ. Giannakopoulos
Tutorial Friday 12:15 – 13.45 MI 02.04.011 D. Poças

Office hours: Wednesdays & Fridays, 13:00–15:00, Room 02.04.061 (for the duration of the course); or after email appointment.

Exam: Friday, June 15, 2018 – 16:15 – Interims Hörsaal 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, Scheduling Unrelated Machines, 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 the standard reference text in the field. It might be slightly outdated at some specific 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 (under the “Resources” tab), free of charge.

For convenience, we will use the shorthands [20LAGT] and [AGT], respectively, to cite the two main references mentioned above.

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).

Outline of Lectures & References

Exercises

Instructions for handing-in your solutions: either bring them, in person, by the end of Wednesday’s lecture (to Yiannis), or send them via email (to Diogo); in the latter case, make sure to submit your work as a single file.