How Many Votes is a Lie Worth? Measuring Strategyproofness through Resource Augmentation

arXiv:2602.22838 · cs.GT · Submitted 2026-02-26 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.

Tom: We're looking at the paper: "How Many Votes is a Lie Worth? Measuring Strategyproofness through Resource Augmentation".

Jane: Here's the gist of the paper. The paper introduces a framework called manipulation potential, which serves as a prior-free metric to measure the comparative advantage of a strategic voter over their augmented truthful self.

Tom: This potential quantifies how many copies of a voter's (truthful) vote must be added to the election to achieve an outcome as good as their best possible manipulation.

Jane: The core finding is that this framework provides a principled method for comparing different voting rules based on their manipulation potential.

Tom: A rule with a low manipulation potential leaves little worst-case advantage to lying over finding like-minded voters or increasing voter weight through other means.

Title and authors: Tom: We're talking about "How Many Votes is a Lie Worth? Measuring Strategyproofness through Resource Augmentation." The authors are Ratip Emin Berker, Vincent Conitzer, Eden Hartman, Jiayuan Liu, and Caspar Oesterheld from Carnegie Mellon University and the University of Oxford >

Jane: It’s about moving beyond the general idea that any voting rule can be manipulated by untruthful voters and instead measuring the actual strength of that manipulation through this resource augmentation idea.

Lu: The paper suggests we measure how many copies of a voter's truthful vote must be added to the election in order to get an outcome as good as their best possible manipulation could yield >

Meng: I mean, if we can quantify that advantage, it gives us a principled way to see which rules are actually robust against strategic voting when voters can only boost their truthful support >

Lalam: It sets up this metric so we can compare different social choice functions by looking at their inherent resistance to strategic voting under resource augmentation >

The paper's summary: Tom: The paper summarizes that this manipulation potential gives us a principled way to compare voting rules based on how much worst-case advantage a voter has when lying versus finding like-minded voters or increasing their vote weight >

Jane: They go into specific examples to show this, like comparing the Borda Count against other rules and showing that Borda Count has a very special property regarding the number of voters >

Lu: They find that under certain conditions, specifically when there are many voters compared to candidates, like when n is much larger than m, Borda Count has a manipulation potential that is independent of the number of voters itself >

Meng: That’s interesting because independence from the size of the electorate suggests a rule with lower incentive for manipulation if you can only increase your truthful support >

Lalam: They also looked at other rules and found that some, like Condorcet extensions such as Black's Rule, have higher manipulation potentials compared to Borda Count under certain conditions >

The paper's improvements: Tom: The paper suggests improvements by framing this potential as a way to measure the trade-off between rules that exhibit low manipulation potential and those that strictly follow majorities >

Jane: It highlights a tension between rules that are very resistant to manipulation and those that strictly enforce majoritarian outcomes, which is something we should pay attention to when selecting a system >

Lu: They also show how this framework helps us reject certain classes of rules; for example, they show that any such rule that is additionally majoritarian will perform significantly worse than Borda Count under large electorates >

Meng: So it’s not just about finding the best rule, but figuring out which classes of rules we should even consider if we want to minimize the incentive for strategic voting >

Lalam: It provides a way to reject rules based on consistency; for instance, they show that rules like Copeland have an infinite group manipulation potential because they are not k-ASP for any k greater than or equal to zero >

Conclusion: Tom: So, to wrap up, the main point of "How Many Votes is a Lie Worth? Measuring Strategyproofness through Resource Augmentation" is that this potential allows us to compare voting rules based on their inherent resistance to strategic voting when voters can only increase their truthful support >

Jane: They show Borda Count has a manipulation potential of m minus two assuming the number of voters n is even, which means it's independent of the number of people voting when n is large >

Lu: The finding that this metric allows us to select Borda Count when the voter count outweighs the candidate count, or Plurality otherwise, points toward a clear decision rule based on scale >

Meng: For deployment, knowing that Borda Count has this bounded potential means it offers weak incentives for manipulation if you can only increase your truthful support >

Lalam: And to conclude, this framework is a powerful tool to compare social choice functions by showing that rules like Borda Count offer low worst-case advantage for lying compared to other options >

Carnegie Mellon University · Foundations of Cooperative AI Lab (FOCAL) · University of Oxford · Bar-Ilan University

