arXiv:2602.22838 · v3
How Many Votes is a Lie Worth? Measuring Strategyproofness through Resource Augmentation
摘要
It is well known, by the Gibbard-Satterthwaite Theorem, that when there are more than two candidates, any non-dictatorial voting rule can be manipulated by untruthful voters. But how much stronger is an untruthful voter than a truthful one under different voting rules? We suggest measuring the potential comparative advantage of a strategic voter by asking how many copies of their (truthful) vote must be added to the election in order to achieve an outcome as good as their best manipulation. Intuitively, this definition quantifies what a voter can gain by manipulating in comparison to what they would have gained by finding like-minded voters to join the election (equivalently, by increasing their voter weight). Our measure is prior-free and requires no assumptions on the voters' cardinal utilities. Using this framework, we obtain a principled method to compare the manipulation leverage for different voting rules. We show that while the manipulation leverage of many rules grows linearly with the number of voters, Borda Count's is m-2, where m is the number of candidates. We prove that the positional scoring rule with the smallest manipulation leverage is always Borda Count (if voters outnumber candidates) or Plurality (otherwise). Further, any rule satisfying a weak form of majority consistency (and thus any Condorcet extension) cannot outperform Plurality, while any majoritarian rule will perform significantly worse. Consequently, Borda Count has much lower manipulation leverage than these wide classes of rules under large electorates. Finally, we establish a quantitative extension of the Gibbard--Satterthwaite theorem, proving no anonymous and onto voting rule can have manipulation leverage that is lower than m-2 across all electorate sizes. As a result, Borda Count is indeed optimal among all such rules.
作者备注：61 pages, 3 figures. new additions for this version: stronger results on majoritarian rules (Section 4), a game-theoretic framework (Section 5), and a universal lower bound (Section 6)