Course AMD: Algorithmic Mechanism Design

Time:	Monday 13.15 – 15.00 (February 24 – April 28 with the exception of April 21)
Location:	All LNMB courses take place on the Campus Utrecht Science Park. Room HFG 611, Hans-Freudenthal building, Budapestlaan 6, 3584 CD Utrecht
Lecturer:	Prof. Dr. G. Schäfer (CWI and University of Amsterdam), and Prof. Dr. M. Uetz (Unversity of Twente)

Important information

Participants of this course: please see the lecturers' website.

Course description

Algorithmic Mechanism Design (AMD) is a research area that lies at the interface of Game Theory and Algorithms and Optimization. On a high level, the goal in AMD is to develop algorithms that induce "socially desirable" outcomes in situations in which several strategic decision makers (or agents) are involved. Examples of the many applications of AMD include auctions, matching markets, voting systems, environmental regulations, fair allocation and division, cost and energy sharing, etc.

To achieve the above, we need to design algorithms that (i) compute such desirable outcomes efficiently, and (ii) determine an incentive scheme for the agents such that it is in each agents' self-interest to adhere to the computed solution. Naturally, the development of such algorithms is even more challenging than "traditional" algorithm design.

Detailed contents

The course covers both fundamental and recent results in AMD, with a particular focus on getting to know the state-of-the-art techniques to design such algorithms. A tentative list of topics that will be covered in this course are:

mechanism design basics:

single-item auctions (first-price, second-price)
combinatorial auctions (VCG mechanism)
single-parameter auctions (Myerson's Lemma)
revenue maximization and revenue equivalence

simple vs. optimal vs. approximate mechanism design

knapsack auctions
LP-based reduction techniques
prophet inequalities and posted price mechanisms
mechanism design with budget constraints
stable matchings and fair division
matching markets and envy-freeness
cost sharing mechanisms

Literature

The course is based on chapters from different textbooks and original articles (references will be provided throughout the course). Many topics covered in class can be found in the following books:

N. Nisan, T. Roughgarden, E. Tardos, and V. V. Vazirani (Editors), Algorithmic Game Theory, Cambridge University Press, 2007.
Y. Shoham and K. Leyton-Brown, Multiagent Systems, Cambridge University Press, 2009.
T. Roughgarden, Twenty Lectures on Algorithmic Game Theory, Cambridge University Press, 2016.
J. Hartline, Mechanism Design and Approximation, Manuscript.

Prerequisites

basic knowledge of probability theory, complexity theory, algorithms & optimization
some knowledge of game theory is advantageous but not required

Examination

Take home problems.

Address of the lecturers

Prof. Dr. G. Schäfer
CWI, P.O. Box 94079, 1090 GB Amsterdam
Phone: 020 - 592 4165
E-mail: g.schaefer@cwi.nl

Prof. Dr. M. Uetz
University of Twente, P.O. Box 217, 7500 AE Enschede
Phone: 053 - 489 3420
E-mail: m.uetz@utwente.nl