pipette
ENEnglish

Regularizing the Veto Core

M. August Rossi

Preprint

En palabras de los autores

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 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 , and prove that its distortion lies in ; we conjecture that the lower bound is tight. A fixed can increase distortion, but letting 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{\i}z{\i}lkaya and Kempe.

Resultado principalLimitación que admiten los autores

Apareció: martes, 20 de octubre. arXiv. Preprint, todavía sin revisión por pares.