Voting method improved for fairness and best choice selection
Regularizing the Veto Core
Computer Science and Game Theory
Summary
Choosing a winner in a vote based only on rankings can be tricky, especially when some methods tie between options everyone doesn’t equally support. The authors looked at a known voting approach called SimultaneousPluralityVeto, which picks winners close to voters’ preferences but sometimes fails to choose the clearly better candidate. They introduced a small adjustment to the method that ensures the chosen winner is always Pareto-efficient—that is, no other candidate is better for all voters—and keeps the method’s efficiency and fairness features. This work helps design voting rules that pick winners more reliably and fairly.
What this means in practice
- •For political system designers: Develop voting systems that guarantee fair winner selection without ties when unanimous preference exists among voters.
- •For online platform managers: Implement ranking-based voting methods for community decisions that reliably pick options preferred by most users.
Authors
M. August Rossi
Abstract
The metric distortion framework asks voting rules to elect a candidate close to the voters using only their rankings. SimultaneousPluralityVeto elects from the plurality veto core and achieves the optimal worst-case distortion of 3, but it is not Pareto-efficient: it can declare a tie between two candidates even when every voter prefers one of them. Removing Pareto-dominated candidates afterward would break the convexity of tied winner sets. We instead introduce regularization, which adds a small $\varepsilon$ to every candidate's weight, restoring Pareto-efficiency. To study its effect on distortion, we introduce the rank score veto core, whose candidate weights come from a positional scoring vector $\mathbf{s}$, and prove that its distortion lies in $[1 + 2(||\mathbf{s}|| - s_m),\, 1 + 2||\mathbf{s}||]$; we conjecture that the lower bound is tight. A fixed $\varepsilon$ can increase distortion, but letting $\varepsilon$ depend on the number of voters preserves the distortion guarantee of the original veto core. Regularized SimultaneousPluralityVeto thus has optimal distortion, is Pareto-efficient, and has convex tied winner sets, resolving an open question of Kızılkaya and Kempe.