Lecturer: Yiannis Giannakopoulos
Weekly hours: 2+1
ECTS credits: 5
Lectures: October 18, 2021 – February 07, 2022
Tutorials: November 4, 2021 – February 10, 2022
| Class Type | Day | Time | Room |
|---|---|---|---|
| Lecture | Monday | 14:15 – 15:45 | Johann-Radon-Hörsaal (H13) |
| Tutorial | Thursday | 14:15 – 15:45 | 0.151-115 Elektrotechnik |
Office hours: Tuesdays, 13:30 – 15:00, online via Zoom (the link will be posted on StudOn).
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 Economic and Algorithmic Theory. 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 (the complexity of) computing equilibria, the price of anarchy, 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.
Basic knowledge of: calculus, probability theory, and linear/combinatorial optimization and/or algorithms & complexity
In particular, 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.
Disclaimer: This is 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.
We will not make use of a single “official” textbook; instead, lecture notes will be provided by the instructor after each lecture and uploaded to this web page (see below).
The following two textbooks include much of the material that we are going to cover in class and are highly recommended:
FAU students can get free electronic access to the book via the university’s network, through the Library.
The book is available online here, free of charge.
For convenience, we will use the shorthands [20LAGT] and [AGT], respectively, to cite these two books.
Further references to additional texts, resources, and specific research papers will be given during the semester (see the detailed outline below after each lecture).