Abstract

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(c,ε,δ)–M

ARGIN OF VICTORY problem, where given an election onvoters, the goal is to estimate the margin of victory M(ε)of ε within an additive factor of cM() +εn.We study the(c,ε,δ)–M ARGIN  OF V ICTORY prob-lem for many commonly used voting rules includ-ing scoring rules, approval, Bucklin, maximin, and CopelandWe  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 andCopeland α voting rules