The Distortion of Binomial Voting Defies Expectation
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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
An Elementary Analysis of the Probability That a Binomial Random Variable Exceeds Its Expectation
We give an elementary proof of the fact that a binomial random variable $X$ with parameters $n$ and $0.29/n \le p < 1$ with probability at least $1/4$ strictly exceeds its expectation. We also show that for $1/n \le p < …
Tight Lower Bound on the Probability of a Binomial Exceeding its Expectation
We give the proof of a tight lower bound on the probability that a binomial random variable exceeds its expected value. The inequality plays an important role in a variety of contexts, including the analysis of relative …
Generalization BoundsLearning TheoryBest of Both Distortion Worlds
We study the problem of designing voting rules that take as input the ordinal preferences of $n$ agents over a set of $m$ alternatives and output a single alternative, aiming to optimize the overall happiness of the agen…
On the Distortion of Voting with Multiple Representative Candidates
We study positional voting rules when candidates and voters are embedded in a common metric space, and cardinal preferences are naturally given by distances in the metric space. In a positional voting rule, each candidat…
Breaking the Metric Voting Distortion Barrier
We consider the following well-studied problem of metric distortion in social choice. Suppose we have an election with $n$ voters and $m$ candidates located in a shared metric space. We would like to design a voting rule…