Mechanism Design Without Money

Seminar

Basic Information

Given by:	Kurt Mehlhorn, Javier Cembrano, Golnoosh Shahkarami
Time:	Tuesdays at 2:15pm
Room:	024 (MPI-INF)
First Meeting:	April 8, 2025
Credits:	7 credit points
Prerequisites:	This is a theoretical seminar that will require mathematical maturity (in particular, the ability to understand and write formal mathematical proofs) and a good background in algorithms. A proper preparation of your talk will require non-trivial effort. The target audience of this seminar is master students, PhD students, as well as postdocs.
Deadlines:	TBA

Description

Mechanism design is an area of algorithmic game theory that focuses on coordinating players' interests to achieve collective decisions. While a common approach involves financial incentives, monetary transactions are unethical or impractical in many real-world scenarios; canonical examples include assigning students to schools, matching organ donors to recipients, placing public facilities, and electing representatives. The field of mechanism design without money explores ways to align individual incentives with socially desirable outcomes in such settings.

Some initial lectures will be taken by the instructors to explain the basics that will help students to select their paper/topic. The seminar is open for all interested students and postdocs. Students aiming to get credit points must give a regular talk and write a short summary about the paper. The presentation needs to be discussed with us at least one week before your scheduled talk.

Reference Texts

Gale, D., & Shapley, L. S. (1962). College admissions and the stability of marriage. The American mathematical monthly, 69(1), 9-15. [DOI]

Gibbard, A. (1973). Manipulation of voting schemes: a general result. Econometrica, 587-601. [DOI]

Satterthwaite, M. A. (1975). Strategy-proofness and Arrow's conditions: Existence and correspondence theorems for voting procedures and social welfare functions. Journal of economic theory, 10(2), 187-217. [DOI]

Abdulkadiroğlu, A., & Sönmez, T. (2003). School choice: A mechanism design approach. American economic review, 93(3), 729-747. [DOI]

Dughmi, S., & Ghosh, A. (2010). Truthful assignment without money. In Proceedings of the 11th ACM conference on Electronic commerce, 325-334. [DOI]

Procaccia, A. D., & Tennenholtz, M. (2013). Approximate mechanism design without money. ACM Transactions on Economics and Computation (TEAC), 1(4), 1-26. [DOI]

Koutsoupias, E. (2014). Scheduling without payments. Theory of Computing Systems, 54(3), 375-387. [DOI]

Ashlagi, I., Fischer, F., Kash, I. A., & Procaccia, A. D. (2015). Mix and match: A strategyproof mechanism for multi-hospital kidney exchange. Games and Economic Behavior, 91, 284-296. [DOI]

Fischer, F., & Klimm, M. (2015). Optimal Impartial Selection. SIAM Journal on Computing, 44(5), 1263-1285. [DOI]

Freeman, R., Pennock, D. M., Peters, D., & Vaughan, J. W. (2021). Truthful aggregation of budget proposals. Journal of Economic Theory, 193, 105234. [DOI]

Cembrano, J., Klimm, M., & Knaack, M. (2024). Packing a Knapsack with Items Owned by Strategic Agents. In Proceedings of the 20th Conference on Web and Internet Economics. [DOI]

Agrawal, P., Balkanski, E., Gkatzelis, V., Ou, T., & Tan, X. (2024). Learning-Augmented Mechanism Design: Leveraging Predictions for Facility Location. Mathematics of Operations Research. [DOI]

Balkanski, E., Gkatzelis, V., & Shahkarami, G., (2024). Randomized Strategic Facility Location with Predictions. In Proceedings of the 38th Conference on Advances in Neural Information Processing Systems. [DOI]

How to apply?

Application for seminars is possible through the central SIC seminar system (https://seminars.cs.uni-saarland.de/sose25seminars).

If you are interested in attending specifically this seminar, we kindly recommend you to

send a request by e-mail to Javier Cembrano or Golnoosh Shahkarami. Please indicate your full name and enrollment number.
apply for this seminar in the central SIC seminar system.