cs.GT

Submitted: 2026-02-26

Updated: 2026-11-10

Comments: 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)

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Importance score: 100/100

The gist: The paper introduces a framework called manipulation potential, which serves as a prior-free metric to measure the comparative advantage of a strategic voter over their augmented truthful self.

Key concepts

Manipulation Potential (MP)
This is a metric quantifying the comparative advantage of a strategic voter over their truthful self. It measures how many copies of a voter's truthful vote must be added to the election to reach an outcome as good as their best possible manipulation.
Borda Count (BC)
Borda Count is highlighted because its manipulation potential is independent of the number of voters ($n$). Specifically, Theorem 4.13 shows MP(BC) = m - 2 (for even $n$), suggesting it performs well when electorates are large.
Resource Augmentation
This refers to the ability of a voter to increase their truthful support by adding more copies of their vote to the election. The framework uses this concept to test strategic voting resistance, comparing how much gain a voter can achieve through lying versus finding like-minded voters.

Terminology

Summary

The paper introduces a framework called manipulation potential, which serves as a prior-free metric to measure the comparative advantage of a strategic voter over their augmented truthful self. p. 2 This potential quantifies how many copies of a voter's (truthful) vote must be added to the election to achieve an outcome as good as their best possible manipulation.

The core finding is that this framework provides a principled method for comparing different voting rules based on their manipulation potential. p. 0 A rule with a low manipulation potential leaves little worst-case advantage to lying over finding like-minded voters or increasing voter weight through other means. p. 4

Key results regarding specific rules include:

  • Borda Count (BC): Borda Count stands out because its manipulation potential is independent of the number of voters (n). Specifically, Theorem 4. p. 613 establishes that MP(BC) = m - 2 (assuming n is even). p. 0 This suggests that under large electorates, Borda Count outperforms many other rules, including positional scoring rules and majority-consistent rules. p. 4

  • Positional Scoring Rules: The positional scoring rule with the lowest manipulation potential is either Borda Count or Plurality, depending on the relationship between m-2 and n-1.

  • Other Rules: Condorcet extensions, such as Black's Rule, have higher manipulation potentials (MP(BL) = n-1) compared to Borda Count under certain conditions.

The framework also demonstrates a fundamental tradeoff: there is a tension between rules that exhibit low manipulation potential and those that strictly follow majorities. p. 4

In contrast, the analysis of other rules reveals different behaviors regarding resource augmentation. p. 2 For instance, for Copeland, Theorem B. p. 21 shows that its group manipulation potential (GMP(CL)) is infinite (infinity), meaning Copeland is not k-ASP for any k at least 0. Similarly, Proposition C. p. 21 proves that the manipulation potentials of Pareto and Omninomination rules are both infinity, indicating neither rule is k-ASP for any k at least 0. p. 3 This implies these rules have unbounded manipulation potentials. p. 3

In summary, the paper establishes manipulation potential as a powerful tool to compare social choice functions based on their inherent resistance to strategic voting under resource augmentation. p. 0 Borda Count is highlighted for its independence from the number of voters, suggesting it offers weak incentives for manipulation when voters can only increase their truthful support. p. 4

Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.

Improvements for AI systems

  1. Resource augmentation metric for strategic voting: The system can measure 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. This quantifies what a voter can gain by manipulating in comparison to what they would have gained by finding like-minded voters.

  2. Rule comparison based on manipulation potential: The system can compare different voting rules by calculating their manipulation potential, which is defined as the number of truthful copies needed (in the worst case) to ensure a voter could not have reached a better outcome by misreporting. This allows for a principled separation between rules in terms of manipulability.

  3. Rule selection based on scale: The system can determine that Borda Count has one that is independent of this number [of voters], allowing it to select Borda Count when the number of voters n is much larger than the number of candidates m, as its manipulation potential is bounded by m minus 2.

  4. Rule selection based on rule class: The system can identify that the positional scoring rule with the smallest manipulation potential will always be either Borda Count (if the number of voters outweighs the number of candidates) or Plurality (otherwise), guiding selection towards these two rules in those regimes.

  5. Rule rejection based on consistency: The system can reject rules belonging to classes like Condorcet extensions if they are majoritarian, as it proves any such rule that is additionally majoritarian will perform significantly worse than Borda Count under large electorates.

Sources

Related papers