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 22, 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: | April 29: Preference list of papers |
| July 22: Summary |
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.
Contact us (jcembran@mpi-inf.mpg.de, gshahkar@mpi-inf.mpg.de) in case there are any questions!
Schedule
| Date | Speaker | Title |
|---|---|---|
| April 22 | Golnoosh Shahkarami | Introduction to Mechanism Design |
| April 29 | Javier Cembrano | Gibbard-Satterthwaite Theorem |
| May 6 | Golnoosh Shahkarami | Strategic Facility Location |
| May 13 | Javier Cembrano | Stable Matching |
| May 20 | No Lecture | - |
| May 27 | Student 1 | Effective Affirmative Action in School Choice |
| June 3 | Student 2 | Mix and Match: A Strategyproof Mechanism for Multi-hospital Kidney Exchange |
| June 10 | Student 3 | Learning-Augmented Mechanism Design: Leveraging Predictions for Facility Location |
| June 17 | Student 4 | Resolving the Optimal Metric Distortion Conjecture |
| June 24 | Student 5 | Optimal Impartial Selection |
| July 1 | Student 6 | EFX: A Simpler Approach and an (Almost) Optimal Guarantee via Rainbow Cycle Number |
| July 8 | Student 7 | Truthful Aggregation of Budget Proposals |
| July 15 | Student 8 | Truthful Assignment without Money |
List of Papers
Hafalir, I. E., Yenmez, M. B., Yildirim, M. A. (2013). Effective affirmative action in school choice. Theoretical Economics, 8(2), 325-363. [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]
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]
Gkatzelis, V., Halpern, D., Shah, N. (2020). Resolving the optimal metric distortion conjecture. In 61st Annual Symposium on Foundations of Computer Science (FOCS) (pp. 1427-1438). IEEE. [DOI]
Fischer, F., Klimm, M. (2015). Optimal Impartial Selection. SIAM Journal on Computing, 44(5), 1263-1285. [DOI]
Akrami, H., Alon, N., Chaudhury, B. R., Garg, J., Mehlhorn, K., Mehta, R. (2024). EFX: A Simpler Approach and an (Almost) Optimal Guarantee via Rainbow Cycle Number. Operations Research 73(2):738-751. [DOI]
Freeman, R., Pennock, D. M., Peters, D., Vaughan, J. W. (2021). Truthful aggregation of budget proposals. Journal of Economic Theory, 193, 105234. [DOI]
Dughmi, S., Ghosh, A. (2010). Truthful assignment without money. In Proceedings of the 11th ACM conference on Electronic commerce (pp. 325-334). [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.