The Pareto frontier for random mechanisms

Abstract

In many situations, a group of individuals (called agents) must collectively decide on one of several alternatives, e.g., elect the next president. Ordinal mechanisms are systematic procedures to make such decisions based on the agents’ preference orders over the alternatives. A mechanism is strategyproof if it makes truthful reporting of preferences a dominant strategy. Strategyproofness is therefore the “gold standard” among the incentive concepts. However, the seminal impossibility result of Gibbard [1977] showed that strategyproofness also greatly restricts the design space of ordinal mechanisms even if they can use randomization. In particular, it is incompatible with many other common desiderata, such as Condorcet consistency, stability, or egalitarian fairness. Thus, trade-offs between strategyproofness and other desiderata are necessary.
In this paper, we study these trade-offs. We use approximate strategyproofness to define manipulability, a measure to quantify the incentive properties of non-strategyproof mechanisms, and we introduce deficit, a measure to quantify the performance of mechanisms with respect to another desideratum. A mechanism that minimizes the deficit subject to a particular bound on manipulability is called optimal at this bound; and the mechanisms that are optimal at some bound form the Pareto frontier. Our main contribution is a structural characterization of this Pareto frontier: we show that there exists a finite set of supporting manipulability bounds, such that it suffices to identify optimal mechanisms at each of them. Other mechanisms along the Pareto frontier can then be constructed as hybrids (i.e., convex combinations) of these optimal mechanisms.
This allows a concise representation of the Pareto frontier in terms of a finite number of optimal mechanisms and their hybrids. In combination with linear programming, we can exploit this characterization to compute the whole Pareto frontier algorithmically. To illustrate its shape, we apply our results to determine the Pareto frontier for two different desiderata, namely Plurality and Veto scoring, in settings with 3 alternatives and up to 18 agents.