LNMB PhD Course:
Algorithmic Mechanism Design 2021

Course Objectives

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:

• • 1. 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

    2. Simple vs. optimal vs. approximate mechanism design:

       • knapsack auctions

       • LP-based reduction techniques

       • prophet inequalities and posted price mechanisms

    3. Mechanism design with budget constraints

    4. Stable matchings and fair division

    5. Matching markets and envy-freeness

    6. Cost sharing mechanisms

Besides the material covered in class, we will also ask you to study some material on your own and to solve three take-home assignments (see below).

Prerequisites

We assume that the participants have a solid background knowledge of discrete optimization (in particular, fundamental algorithms, computational complexity, convex programming, etc.) and probability theory; some basic knowledge of game theory is advantageous, but not a prerequisite for the course.

This course is part of the Dutch Network on the Mathematics of Operations Research (LNMB).

Time and Location

The course starts on March 1, 2021 and ends on May 3, 2021 (9 + 1 sessions).

Date/Time: Mondays, 15:15-17:00
Location: The course will be given online through zoom

Zoom links:

(Lectures 1-5, from March 1)

https://cwi-nl.zoom.us/j/86997481107?pwd=bmRrKzVpKzEwbks1SVZqYVNEcEF3dz09

Meeting ID: 869 9748 1107
Passcode: 954152

(Lectures 6-10, from April 12)

https://utwente-nl.zoom.us/j/89804013971?pwd=RklRQTBOUmlWTGFabHFoWjI1dlNnQT09

Meeting ID: 898 0401 3971
Passcode: 806463

NOTE:

• There will be NO LECTURE on April 5 (Easter).

• We have a backup slot on May 10 which we might use if some lectures have to be cancelled.

Lecturers

The course will be given by Guido Schäfer and Marc Uetz.

Please feel free to approach us if you have any questions, comments or remarks related to the course.

Prof. Dr. Guido Schäfer
Networks and Optimization Group, Centrum Wiskunde & Informatica
Institute for Logic, Language and Computation, University of Amsterdam
Email: g.schaefer@cwi.nl

Prof. Dr. Marc Uetz
Mathematics of Operations Research, University of Twente
Email: m.uetz@utwente.nl

Assignments

Assignments will be issued and have to be handed in as indicated below (still tentative schedule):

• Assignment 1: issued March 8, due March 22

• Assignment 2: update: Assginment 2 comes in two parts:

  • Part A: issued March 29, due April 12 April 19!

  • Part B: issued April 12, due April 26

• Assignment 3: issued May 3, due May 17

The assignments will be posted in the online material section below.

WORKING IN GROUPS:

You are allowed (and in fact we would like to encourage you) to work on the solutions of the assignmemts with your student fellows. The maximum group size is limited to three students. Please let us know if you want to be matched up with other fellow students.

Please do not copy solutions from other groups!

HAND-IN:

The solutions of the assignments have to be handed in by email (due date, before 23:59).

Please send your solutions to us directly (respective lecturer, using the email address above). Please ensure that scans of hand-written solutions have a sufficiently high resolution.

Literature

The following books (tentative list) contain most of the material covered in class and are good references if you want to learn more.

[Rou16]
T. Roughgarden, Twenty Lectures on Algorithmic Game Theory, Cambridge University Press, 2016.
Note: The full-text of the book (pdf) seems to be available online.

[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 (pdf) seems to be available online.

[Har14]
J. Hartline, Mechanism Design and Approximation, Manuscript.
Note: Chapters 1-8 are available here; see also this website.

[Kri09]
V. Krishna, Auction Theory, Academic Press, 2009.

[SLB16]
Y. Shoham and K. Leyton-Brown, Multiagent Systems, Cambridge University Press, 2009.
Note: The full-text of the book (pdf) is available here.

[KP16]
A. R. Karlin and Y. Peres, Game Theory, Alive, American Mathematical Society, 2016.
Note: The full-text of the book (pdf) is available here.

[V11]
R.V. Vohra, Mechanism Design - A Linear Programming Approach, Cambridge University Press, 2011.

Online Material

The online material of the course can be found here (password protected, drop me a line if you forgot the password).