The Distortion of Binomial Voting Defies Expectation

Yannai A. Gonczarowski · Gregory Kehne · Ariel Procaccia · Ben Schiffer · Shirley Zhang

Great Hall & Hall B1+B2 (level 1) #1800
[ ]
Wed 13 Dec 3 p.m. PST — 5 p.m. PST


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.

Chat is not available.