Announcements:

Course Description:

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:

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

Aims and Prerequisites:

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.

Time and Location:

The course consists of 9 lectures.

Date/Time: Monday, 13:00-14:45
Location: Mathematical Building, room 611AB, Utrecht University

The first lecture is on February 10, 2014. The last lecture is on April 7, 2014.

Lecturer:

Prof. Dr. Guido Schäfer
Email: g dot schaefer 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

Assessment:

Assignments will be issued on a bi-weekly basis.

PLEASE(!) WORK IN GROUPS OF AT MOST 2 STUDENTS 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 13: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.

References and Links:

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-5 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.

If you want to refresh your knowledge on complexity theory, you might want to check Chapter 9 of the Lecture Notes on Discrete Optimization that I gave as part of the Mastermath program.

For more details on complexity classes (PLS, PPAD) and their relations, check out the complexity zoo.

Course Material:

The online material of the course can be found here (password protected).

Lecture 1 (Feb. 10)

Lecture 2 (Feb. 17)

Lecture 3 (Feb. 24)

Lecture 4 (March 3)

Lecture 5 (March 10)

Lecture 6 (March 17)

Lecture 7 (March 24)

Lecture 8 (March 31)

Lecture 9 (April 7)