Title: Trade-offs between Strategyproofness and Efficiency of Ordinal Mechanisms
Abstract: There are some things that money cannot buy. For moral and ethical reasons society has set boundaries regarding the use of money for certain resources and transactions. Such restrictions often arise in situations that are of great importance to people's lives: subsidized housing must be assigned to tenants, seats at public schools must be assigned to students, or a new president must be elected. The design of mechanisms for these problems is plagued by severe impossibility results pertaining to strategyproofness. In this thesis we address the research question of how to trade off strategyproofness and other desiderata in the design of ordinal mechanisms. For the assignment domain we introduce the new relaxed incentive concept of partial strategyproofness. We employ this concept to show that a choice between three popular school choice mechanisms, the Deferred Acceptance mechanism and two variants of the Boston mechanism, involves an implicit trade-off between strategyproofness and efficiency. Next, we give sufficient and almost necessary conditions under which hybrid mechanisms facilitate meaningful trade-offs between strategyproofness and efficiency of assignment mechanisms. Finally, in the general ordinal domain we introduce a new framework to assess mechanisms by their manipulability and their deficit. The deficit is a measure for their ability to achieve another desideratum, such as efficiency, stability, or fairness. Within this framework the Pareto frontier consists of those mechanisms that trade-off manipulability and deficit optimally. Our results is a structural characterization of this Pareto frontier.
