Abstract: We study the trade-offs between strategyproofness and other desiderata, such as efficiency or fairness, that often arise in the design of random ordinal mechanisms. We use epsilon-approximate strategyproofness to measure the manipulability of non-strategyproof mechanisms, and we introduce the deficit to quantify the performance of mechanisms with respect to a desideratum. When the desideratum is incompatible with strategyproofness, mechanisms that trade off manipulability and deficit optimally form the Pareto frontier. Our main contribution is a structural characterization of this Pareto frontier, and we present algorithms that exploit this structure to compute it. To illustrate its shape, we apply our results for two orthogonal desiderata, namely Plurality and Veto scoring, in a setting with 3 agents and 3 alternatives.
