# Estimating the Margin of Victory of an Election using Sampling

arXiv: https://arxiv.org/abs/1505.00566 · HTML: https://mlsanity.com/paper/1505.00566/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 May 2015.

## Built on by (most cited first, 2 of 2)

- [Sampling-Based Winner Prediction in District-Based Elections](https://mlsanity.com/paper/2203.00083/) (2022)
- [How Hard is it to Rig a Benchmark? A Social Choice Analysis of Leaderboard Robustness](https://mlsanity.com/paper/2605.23628/) (2026)

## Abstract (arXiv)

The margin of victory of an election is a useful measure to capture the robustness of an election outcome. It also plays a crucial role in determining the sample size of various algorithms in post election audit, polling etc. In this work, we present efficient sampling based algorithms for estimating the margin of victory of elections. More formally, we introduce the textsc(c, ε, δ)--Margin of Victory problem, where given an election E on n voters, the goal is to estimate the margin of victory M(E) of E within an additive factor of c MoV(E)+ε n. We study the textsc(c, ε, δ)--Margin of Victory problem for many commonly used voting rules including scoring rules, approval, Bucklin, maximin, and Copelandα. We observe that even for the voting rules for which computing the margin of victory is NP-Hard, there may exist efficient sampling based algorithms, as observed in the cases of maximin and Copelandα voting rules.