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
define "manipulability," a measure to quantify the incentive properties
of non-strategyproof mechanisms, and we introduce the "deficit," a
measure to quantify the performance of mechanisms with respect to
another desideratum. When this 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 different desiderata, namely
Plurality and Veto scoring, in settings with 3 alternatives and up to 18
agents.
