Concentration of distortion: The value of extra voters in randomized social choice

Journal Article

We study higher statistical moments of Distortion for randomized social choice in a metric implicit utilitarian model. The Distortion of a social choice mechanism is the expected approximation factor with respect to the optimal utilitarian social cost (OPT). The kth moment of Distortion is the expected approximation factor with respect to the kth power of OPT. We consider mechanisms that elicit alternatives by randomly sampling voters for their favorite alternative. We design two families of mechanisms that provide constant (with respect to the number of voters and alternatives) kth moment of Distortion using just k samples if all voters can then participate in a vote among the proposed alternatives, or 2k-1 samples if only the sampled voters can participate. We also show that these numbers of samples are tight. Such mechanisms deviate from a constant approximation to OPT with probability that drops exponentially in the number of samples, independent of the total number of voters and alternatives. We conclude with simulations on real-world Participatory Budgeting data to qualitatively complement our theoretical insights.

Duke Authors

Cited Authors

  • Fain, B; Fan, W; Munagala, K

Published Date

  • January 1, 2020

Published In

Volume / Issue

  • 2021-January /

Start / End Page

  • 110 - 116

International Standard Serial Number (ISSN)

  • 1045-0823

Citation Source

  • Scopus