Metric distortion Under Probabilistic Voting
For social choice theorists, it provides a more realistic analysis of voting rules under probabilistic voter behavior, revealing that classical deterministic distortion rankings can be misleading.
This paper extends the metric distortion framework to probabilistic voting models like Plackett-Luce, showing that distortion results better match intuitions (e.g., Copeland beats Random Dictator with distortion 2 vs Ω(√m) in large elections, reversing the classical order).
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 \textsc{Plurality}, \textsc{Copeland}, \textsc{Random Dictator} and \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 \textsc{Copeland}'s distortion is at most 2, whereas that of \textsc{RandomDictator} is $Ω(\sqrt{m})$ in large elections (i.e., number of voters $n \rightarrow \infty$), where $m$ is the number of candidates. This contrasts sharply with the classical model, where \textsc{RandomDictator} beats \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 $θ$, the distortion under \textsc{Borda} is $Θ(m^{1-2/θ})$ when $θ>2$ and $Θ(1)$ otherwise. This generalizes the classical deterministic voting model where the distortion of \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.