LNMB PhD Course:
Algorithmic Game Theory 2024
Announcements
May 6: Assignment 3 and the "fair division of indivisible goods" slides have been posted. Unfortunately, there was not enough time to do the proofs of the theorems on Slides 28 and 34; I will create a video for those later this week.
April 29: The "improving POA with predictions" slides have been posted. In Lecture 9 (obligatory attendance) we will continue with a new topic.
April 28: Assignment 3 will be issued May 6 instead of April 29.
April 22: The "prophet inequality" slides (with some corrections), as well as the hand-written notes of the "equilibrium hierarchy" slides, have been uploaded. In Lecture 8, we will continue with a new topic.
April 16: In the upcoming Lecture 7, we will finish the "equilibrium hierarchy" slides (see SURFdrive). After that, we start with a new topic.
April 9: Feedback on Assignment 1 has been provided by email. Some general remarks can be found in the course folder also.
April 8: Pieter takes over the course next week Monday.
April 8: Assignment 2 has been posted and is due on April 22.
March 25: Preparation for next class (08-04): Please read Section 2.7 of the Lecture Notes!
March 25: There is no lecture next Monday. Happy Easter!
March 25: Posted Lecture Notes and slides are complete (GS part).
March 20: Preparation for next class (25-03): Please read Sections 2.1, 2.2, 2.3 & 2.5 of the Lecture Notes!
We will only briefly discuss this material in class and continue with the complexity of Nash equilibria in potential games on Monday.March 20: Lecture Notes have been updated (see online material).
March 10: Assignment 1 has been posted and is due on March 25.
Feb. 14: The course starts on Monday, March 4, 2024, 11:00-12:45. The course will be given onsite (Campus Utrecht Science Park, room HFG 611) and through zoom.
Course Objectives
Algorithmic Game Theory (AGT) is an interdisciplinary research area that lies in the intersection of Theoretical Computer Science, Discrete Mathematics and Economic Theory. The area builds upon game-theoretic foundations to study situations of strategic decision making, with a particular focus on computational and algorithmic aspects. It combines methodologies and techniques from several disciplines such as complexity theory, algorithm design, discrete and continuous optimization, online decision making and learning, auction and mechanism design, etc.
The overall goal of the course is to build up a mathematical toolbox of state-of-the-art models, methodologies and techniques to study the impact of strategic decision making and to develop efficient algorithms for such environments.
The main topics that will be covered in this course are:
selfish routing games and the price of anarchy
Braess paradox, Stackelberg routing, network tolls
best-response dynamics and potential games
complexity of equilibrium computation
quantifying the inefficiency of equilibria
equilibrium hierarchy and no-regret learning
smoothness and extension theorems
improving price of anarchy with predictions
prophet inequalities
fair division of indivisible goods
Besides the material covered in class, we will 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, linear/convex programming, etc.) and probability theory; 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).
Time and Location
The course starts on March 4 (Lecture #1) and ends on May 6, 2024 (Lecture #9).
Date/Time:
Mondays, 11:00-12:45
Location:
Room HFG 611, Hans-Freudenthal Building
(Budapestlaan 6, 3584 CD Utrecht, see Google Maps)
Zoom link:
LNMB PhD Course: AGT 2024
(Meeting ID: 843 8079 9418)
All lectures will be given onsite in Utrecht.
Additionally, we will stream the lectures through zoom so that participants who cannot attend in person can follow the lectures remotely. The default policy is that the lectures will not be recorded.
Attendance:
Note that students who want to obtain 1 EC for the course (no assignments) have to be present during the lectures in Utrecht.
Please note that the attendance in Utrecht is obligatory for all students following the course for Lecture #1 (March 4), Lecture #5 (April 8) and Lecture #9 (May 6).
Note:
There will be no lecture on April 1 (Easter).
We have a backup slot on May 13 which we might use if some lectures have to be cancelled.
Lecturer
The course will be given by Guido Schäfer and Pieter Kleer. Contact details are given below.
Please feel free to approach us if you have any questions, comments or remarks related to the course.
Prof. Dr. Guido Schäfer
Networks and Optimization Group, Centrum Wiskunde & Informatica
Institute for Logic, Language and Computation, University of Amsterdam
Email: g.schaefer@cwi.nl
Dr. ir. Pieter Kleer
Department of Econometrics and Operations Research
Tilburg School of Economics and Management, Tilburg University
Email: p.s.kleer@tilburguniversity.edu
Assignments
Assignments will be issued and have to be handed in as indicated below:
NOTE: tentative schedule
Assignment 1: issued March 11, due March 25
Assignment 2: issued April 8, due April 22
Assignment 3: issued April 29, issued May 6, due May 27
The assignments will be posted in the online material section below.
WORKING IN GROUPS:
Please work in groups on the assignments. The maximum group size is limited to three students.
Please let us know if you want to be matched up with other fellow students.
NB: It is not allowed to copy solutions from other groups! If you obtain your solution with help of others than your teammates, or with help of the Internet, it is obligatory to give credits to the relevant sources. You should always explain your solution in your own words, and be able to explain it to the lecturers upon request.
HAND-IN:
The solutions of the assignments have to be handed in by email (due date, before 23:59 CEST).
Please submit your solutions via the following surfdrive upload folder.
Please ensure that scans of hand-written solutions have a sufficiently high resolution: unreadable solutions = no points.
Literature
The following books contain most of the material 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.
[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.
[SLB16]
Y. Shoham and K. Leyton-Brown, Multiagent Systems, Cambridge University Press, 2009.
Note: The full-text of the book (pdf) is available here.
[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.
Online Material
The online material of the course can be found here (password will be provided in the lecture).