Metric distortion Under Probabilistic Voting

Metric distortion in social choice is a framework for evaluating how well voting rules minimize social cost when both voters and candidates exist in a shared metric space, with a voter’s cost defined by their distance to a candidate. Voters submit rankings, and the rule aggregates these rankings to determine a winner. We extend this framework to incorporate probabilistic voting, recognizing that real-world voters exhibit randomness in how they vote. Our extension includes various probability functions, notably the widely studied Plackett-Luce (PL) model. We show that the distortion results under probabilistic voting better correspond with conventional intuitions regarding popular voting rules such as $\text{textsc}Plurality$, $\text{textsc}Copeland$, $\text{textsc}RandomDictator$ and $\text{textsc}Borda$ than those under deterministic voting. For example, in the PL model with candidate strength inversely proportional to the square of their metric distance from a voter, we show that $\text{textsc}Copeland$'s distortion is at most 2, whereas that of $\text{textsc}RandomDictator$ is $\mathrm{\Omega }(\sqrt{m})$ in large elections (i.e., number of voters $n\to \mathrm{\infty }$), where $m$ is the number of candidates. This contrasts sharply with the classical model, where $\text{textsc}RandomDictator$ beats $\text{textsc}Copeland$ with a distortion of 3 versus 5. In the PL model where the candidate strength is inversely proportional to the distance raised to power $\theta$, the distortion under $\text{textsc}Borda$ is $\mathrm{\Theta }(m^{1-2\mathrm{/}\theta })$ when $\theta >2$ and $\mathrm{\Theta }(1)$ otherwise. This generalizes the classical deterministic voting model where the distortion of $\text{textsc}Borda$ is $2m-1$. The proof uses a novel variant of asymptotic duality where we choose the Lagrange multiplier via asymptotically maximizing the derivative of the objective function. Overall, our work opens a new frontier for analyzing voting rules.