  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 $k^{th}$ moment of Distortion is the
expected approximation factor with respect to the $k^{th}$ 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) $k^{th}$
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.
