Header

UZH-Logo

Maintenance Infos

The Pareto frontier for random mechanisms


Mennle, Timo; Seuken, Sven (2016). The Pareto frontier for random mechanisms. In: The 2016 ACM Conference on Economics and Computation, Maastricht, The Netherlands, 24 August 2016 - 28 August 2016, 769.

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.

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.

Statistics

Altmetrics

Downloads

6 downloads since deposited on 06 Jan 2017
6 downloads since 12 months
Detailed statistics

Additional indexing

Item Type:Conference or Workshop Item (Paper), refereed, original work
Communities & Collections:03 Faculty of Economics > Department of Informatics
Dewey Decimal Classification:000 Computer science, knowledge & systems
Language:English
Event End Date:28 August 2016
Deposited On:06 Jan 2017 15:37
Last Modified:30 Aug 2017 03:08
Publisher:ACM Press
ISBN:9781450339360
Publisher DOI:https://doi.org/10.1145/2940716.2940786
Other Identification Number:merlin-id:14389

Download

Preview Icon on Download
Preview
Content: Accepted Version
Filetype: PDF
Size: 674kB
View at publisher
Preview Icon on Download
Preview
Content: Published Version
Filetype: PDF
Size: 802kB