2023/06/27 by Yannai A. Gonczarowski, Gonczarowski, Yannai A., Gregory Kehne +7
Decision Sciences · Economics, Econometrics and Finance · Social Sciences · #Artificial Intelligence (cs.AI) #Auction Theory and Applications #Computer Science and Game Theory (cs.GT) #Experimental Behavioral Economics Studies #FOS: Computer and information sciences #Game Theory and Voting Systems
paper · pdf · doi:10.48550/arxiv.2306.15657
openalex publication_date 2023/06/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01
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.