- The course starts on
**Monday, February 24, 2020**, 11:00-12:45, Hans Freudenthalgebouw (Budapestlaan), Room 611AB, Utrecht University.

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:

- network routing games, Wardrop flow, price of anarchy
- Braess paradox, Stackelberg routing, network tolls
- existence and computation of mixed Nash equilbria
- congestion games, potential functions, price of stability
- equilibrium hierarchy, smoothness technique, extension theorems
- combinatorial auctions and VCG mechanism
- mechanism desgin, monotone approximation algorithms
- matching markets and generalized second-price auction

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 11, 2020**.

**Date/Time:**Monday, 11:00-12:45**Location:**Hans Freudenthalgebouw (Budapestlaan), Room 611AB, Utrecht University

**NOTE:** There will be **NO LECTURES** on **April 13** (Easter) and **April 27** (King’s Day).

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:

- Assignment 1: issued March 9, due March 23
- Assignment 2: issued March 30, due April 14
- Assignment 3: issued April 20, due May 4

**PLEASE(!) WORK IN PAIRS 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.

**[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 (at a later stage).