Topics in Algorithmic Game Theory and Economics
Advanced Course, 2+1
Basic Information
Lecturer:  Pieter Kleer 

Lectures:  Wednesday, 14:1516:00 (Zoom) 
Tutor:  Golnoosh Shahkarami 
First lecture:  November 11, 2020 
Tutorials:  Monday, 12:1514:00 (roughly biweekly; also on Zoom) 
Homework:  There will be (mandatory) exercise sets that have to be handed in and will be graded by us.

Oral Exam:  February 2324, 2021. (Reexam: March 10, 2021) 
Credits:  5 
Prerequisites:  Basic knowledge about:
Familiarity with linear programming and combinatorial optimization is useful (e.g., from the course Optimization), 
Zoom link  Click here (this link is for both the lectures and tutorials). 
Announcements
Please subscribe to the mailing list in order to receive course information: https://lists.mpiinf.mpg.de/listinfo/agt2020.
 (19.02) Oral exams take place on February 2324, 2021. All relevant info has been sent those to taking the oral exam.
 (19.02) As announced earlier on the mailing list, the reexam takes place on March 10, 2021.
Description
In this course we will cover topics in the areas of Algorithmic Game Theory and Computational Economics, which can be placed at the intersection of economics and theoretical computer science. The course consists of two parts.
Game theory is concerned with the study of mathematical models of strategic interaction between players. One of its core aspects is the study of equilibrium situations: `Stable' states of the model in which no player has an incentive to switch strategies. Roughly twenty years ago, computer scientists became interested in studying the algorithmic aspects of such equilibria. Can we compute them efficiently, that is, in polynomial time? In the first part of this course we will cover results addressing this question, and more, in general nplayer games and the special class of potential (or congestion) games. We will mostly focus on computational questions concerning pure Nash equilibria (PNE), mixed Nash equilibria (MNE) and (coarse) correlated equilibria (CCE).
In the second part of this course we study problems in the area of Computational Economics, with a focus on online selection problems. One example here is the selling of an item on an online platform in which buyers arrive in an unknown order, and where we have to irrevocably decide upon a buyer's arrival if we want to sell to her or not. This problem is closely related to, e.g., the classical secretary problem. We will cover various results and online models in this area, such as combinatorial secretary problems and prophet inequalities, and also discuss connections to online mechanism design.
Schedule
Tentative outline (subject to changes). Files are sometimes updated.
Date  Topic  Slides  References 

11.11  Introduction and overview  Lecture 1, Handout  Chapter 13 [R2016] 
16.11  Tutorial 0 (Background material)  
18.11  Congestion games I: Computation of PNE  Lecture 2, Handout  Chapter 19 [R2016] 
25.11  Congestion games II: Inefficiency of PNE  Lecture 3, Handout  
30.11  Tutorial 1  
02.12  Finite games I: Existence and computation of MNE  Lecture 4, Handout  Chapter 20 [R2016] 
09.12  Finite games II: Computation of approximate MNE  Lecture 5, Handout  
14.12  Tutorial 2  
16.12  Computation of (C)CE  Lecture 6, Handout  Chapter 17 [R2016] 
23.12  (Christmas Break)  
30.12  (Christmas Break)  
04.01  Tutorial 2.5  
06.01  Online Selection Problems  Lecture 7, Handout  
13.01  Some Mechanism Design  Lecture 8, Handout  Chapters 23 [R2016] 
20.01  Online Bipartite Matching  Lecture 9, Handout  
2501  Tutorial 3  
27.01  Matroid Secretary Problems  Lecture 10, Handout  
03.02  Prophet Inequalities  Lecture 11, Handout  
08.02  Tutorial 4  
19.02 (14:15)  Q&A session for oral exam  
2324.02  Oral exams  
Homework
 Homework Set 1 (deadline: November 26, 23:59 CET)
 Homework Set 2 (deadline: December 10, 23:59 CET)
 Homework Set 2.5 (will not be graded)
 Homework Set 3 (deadline: January 21, 23:59 CET)
 Homework Set 4 (deadline: February 4, 23:59 CET)
Material
Further reading
Lecture 1 (11.11):
 See Chapter 13 of [R2016] for an overview of the hierarchy of equilibrium concepts that we discussed during the lecture.
Lecture 2/3 (18.11/25.11):
 See Chapter 19 of [R2016] for the complexity of computing a PNE when interpreted as a local search problem.
 See this paper of Roughgarden for an overview of the smoothness technique and more of its applications.
Lecture 4 (02.12):
 See Chapter 20 [R2016] for the PPAD complexity of computing an MNE.
 Starting point for reading about the convergence time of fictitious play is this paper by Daskalakis and Pan (and references therein).
Lecture 5 (09.12):
 Paper by Lipton, Markakis and Mehta regarding approximate Nash equilibria with logarithmic support size (discussed during lecture).
Lecture 6 (16.12):
 See Chapter 17 [R2016] for the noregret dynamics discussed during the lecture, and a proof that the MW algorithm satisfies the noregret property.
 See Chapter 18 [R2016] for similar (but different) "noregret dynamics" converging to a correlated equilibrium.
Lecture 7 (06.01):
 For the full proof of the performance guarantee of the secretary algorithm, see, e.g., this note.
Lecture 8 (13.01):
 See Chapters 2 and 3 [R2016] for a more formal treatment of Mechanism Design, and, in particular, a proof of Myerson's lemma.
 See also Part II of [NRTV2008] for a more extensive treaty.
Lecture 9 (20.01):
 Paper by Kesselheim, Radke, Tönnis and Vöcking on online bipartite matching algorithm.
 Paper by Reiffenhäuser with online strategyproof mechanism for unitdemand setting.
Lecture 10 (27.01):
 Paper of Babaioff, Immorlica, Kempe and Kleinberg on the matroid secretary problem.
Lecture 11 (03.02):
 Paper of Kleinberg and Weinberg on matroid prophet inequalities.
References (books)
 Algorithmic Game Theory by Noam Nisan, Tim Roughgarden, Éva Tardos and Vijay V. Vazirani [NRTV2008]
 Twenty Lectures on Algorithmic Game Theory by Tim Roughgarden [R2016]
 This book is based on Prof. Roughgarden's lecture notes.
Digital editions of these books are accessible from within the IPrange of Saarland University. Hardcopies available in the university library.
Background (prerequisite) material
Throughout the course, we will use some elementary tools from combinatorics, (linear) optimization and probability theory that will not be fully explained in the lectures. A small document containing more details on this material can be found below.
About Zoom and Lecture Material
We have decided to use Zoom (https://zoom.us/) as a videoconferencing service. Note that this provider (Zoom Video Communications, Inc., 55 Almaden Blvd, Suite 600, San Jose, CA 95113, USA) can access all data that you provide when registering for the video conference. If you do not provide personal data during the registration, there is still a possibility that Zoom identifies you using your IP address. We would not have decided to use Zoom if we considered this as a significant risk. Should you still have privacy concerns (and are not using an Internet Service Provider that cannot map IP addresses to your name), we suggest using an anonymization service such as Tor (https://www.torproject.org/). You can find Zoom's complete privacy policy at: https://zoom.us/dede/privacy.html
We aim to create a pleasant lecture environment despite the current situation. Personal interactions on Zoom, with your microphone and camera switched on, may contribute to this environment. We also encourage you to ask questions verbally. Note that this is voluntary. You may switch off both your camera and your microphone, and register under a pseudonym. Questions are still possible, in particular using the chat function.
The lectures on Zoom will be recorded, the tutorials not. Access to the recordings will be provided to participants registered to the mailing list. It is strictly forbidden to share access information, as well as any offline copies of the recorded lectures, with others. In general, all material (and access to material) provided via the mailing list is for personal use only, and may not be distributed.