Topics in Algorithmic Game Theory and Economics

Basic Information

Tutorials:  Homework: Lecturer: Pieter Kleer Lectures: Wednesday, 14:15-16:00 (Zoom) Tutor: Golnoosh Shahkarami First lecture: November 11, 2020 Monday, 12:15-14:00 (roughly bi-weekly; also on Zoom) There will be (mandatory) exercise sets that have to be handed in and will be graded by us.Solutions will be discussed during the tutorials.Half of homework points necessary to qualify for final (oral) exam. Oral Exam: February 23-24, 2021. (Re-exam: March 10, 2021) Credits: 5 Prerequisites: This course requires basic knowledge regardingLinear algebra (inlcuding how to solve linear systems)Probability theory (random variables, expectations)Graph theoryCalculusFuthermore, having some background in combinatorial optimization (e.g., the course Optimization) is usful, but not required. Finally, we assume mathematical maturity, i.e., you should be comfortable with writing mathematical proofs.

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 n-player 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.

DateTopicSlidesReferences
11.11Introduction and overviewLecture 1,   Hand-out   Chapter 13 [R2016]
16.11Tutorial 0 (Background material)
18.11Congestion games I: Computation of PNELecture 2,   Hand-out   Chapter 19 [R2016]
25.11Congestion games II: Inefficiency of PNELecture 3,   Hand-out
30.11Tutorial 1
02.12Finite games I: Existence and computation of MNELecture 4,   Hand-outChapter 20 [R2016]
09.12Finite games II: Computation of approximate MNELecture 5,   Hand-out
14.12Tutorial 2
16.12Computation of (C)CELecture 6,   Hand-outChapter 17 [R2016]
23.12(Christmas Break)
30.12(Christmas Break)
04.01Tutorial 2.5
06.01Online Selection ProblemsLecture 7,   Hand-out
13.01Some Mechanism DesignLecture 8,   Hand-outChapters 2-3 [R2016]
20.01Online Bipartite MatchingLecture 9,   Hand-out
25-01Tutorial 3
27.01Matroid Secretary ProblemsLecture 10,  Hand-out
03.02Prophet InequalitiesLecture 11,  Hand-out
08.02Tutorial 4
19.02 (14:15)Q&A session for oral exam
23-24.02Oral exams

Material

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 no-regret dynamics discussed during the lecture, and a proof that the MW algorithm satisfies the no-regret property.
• See Chapter 18 [R2016] for similar (but different) "no-regret 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 unit-demand 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]

Digital editions of these books are accessible from within the IP-range 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.