The Distortion of Binomial Voting Defies Expectation
This work addresses a limitation in computational social choice by shifting from worst-case to expected analysis, offering a more practical framework for designing voting rules.
The paper tackles the problem of evaluating voting rules beyond worst-case analysis by introducing expected distortion with respect to voter utility distributions, and it proposes binomial voting, which achieves strong distribution-independent guarantees for both expected distortion and welfare.
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.