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