LNMB PhD Course:
Algorithmic Game Theory 2022

Announcements

  • May 30: Given that many of you expressed the wish to have another tutorial, Sophie will offer a final final tutorial session on Thursday, June 9, 10:00-11:30. Please use the tutorial zoom link given below.

  • May 17: There will be a final tutorial session offered by Sophie next week Monday, May 23, 11:00. Please use the tutorial zoom link below.

  • May 16: Slides, video of today's lecture and updated Lecture Notes (final) have been posted.

  • May 16: Deadline for hand-in of Assignment 3 is extended to May 30.

  • May 9: Assignment 3 has been posted (due May 23).

  • May 8: Note that there will be no online live lecture on Monday, May 9. Instead, please follow the posted video lectures and study the respective chapters in the Lecture Notes (as indicated in the readme file).

  • April 24: Video lectures (two parts) to be studied independently have been posted. Please refer to the readme file in the online material folder for guidelines on how to proceed.

  • April 23: Note that there will be no online live lecture on Monday, April 25. Instead, video lectures will be provided shortly that can be studied independently.

  • April 23: Deadline for hand-in of Assignment 2 is extended to May 9.

  • April 15: Video of yesterday's tutorial is available online.

  • April 11: Sophie will organize a tutorial session on Thursday, April 14, 13:00; details can be found below.

  • April 11: Assignment 2 has been posted (due May 2). Also: slides and video of today's lecture have been posted. NOTE: No class next week Monday (Easter Monday) – have a good Easter break!

  • April 4: Slides, video of today's lecture and updated Lecture Notes have been posted. Preparation for next week (11-04): please read Chapter 2 (Sec. 2.1-2.3 & 2.5).

  • April 1: Slides and video of lecture on Monday have been uploaded.

  • March 21: Assignment 1 has been posted. Also: slides and video of today's lecture have been uploaded; the Lecture Notes were slightly updated.

  • March 14: If you want to prepare for next week: feel free to have a look at Chapter 1 (Sec. 1.1-1.6) and Chapter 2 (KKT conditions) of the Lecture Notes.

  • March 14: Slides and video of today's lecture have been uploaded. Also the Lecture Notes (first part) are available. (See online material.)

  • March 10: The zoom link for the lectures can be found below.

  • Feb. 28: The course starts on Monday, March 14, 2022, 11:00-12:45. The course will be given online through zoom (details will follow soon).

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

  • selfish load balancing and scheduling

  • complexity of equilibrium computation

  • quantifying the inefficiency of equilibria

  • equilibrium hierarchy and no-regret learning

  • smoothness and extension theorems

  • markets and fair division

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 14, 2022 (lecture #1) and ends on May 16, 2022 (lecture #9).

Date/Time:
Mondays, 11:00-12:45

Location:
The course will be given online through zoom

Zoom link:
https://cwi-nl.zoom.us/j/89760113504?pwd=ZTFmSEN1ZUs0anFmRlFPSW1Qa3VIQT09
(Meeting ID: 897 6011 3504, Passcode: 940434)

NOTE:

  • There will be NO LECTURE on April 18 (Easter).

  • We have a backup slot on May 23 which we might use if some lectures have to be cancelled.


TUTORIAL SESSIONS:

Sophie organizes a tutorial session on Thursday, April 14, 13:00, to discuss Assignment 1 and other questions that come up.

UPDATE: Another tutorial session to discuss Assignment 2 will take place on Monday, May 23, 11:00.

The respective zoom link is:

Zoom link:

https://cwi-nl.zoom.us/j/84040650335?pwd=a2xTWG5iRjhsZjAvRG0zZ3QzRW5HQT09

(Meeting ID: 840 4065 0335, Passcode: 768602)

In case you cannot make: The tutorial will be recorded and put online afterwards for your convenience.

Lecturer

The course will be given by Guido Schäfer.


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

Please feel free to approach me if you have any questions, comments or remarks related to the course.


Sophie Klumper will be the teaching assistant of the course.

Assignments

Assignments will be issued and have to be handed in as indicated below:

NOTE: tentative schedule

  • Assignment 1: issued March 21, due April 4

  • Assignment 2: issued April 11, due May 2 extended to May 9

  • Assignment 3: issued May 9, due May 23 extended to May 30

The assignments will be posted in the online material section below.


WORKING IN GROUPS:

You are allowed (and in fact we would like to encourage you) to work on the solutions of the assignmemts with your student fellows. The maximum group size is limited to three students. Please let us know if you want to be matched up with other fellow students.

Please do not copy solutions from other groups!


HAND-IN:

The solutions of the assignments have to be handed in by email (due date, before 23:59).

Please send your solutions directly to Sophie (Sophie.klumper@cwi.nl). Please ensure that scans of hand-written solutions have a sufficiently high resolution.

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