  In the single winner determination problem, we have n voters and m candidates
and each voter j incurs a cost c(i, j) if candidate i is chosen. Our objective
is to choose a candidate that minimizes the expected total cost incurred by the
voters; however as we only have access to the agents' preference rankings over
the outcomes, a loss of efficiency is inevitable. This loss of efficiency is
quantified by distortion. We give an instance of the metric single winner
determination problem for which any randomized social choice function has
distortion at least 2.063164. This disproves the long-standing conjecture that
there exists a randomized social choice function that has a worst-case
distortion of at most 2.
