  In computational social choice, the distortion of a voting rule quantifies
the degree to which the rule overcomes limited preference information to select
a socially desirable outcome. This concept has been investigated extensively,
but only through a worst-case lens. Instead, we study the expected distortion
of voting rules with respect to an underlying distribution over voter
utilities. Our main contribution is the design and analysis of a novel and
intuitive rule, binomial voting, which provides strong distribution-independent
guarantees for both expected distortion and expected welfare.
