Course AMD: Algorithmic Mechanism Design

Time:

Monday 15.15 – 17.00 (March 6 - April 3 and April 17 - May 15)

Location:

All LNMB courses can be attended on the Campus Utrecht Science Park. The lecture rooms vary from week to week:

March 6: Buys Ballot building - lecture room 083
March 13: Hans Freudenthal building - lecture room 611AB
March 20: Marinus Ruppert building - lecture room B
March 27: Victor J. Koningsberger building - lecture room 224
April 3: Buys Ballot building - lecture room 083
April 17: Buys Ballot building - lecture room 017
April 24; May 1, 8, 15: Buys Ballot building - lecture room 165

Note that there's no lecture on April 10 (Easter)

Lecturer:

Prof.dr. G. Schäfer (CWI and University of Amsterdam), and Prof.dr. M. Uetz (Unversity of Twente)

Course description:
(for participants of this course: see the lecturer's website)

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.

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.

Website for the course: go to website

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