Courses > PHD Courses
Top image

 
Home
News
Courses
Management Team
Conferences
Dutch OR Groups
People
Links
Contact
 

Landelijk Netwerk Mathematische Besliskunde

Course AMD: Algorithmic Mechanism Design

 
Time: Monday 15.15 – 17.00 (March 1 - March 29 and April 12 - May 10.).
Location: All LNMB courses will be taught on-line until further notice.
Lecturer: Prof.dr. G. Schäfer (CWI and VU University 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