- 17/05: Assignment 3 has been posted and is due on May 30, 2016.
- 17/05: Updated slides on mechanism design (part 2) have been posted.
- 09/05: Assignment 3 will be posted by the end of this week.
- 05/05: Slides of the mechanism design part given by Bart have been posted.
- 30/04: As agreed during last lecture, the due date for Assignment 2 is postponed to May 9.
- 19/04: Preparation for next class (25/04): Please study Sec. 5.2 (Lemke-Howson algorithm) of the Lecture Notes by yourself.
- 19/04: Assignment 2 has been posted and is due on May 2, 2016. Lecture Notes have been updated.
- 10/04: Due to sickness, the lecture on Monday, April 11, has to be canceled unfortunately.
- 25/03: Assignment 1 has been posted and is due on April 11, 2016.
- 25/03: Lecture notes and slides on potential games are available.
- 18/03: Please try to solve Problem 1 (see selfish routing slides, page 37)
- 07/03: Lecture notes and slides on selfish routing are available (see course material).
- 18/02: The course starts on
**Monday, March 7, 2016**, 11:00-12:45, Mathematical Building (Budapestlaan), room 611AB, Utrecht University.

Algorithmic game theory is a rather new and rapidly growing research area that lies at the intersection of mathematics, theoretical computer science and economics. 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 areas like discrete optimization, algorithms, computational complexity, game theory, mechanism design, etc.

Topics that we will cover in the course are:

- selfish routing and congestion games
- complexity of computing equilibria
- inefficiency of equilibria
- smoothness of games and learning
- combinatorial auctions
- approximation and mechanism design
- ad auctions and the generalized second-price auction

Besides the material that we cover in class, we will also ask you to study some material on your own and to solve take-home assignments.

This course is part of the Dutch Network on the Mathematics of Operations Research (LNMB).

The aim of the course is to both learn about fundamental results of the field and to get acquainted with recent state-of-the-art techniques.

We assume that the participants have some background knowledge in discrete optimization (algorithms, complexity, linear programming, etc.); knowledge of game theory is advantageous but not a prerequisite for the course.

The course consists of **9 lectures**.

Date/Time: |
Monday, 11:00-12:45 |

Location: |
Mathematical Building, room 611AB, Utrecht University |

The first lecture is on March 7, 2016. The last lecture is on May 9, 2016.

Prof. Dr. Guido Schäfer

Email: g dot schaefer at cwi dot nl

Dr. Bart de Keijzer

Email: keijzer at cwi dot nl

Office hours by appointment

**Office at CWI:**

Centrum Wiskunde & Informatica

Networks and Optimization Group

Science Park 123, 1098 XG Amsterdam

Room: M235

Assignments will be issued as indicated below (see online material).

- Assignment 1 (issued March 25), due April 11.
- Assignment 2 (issued April 11), due May 9.
- Assignment 3 (issued May 17), due May 30.

**PLEASE(!) WORK IN PAIRS TO SOLVE AND HAND IN THE
ASSIGNMENTS.**

The assignments have to be handed in at the beginning of the next lecture or by email (on due date, before 11:00). If you want to hand-in your solutions by email, then please send them directly to me (g dot schaefer at cwi dot nl). Please ensure that scans of hand-written solutions have a sufficiently high resolution for printing.

We will use selected chapters from the books listed below.

[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 is available online here (username=agt1user,
password=camb2agt). There is also an Errata. |

[Har14] |
J. Hartline, Mechanism Design and Approximation,
Manuscript.Chapters 1-8 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 is available online 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.