May 23: Yet another update: I am (still) busy with correcting the last homework assignment (no. 3). Next week I will be done. Sorry for the delay.
May 12: Just a quick update: I am not yet finished with the corrections of 2b, but get there hopefully soon. I'm on it.
May 8: Realizing that Exercise 4 of exercise set no. 3 has been covered in the lecture earlier by Guido, you may skip that one!
May 7: About Exercise 2 of exercise set no. 3, where you are asked to prove revenue equivalence for any implementable allocation rule x: Note that Lecture 7 showed a characterization of revenue equivalence in terms of anti-symmetry of shortest path distances in type graphs G_x. For this exercise you may assume and use that the same characterization also holds for allocation graphs H_x (see sheet 24). Also note that we assume here that the number of allocations X is finite.
April 27: Lecture slides for Lecture no. 9 (simple mechanisms) are up, as well as final set of homework assignments. Due date is May 12. See you on Monday April 29.
April 17: Assignment 2A has been graded and feedback has been sent to the respective groups. The (partial) solutions of Assignment 2A are availabe in the online material folder.
April 11: Lecture slides for Lecture no. 8 (revenue maximization) are up. See you on Monday April 14.
April 6: Exercises 2b are uploaded. It looks a lot but it actually isn't. Should be well doable with the given hints. Please email me if anything is unclear. Note the due date (April 14 April 28).
April 5: Lectures slides for Lecture no. 7 (on what is known as revenue equivalence) are now uploaded. Exercises 2b will follow soon.
March 31: Assignment 1 has been graded and feedback has been sent to the respective groups. Some general remarks/comments based on the grading of Assignment 1 have been posted in the online material folder. Also the partial solutions of Assignment 1 have been extended slightly.
March 30: Lecture slides for Lecture no. 6 (on what is called cyclical monotonicity) have been uploaded to the online material. Looking forward to seeing you tomorrow, March 31 in Utrecht. Assignments 2b will follow during next week.
March 26: Partial solutions of Assignment 1 are available in the online material section. Also, given that we had to rush through the lecture on cost sharing mechanism a bit, the video lecture from the AMD 2023 course is available (in case you are interested).
March 24: Assignment 2a has been posted. Submission deadline has been extended to April 7.
March 3: Please let us know by email if you are searching for fellow students to collaborate on the assignments. We will try to match you up then.
March 2: Assignment 1 has been posted and is due March 17.
Feb 24: Slides of the first lecture are available in the online material section (password as announced during lecture).
Feb 13: Course page is up. Welcome! Please note that this course starts one week later than the other LNMB PhD courses: The first lecture of AMD will be on Monday, Febraury 24, 2025, 13:15-15:00. We're looking forward to seeing you then!
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
generalized second-price auction
LP-based reduction techniques
posted price mechanisms
Specialized topics:
Mechanisms without money
Mechanisms with budget constraints
Mechanisms with predictions
Matching markets and envy-freeness
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).
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).
See also here for the course announcement on the LNMB page.
The course starts on Febraury 24, 2025 and ends on April 28, 2025 (9 lectures).
NB: There is no lecture on April 21!
Date/Time:
Location:
Room:
Mondays, 13:15-15:00
Campus Utrecht Science Park
Room HFG 611, Hans-Freudenthal building, Budapestlaan 6, 3584 CD Utrecht.
A campus map is available here.
The course will be given by Guido Schäfer and Marc Uetz.
Networks and Optimization Group, Centrum Wiskunde & Informatica
Institute for Logic, Language and Computation, University of Amsterdam
Email: g.schaefer@cwi.nl
Mathematics of Operations Research, University of Twente
Email: m.uetz@utwente.nl
The first five lectures will be given by Guido. The last four lectures will be given by Marc. Marc takes over March 31.
Please feel free to approach us if you have any questions, comments or remarks related to the course.
Assignments will be issued and have to be handed in as indicated below (still tentative schedule):
Assignment 1: issued March 3, due March 17
Assignment 2: Assignment 2 comes in two parts:
Part A: issued March 24, due March 31 April 7
Part B: issued April 7, due April 14 April 28
Assignment 3: issued April 28, due May 12
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.
Please let us know if you want to be matched up with other fellow students.
Please do not copy solutions from other groups!
The solutions of the assignments have to be uploaded to this surfdrive folder (due date, before 23:59).
The following references 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.
[MU16]
R. Müller and M. Uetz, Shortest Path to Mechanism Design, In: Gems of Combinatorial Optimization and Graph Algorithms, Springer 2016 (link)