  We study social choice mechanisms in an implicit utilitarian framework with a
metric constraint, where the goal is to minimize \textit{Distortion}, the worst
case social cost of an ordinal mechanism relative to underlying cardinal
utilities. We consider two additional desiderata: Constant sample complexity
and Squared Distortion. Constant sample complexity means that the mechanism
(potentially randomized) only uses a constant number of ordinal queries
regardless of the number of voters and alternatives. Squared Distortion is a
measure of variance of the Distortion of a randomized mechanism.
  Our primary contribution is the first social choice mechanism with constant
sample complexity \textit{and} constant Squared Distortion (which also implies
constant Distortion). We call the mechanism Random Referee, because it uses a
random agent to compare two alternatives that are the favorites of two other
random agents. We prove that the use of a comparison query is necessary: no
mechanism that only elicits the top-k preferred alternatives of voters (for
constant k) can have Squared Distortion that is sublinear in the number of
alternatives. We also prove that unlike any top-k only mechanism, the
Distortion of Random Referee meaningfully improves on benign metric spaces,
using the Euclidean plane as a canonical example. Finally, among top-1 only
mechanisms, we introduce Random Oligarchy. The mechanism asks just 3 queries
and is essentially optimal among the class of such mechanisms with respect to
Distortion.
  In summary, we demonstrate the surprising power of constant sample complexity
mechanisms generally, and just three random voters in particular, to provide
some of the best known results in the implicit utilitarian framework.
