School Choice; Market Design; Efficiency; Strategyproofness; Matching; Mechanism Design; Trade-offs; Efficient Frontier; Assignment Mechanisms
BreroGianluca, LahaieSebastien, SeukenSven (2019), Fast Iterative Combinatorial Auctions via Bayesian Learning, in Thirty-third AAAI Conference of Artificial Intelligence (AAAI-19)
, Honolulu, HawaiiAAAI, Menlo Park, CA, USA.
Brero Gianluca, Lubin Benjamin, Seuken Sven (2018), Combinatorial Auctions via Machine Learning-based Preference Elicitation, in Twenty-seventh International Joint Conference on Artificial Intelligence and the Twenty-third Europe
, Stockholm, SwedenInternational Joint Conferences on Artificial Intelligence , Online.
Dur Umut, Mennle Timo, Seuken Sven (2018), First-Choice Maximal and First-Choice Stable School Choice Mechanisms, in the 2018 ACM Conference
, Ithaca, NY, USAACM, New York, NY, USA.
Mennle Timo, Seuken Sven (2016), The Pareto Frontier for Random Mechanisms, in Proceedings of the 17th ACM Conference on Economics and Computation (EC)
, Maastricht, The NetherlandsACM, New York, NY, USA.
Mennle Timo, Weiss Michael, Philipp Basil, Seuken Sven (2015), The Power of Local Manipulation Strategies in Assignment Mechanisms, in Proceedings of the 24th International Joint Conference on Artificial Intelligence (IJCAI)
, Buenos Aires, ArgentinaAAAI Press, Palo Alto, CA, USA.
There are some things that money cannot buy, like access to the best public schools, a donated kidney, or internship positions at NGOs. For moral and ethical reasons, society has decided to set boundaries regarding the use of money for resources that affect our health, our education, or our work situation. In domains like these, where resources (or matching partners) are scarce and monetary transfers are restricted, we face a matching problem, where people and/or objects must be assigned to each other. The design and analysis of matching mechanisms is part of the relatively new research field called market design. As market designers, we care specifically about the efficiency, strategyproofness, and fairness of the markets we design. Unfortunately, prior research has shown that it is impossible to achieve the optimum on all three dimensions simultaneously, which makes this an interesting market design challenge. Obviously, trade-offs are necessary. Yet, prior work on matching mechanisms has not led to a good understanding of the necessary and possible trade-offs.Instead, the mechanisms studied in previous research only represent discrete points in the space of all possible mechanisms. For example, in one-sided matching, Random Serial Dictatorship is strategyproof, but only ex-post efficient. Probabilistic Serial is ordinally efficient, but only weakly strategyproof. Finally, Rank Value mechanisms are rank efficient, but not even weakly strategyproof. In two-sided matching markets, Deferred Acceptance mechanisms are stable, as well as strategyproof and weakly Pareto efficient for the proposing side. In contrast, the Boston mechanism is strongly Pareto efficient, but manipulable and unstable. While these individual mechanisms are now relatively well understood, the design of mechanisms with intermediate properties is a largely unexplored area; we know relatively little regarding how to trade off small portions of one property for another. The overall goal of this research project is to significantly improve our understanding regarding the possible and necessary trade-offs between efficiency, strategyproofness and other desiderata for matching mechanisms, to ultimately design new mechanisms that make optimal trade-offs. To reach this goal, the research is divided into three separate parts: In Part #1, we study partial strategyproofness, a relaxation of strategyproofness essential for the analysis of trade-offs in matching markets. We first refine and strengthen the partial strategyproofness concept. We then adapt the concept to two-sided matching markets. Finally, we apply the concept to existing non-strategyproof mechanisms and uncover its connection to strategyproofness in the large. In Part #2, we develop new, flexible dominance and efficiency concepts that are needed for the analysis and construction of mechanisms with intermediate properties. This is an important task, because the comparison of mechanisms by conventional dominance concepts is generally ambiguous. To address this problem, we use constrained efficiency and introduce more distinguishing and flexible concepts.In Part #3, we employ our new strategyproofness and efficiency concepts to analyze the necessary and possible trade-offs in matching markets. We first study mechanisms on the efficient frontier, i.e., we seek mechanisms that provide optimal efficiency given certain constraints and, if possible, provide characterizations of these mechanisms. Finally, we propose limit mechanisms as an interesting way to design new mechanisms that make desirable trade-offs. Our research will significantly advance our understanding of the design space for matching mechanisms, in particular regarding what trade-offs are possible and necessary. It will also lead to new insights about the achievable "balance" of various desiderata relevant in real-world matching applications. Finally, our results have great potential to influence future market design research and to provide directions for experimental work regarding human behavior in matching markets.