Algorithmic game theory (AGT) is a rapidly growing research area that lies in the intersection of mathematics, theoretical computer science and economic theory. It uses game-theoretical models and solution concepts to study situations of strategic decision making, with a particular focus on computational and algorithmic issues. It combines methodologies and techniques from discrete optimization, algorithms and complexity, game theory, mechanism design, etc.
The aim of the course is to learn about fundamental results in AGT, but also to get acquainted with the existing state-of-the-art techniques. Ideally, at the end of the course you would be able to pursue your own research project in AGT.
The idea is to cover a broad range of topics (as indicated below); but depending on the interest of the course participants, we might also change or adapt the focus a bit accordingly. A selection of topics that will be covered in the course are:
Besides the material covered in class, we will sometimes also ask you to study some material on your own and to solve three take-home assignments (see below).
Prerequisites: We assume that the participants have a solid background knowledge of discrete optimization (in particular, fundamental algorithms, computational complexity, convex programming, etc.); some basic knowledge of game theory is advantageous, but not a prerequisite for the course.
This course is part of the Dutch Network on the Mathematics of Operations Research (LNMB).
The course starts on February 24, 2020 and ends on May 4, 2020 May 11, 2020.
NOTE: There will be NO LECTURES on April 13 (Easter) and April 27 (King's Day). Additionally, we have a backup slot on May 11 which we might use if some lecture gets canceled.
UPDATE: Due to the corona virus (COVID-19), all lectures will be given via zoom as of March 23, 2020. The last lecture will be given on May 11.
The course will be given by Guido Schäfer. Please feel free to approach me if you have any questions related to the course.
Contact details:
Prof. Dr. Guido Schäfer
Email: g dott schaefer att cwi dott nl
Office at CWI: (office hours by appointment)
Centrum Wiskunde & Informatica
Networks and Optimization Group
Science Park 123, 1098 XG Amsterdam
Room: M235
Assignments will be issued (see the online material section) and have to be handed in as indicated below:
PLEASE WORK IN GROUPS OF AT MOST THREE TO SOLVE AND HAND IN THE ASSIGNMENTS.
The assignments have to be handed in at the beginning of the lecture (due date) or by email (due date, before 11:00). If you hand-in your solutions by email (preferred), please send them to me directly (using the email address above). Please ensure that scans of hand-written solutions have a sufficiently high resolution for printing.
The following books contain most of the material (and much more) covered in class and are good references if you want to learn more.
[NRTV07] N. Nisan, T. Roughgarden, E. Tardos, and V. V. Vazirani (Editors), Algorithmic Game Theory, Cambridge University Press, 2007. Note: The full-text of the book (pdf) seems to be available online.
[SLB16] Y. Shoham and K. Leyton-Brown, Multiagent Systems, Cambridge University Press, 2009. Note: The full-text of the book (pdf) is available here.
[Rou16] T. Roughgarden, Twenty Lectures on Algorithmic Game Theory, Cambridge University Press, 2016. Note: The full-text of the book (pdf) seems to be available online.
[KP16] A. R. Karlin and Y. Peres, Game Theory, Alive, American Mathematical Society, 2016. Note: The full-text of the book (pdf) is available here.
[Har14] J. Hartline, Mechanism Design and Approximation, Manuscript. Note: Chapters 1-8 are available here; see also this website.
If you want to learn more about convex programming (e.g., KKT conditions), the following book (available online) might be a good start:
[BV09] S. Boyd and L. Vandenberghe, Convex Optimization, Cambridge University Press, 2009. Note: The full-text of the book (pdf) is available here.
For more details on complexity classes (PLS, PPAD) and their relations, check out the complexity zoo.
In a nutshell: Lecture Notes on No-Regret Dynamics by Tim Roughgarden. More material for the interested reader: Chapter 4 (Learning, Regret Minimization, and Equilibria) in [NRTV07].
The online material of the course can be found here (password protected, drop me a line of you forgot the password).