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 textscPlurality, textscCopeland, textscRandom Dictator and textscBorda 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 textscCopeland's distortion is at most 2, whereas that of textscRandomDictator is Omega(√m) in large elections (i.e., number of voters n rightarrow ∞), where m is the number of candidates. This contrasts sharply with the classical model, where textscRandomDictator beats textscCopeland 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 textscBorda is Theta(m1-2/θ) when θ>2 and Theta(1) otherwise. This generalizes the classical deterministic voting model where the distortion of textscBorda 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.