Estimating the Margin of Victory of an Election Using Sampling

1 Introduction

In many real life applications, there is often a need for a set of agents to agree upon a common decision although they may have different preferences over the available candidates to choose from. A natural approach used in these situations is voting. Some prominent examples of the use of voting rules in the context of multiagent systems include collaborative filtering [Pennock et al., 2000], personalized product selection [Lu and Boutilier, 2011] etc.

In a typical voting scenario, we have a set of votes each of which is a complete ranking over a set of candidates. We also have a function called voting rule that takes as input a set of votes and outputs a candidate as the winner. A set of votes over a set of candidates along with a voting rule is called an election and the winner is called the outcome of the election.

Given an election, one may like to know how robust the election outcome is with respect to the changes in votes [Shiryaev et al., 2013; Caragiannis et al., 2014; Regenwetter et al., 2006]. One way to capture robustness of an election outcome is to compute the minimum number of votes that must be changed to change the outcome. This idea of robustness is captured precisely by the notion called margin of victory. The margin of victory of an election is the smallest number of votes that need to be changed to change the election outcome. In a sense, an election outcome is considered to be robust if the margin of victory is large.

1.1 Motivation

In addition to being interesting purely because of theoretical reasons, the margin of victory of an election plays a crucial role in many practical applications. One such example is post election audits - methods to observe a certain number of votes (which is often selected randomly) after an election to detect an incorrect outcome. There can be a variety of reasons for an incorrect election outcome, for example, software or hardware bugs in voting machine [Norden and Law, 2007], machine output errors, use of various clip-on devices that can tamper with the memory of the voting machine [Wolchok et al., 2010], human errors in counting votes. Post election audits have nowadays become common practice to detect problems in electronic voting machines in many countries, for example, the US. As a matter of fact, at least thirty states in the US have reported such problems by 2007 [Norden and Law, 2007]. Most often, the auditing process involves manually observing some sampled votes. Researchers have subsequently proposed various risk limiting auditing methodologies that not only minimize the cost of manual checking, but also limit the risk of making a human error by sampling as few votes as possible [Stark, 2008a; 2008b; 2009; Sarwate et al., 2011]. The sample size in a risk limiting audit critically depends on the margin of victory of the election.

Another very important application where the margin of victory plays an important role is polling. In polling, the pollster samples a certain number of votes from the population and predicts the outcome of the underlying election based on the outcome of the election on the sampled votes. One of the most fundamental questions in polling is: how many votes should be sampled? It turns out that the sample complexity in polling too crucially depends on the margin of victory of the election from which the pollster is sampling [Canetti et al., 1995; Dey and Bhattacharyya, 2015]. The number of samples used in an algorithm is called the sample complexity of that algorithm. As the above discussion shows, computing the margin of victory of an election is often a necessary task in many practical applications. However, one cannot observe all the votes in many applications including the ones discussed above. For example, in a survey or polling, one cannot first observe all the votes to compute the margin of victory and then sample a few votes based on the computed margin of victory. Hence, one often needs a "good enough" estimate of the margin of victory by observing a few votes. We, in this work, precisely address this problem: estimate the margin of victory of an election by sampling as few votes as possible.

1.2 Our Contributions

Let n be the number of votes, m the number of candidates, r any voting rule. We introduce and study the following computational problem in this paper 1 :

Definition 1. ((c, ε, δ)-MARGIN OF VICTORY (MOV)) Given a r-election E, determine Mr(E), the margin of victory of E with respect to r, within an additive error of at most cMr(E) + εn with probability at least 1 - δ. The probability is taken over the internal coin tosses of the algorithm.

We call the parameter (c, ε) in Definition 1 the approximation factor of the problem. Our goal here is to solve the (c, ε, δ)-MOV problem with as few sample votes as possible. Our main technical contribution is to come up with efficient sampling based polynomial time randomized algorithms to solve the (c, ε, δ)-MOV problem for various voting rules. Each sample reveals the entire preference order of the sampled vote. The specific contributions of this paper are summarized in Table 1.

Table 1 shows a practically appealing positive result- the sample complexity of all the algorithms presented here is independent of the number of voters. We also present lower bounds on the sample complexity of the (c, ε, δ)-MOV problem for all the common voting rules which matches with the upper bounds when we have a constant number of candidates. Moreover, the lower and upper bounds on the sample complexity match exactly for the k-approval voting rule irrespective of number of candidates, when k is a constant.

One key finding of our work is that, there may exist efficient sampling based polynomial time algorithms for estimating the margin of victory, even if computing the margin of victory is NP-Hard for a voting rule [Xia, 2012], as observed in the cases of maximin and Copelandα voting rules.

1.3 RelatedWork and Discussion

Magrino et al. [Magrino et al., 2011] presents approximation algorithms to compute the margin of victory for the instant runoff voting (IRV) rule. Cary [Cary, 2011] provides algorithms to estimate the margin of victory of an IRV election. Xia [Xia, 2012] presents polynomial time algorithms for computing the margin of victory of an election for various voting rules, for example the scoring rules, and proved intractability results for several other voting rules, for example the maximin and Copelandα voting rules. Endriss et al. [Endriss and Leite, 2014] computes the complexity of exact variants of the margin of victory problem for Schulze, Cup, and Copeland voting rules. However, all the existing algorithms to either compute or estimate the margin of victory need to observe all the votes, which defeats the purpose in many applications including the ones discussed in Section 1.1. We, in this work, show that we can estimate the margin of victory for many common voting rules quite accurately by sampling a few votes only. Moreover, the accuracy of our estimation algorithm is good enough for many practical scenarios. For example, Table 1 shows that it is enough to select only 3600 many votes uniformly at random to estimate MoV n of a plurality election within an error of 0.1 with probability at least 0.99, where n is the number of votes. We note that in all the sampling based applications discussed in Section 1.1, the sample size is inversely proportional to MoV n [Canetti et al., 1995] and thus it is enough to estimate MoV n accurately.

1 Throughout this section, we use standard terminlogy from voting theory. For formal definitions, refer to Section 2.

The margin of victory problem is the same as the optimization version of the destructive bribery problem introduced by Faliszewski et al. [Faliszewski et al., 2006; 2009]. However, to the best of our knowledge, there is no prior work on estimating the cost of bribery by sampling votes.

2 Preliminaries

Let V = {≻1, . . . ,≻n} be the set of all votes and C = {c1, . . . , cm} the set of all candidates. If not mentioned otherwise, m and n denote the number of candidates and the number of voters respectively. Each vote ≻i is a complete order over the candidates in C. For example, for the candidate set C = {a, b}, a ≻i b means that the vote ≻i prefers a to b. We denote the set of all complete orders over C by L(C). Hence, L(C)n denotes the set of all n-voters' preference profiles ≻= (≻1, . . . , ≻n). A map r : ∪n,|C|∈N+L(C)n -→ 2C is called a voting rule. Given a vote profile ≻∈ L(C)n , we call the candidates in the set r(≻) the winners. The pair (≻, C) is called an r-election E if the voting rule used is r.

Examples of some common voting rules are as follows.

Positional scoring rules: A collection of vectors {⃗si}i∈N, where ⃗sm = (α1, α2, . . . , αm) ∈ Rm is a m-dimensional vector with α1 ≥ α2 ≥ · · · ≥ αm and α1 > αm for every m ∈ N, naturally defines a voting rule - a candidate gets score αi from a vote if it is placed at the ith position, and the score of a candidate is the sum of the scores it receives from all the votes. The winners are the candidates with maximum score. Scoring rules remain unchanged if we multiply every αi by any constant λ > 0 and/or add any constant µ. Hence, we can assume without loss of generality that in every score vector ⃗α, there exists a j with αj - αj+1 = 1 and αi = 0 for all i > j. We call such a vector ⃗α a normalized score vector.

The vector ⃗α that is 1 in the first k coordinates and 0 elsewhere gives the k-approval voting rule. 1-approval is called the plurality voting rule. The score vector (m - 1,m - 2, . . . , 1, 0) gives the Borda voting rule.

Approval: In approval voting, each vote approves a subset of candidates. The winners are the candidates which are approved by the maximum number of votes.

Bucklin: A candidate x's Bucklin score is the minimum number ℓ such that at least half of the votes rank x in their top ℓ positions. The winners are the candidates with lowest Bucklin score.

Maximin: Given an election E and any two candidates x and y, the quantity DE(x, y) is defined as NE(x, y) - NE (y, x), where NE (x, y) (respectively NE (y, x)) is the number of votes which prefer x to y (respectively y to x). The maximin score of a candidate x is miny̸=xDE(x, y). The winners are the candidates with maximum maximin score.

Copelandα: The Copelandα score of a candidate x is |{y ̸= x : DE(x, y) > 0}| + α|{y ̸= x : DE(x, y) = 0}|, where α ∈ [0, 1]. The winners are the candidates with the maximum Copelandα score.

For score based voting rules (all the voting rules mentioned above are score based), we denote the score of any candidate x ∈ C by s(x). Given an integer t, we denote the set {1, . . . , t} by [t]. The notion of margin of victory of an election is defined as follows.

Definition 2. (MARGIN OF VICTORY (MOV))

Given an election E = (≻, C) with voting rule r, the margin of victory of E, denoted by Mr(E), is the minimum number of votes that should be changed to change the winning set r(≻).

2.1 Chernoff Bound

We repeatedly use the following concentration inequality:

Theorem 1. Let X1, . . . ,Xℓ be a sequence of ℓ independent random variables in [0, 1] (not necessarily identical). Let S = ∑i Xi and let µ = E [S]. Then, for any 0 ≤ δ ≤ 1:

3 Sample Complexity Lower Bounds

Our lower bounds for the sample complexity of the (c, ε, δ)- MOV problem are derived from the information-theoretic lower bound for distinguishing two distributions. We start with the following basic observation. Let X be a random variable taking value 1 with probability 12 - ε and 0 with probability 12 + ε; Y be a random variable taking value 1 with probability 12 and 0 with probability 12 . Then, it is wellknown that every algorithm needs at least 1 4ε2 ln 1 8e√πδ many samples to distinguish between X and Y with probability of making an error being at most δ [Canetti et al., 1995; Bar-Yossef et al., 2001]. Immediately, we have:

Theorem 2. The sample complexity of the (c, ε, δ)- MOV problem for the plurality voting rule is at least (1-c)2 36ε2 ln ( 1 8e√πδ ) for any c ∈ [0, 1).

Proof: Consider two vote distributions X and Y , each over the candidate set {a, b}. In X, exactly 12 + 6ε+2c/n 1-c fraction of voters prefer a to b and thus the margin of victory is 3ε+c/n 1-c n.

In Y , exactly 12 fraction of voters prefer b to a and thus the margin of victory is one. Any (c, ε, δ)-MOV algorithm A for the plurality voting rule gives us a distinguisher between X and Y with probability of error at most 2δ. This is so because, if the input to A is X then, the output of A is less than c + 2εn with probability at most δ, whereas, if the input to A is Y then, the output of A is more than c + εn with probability at most δ. Now, since n can be arbitrarily large, we get the result. □

Theorem 2 immediately gives the following corollary.

Corollary 1. For any c ∈ [0, 1), every (c, ε, δ)-MOV algorithm needs at least (1-c)2 36ε2 ln ( 1 8e√πδ ) many samples for all voting rules which reduce to the plurality rule for two candidates. In particular, the lower bound holds for scoring rules, approval, Bucklin, maximin, and Copelandα voting rules.

We note that the lower bound results in Theorem 2 and Corollary 1 do not assume anything about the sampling strategy or the computational complexity of the estimator.

4 Sampling Based Algorithms

A natural approach for estimating the margin of victory of an election efficiently is to compute the margin of victory of a suitably small number of sampled votes. Certainly, it is not immediate that samples chosen uniformly at random preserve the value of the margin of victory of the original election within some desired factor. Although it may be possible to formulate clever sampling strategies that tie into the margin of victory structure of the election, we will show that uniformly chosen samples are good enough to design algorithms for estimating the margin of victory for the voting rules studied here. Our proposal has the advantage that the sampling component of our algorithms are always easy to implement, and further, there is no compromise on the bounds in the sense that they are optimal for any constant number of candidates.

Our algorithms involve computing a quantity (which depends on the voting rule under consideration) based on the sampled votes, which we argue to be a suitable estimate of the margin of victory of the original election. This quantity is not necessarily the margin of victory of the sampled votes. For scoring rules, for instance, we will use the sampled votes to estimate candidate scores, and we use the difference between the top two candidate scores (suitably scaled) as the margin of victory estimate. We also establish a relationship between scores and values of the margin of victory to achieve the desired bounds on the estimate. The overall strategy is in a similar spirit for other voting rules as well, although the exact estimates may be different. We now turn to a more detailed description, although some proofs are omitted due to lack of space.

4.1 Scoring Rules and Approval Voting Rule

We begin with the class of scoring rules. Interestingly, the margin of victory of any scoring rule based election can still be estimated quite accurately by sampling only 12 ε2 ln 2m δ many votes. An important thing to note is that, the sample complexity upper bound is independent of the score vector. Before embarking on the proof of this general result, we prove a structural lemma which will be used crucially in the subsequent proof.

Lemma 1. Let α = (α1, . . . , αm) be any normalized score vector (hence, αm = 0). If w and z are the candidates that receive highest and second highest score respectively in a α-scoring rule election instance E = (V, C), then,

Proof: Let Mα(E) be the margin of victory of E. We claim that there must be at least Mα(E)-1 many votes v ∈ V where w is preferred over z. Indeed, otherwise, we swap w and z in all the votes where w is preferred over z. This makes z win the election. However, we have changed at most Mα(E)-1 votes only. This contradicts the definition of margin of victory (see Definition 2). Let v ∈ V be a vote where w is preferred over z. Let αi and αj(≤ αi) be the scores received by the candidates w and z respectively from the vote v. We replace the vote v by v′ = z ≻ · · · ≻ c. This vote change reduces the value of s(w) - s(z) by α1 + αi - αj which is at least α1. Hence, α1(Mα(E)-1) ≤ s(w)-s(z). Each vote change reduces the value of s(w) - s(z) by at most 2α1 since αm = 0. Hence, s(w) - s(z) ≤ 2α1Mα(E). □

With Lemma 1 at hand, we show our estimation algorithm for the scoring rules next.

Theorem 3. There is a polynomial time ( 13 , ε, δ)-MOV algorithm for the scoring rules with sample complexity 12 ε2 ln 2m δ . Proof: Let α = (α1, . . . , αm) be any arbitrary normalized score vector and E = (V, C) an election instance. We sample ℓ (the value of ℓ will be chosen later) votes uniformly at random from the set of votes with replacement. For a candidate x, define a random variable Xi(x) = αi α1 if x gets a score of αi from the ith sample vote. Define ¯ s(x) = nα1 ℓ ∑ℓi=1 Xi(x) the estimate of s(x), the score of x. Also define ε′ = ε2 . Now, using Chernoff bound (Theorem 1), we have the following.

We now use the union bound to get the following.

Define ¯M def == ¯ s( ¯w)-¯ s(¯ z) 1.5α1 the estimate of the margin of victory of the election E (and thus the output of the algorithm), where ¯w ∈ argmaxx∈C{¯ s(x)} and ¯ z ∈ arg maxx∈C\{ ¯w}{¯ s(x)}. We claim that, if ∀x ∈ C, |¯ s(x) - s(x)| ≤ ε′n, then | ¯M -Mα(E)| ≤ 13 Mα(E) + εn. This can be shown as follows.

The second inequality follows from the fact that, ¯ s( ¯w) ≤ s( ¯w)+ε′n ≤ s(w)+ε′n and ¯ s(¯ z) ≥ ¯ s(z) ≥ s(z)-ε′n. The third inequality follows from Lemma 1. Similarly, we bound Mα(E) - ¯M as follows.

This proves the claim. Now, we bound the success probability of the algorithm as follows. Let A be the event that ∀x ∈ C, |¯ s(x) - s(x)| ≤ ε′n.

The third equality follows from Lemma 1 and the fourth inequality follows from inequality 1. Now, by choosing ℓ = 12 ε2 ln 2m δ , we get a ( 13 , ε, δ)-MOV algorithm for the scoring rules. □

Now, we show an algorithm for the (0, ε, δ)-MOV problem for the k-approval voting rule which not only provides more accurate estimate of the margin of victory, but also has a lower sample complexity. The following lemmas will be used subsequently.

Lemma 2. Let E = (V,C) be an arbitrary instance of a k-approval election. If w and z are the candidates that receive highest and second highest score respectively in E, then,

Proof: We call a vote v ∈ V favorable if w appears within the top k positions and z does not appear within top the k positions in v. We claim that the number of favorable votes must be at least Mk-approval(E). Indeed, otherwise, we swap the positions of w and z in all the favorable votes while keeping the other candidates fixed. This makes the score of z at least as much as the score of w which contradicts the fact that the margin of victory is Mk-approval(E). Now, notice that the score of z must remain less than the score of w even if we swap the positions of w and z in Mk-approval(E) - 1 many favorable votes, since the margin of victory is Mk-approval(E). Each such vote change increases the score of z by one and reduces the score of w by one. Hence, 2(Mk-approval(E) - 1) < s(w) - s(z). Again, since the margin of victory is Mk-approval(E), there exists a candidate x other than w and Mk-approval(E) many votes in V which can be modified such that x becomes a winner of the modified election. Now, each vote change can reduce the score of w by at most one and increase the score of x by at most one. Hence, s(w) - s(x) ≤ 2Mk-approval(E) and thus s(w) - s(z) ≤ 2Mk-approval(E) since s(z) ≥ s(x). □

Lemma 3. Let f : R -→ R be a function defined by f(t) = e- λt . Then,

With Lemma 2 and 3 at hand, we now describe our margin of victory estimator.

Theorem 4. There is a polynomial time (0, ε, δ)-MOV algorithm for the k-approval rule whose sample complexity is 12 ε2 ln 2k δ .

Proof: Let E = (V, C) be an arbitrary k-approval election. We sample ℓ votes uniformly at random from V with replacement. For a candidate x, define a random variable Xi(x) which takes value 1 if x appears among the top k candidates in the ith sample vote, and 0 otherwise. Define ¯ s(x) def == nℓ ∑ℓi=1 Xi(x) the estimate of the score of the candidate x, and let s(x) be the actual score of x. Also define ε′ = ε2 . Then by the Chernoff bound (Theorem 1), we have:

Now, we apply the union bound to get the following.

The second inequality follows from Lemma 3 : The expression ∑x∈C 2 exp (- ε′2 ℓn 3s(x) ) is maximized subject to the constraints that 0 ≤ s(x) ≤ n, ∀x ∈ C and ∑x∈C s(x) = kn, when s(x) = n∀x ∈ C ′ for any subset of candidates C ′ ⊆ C with |C ′ | = k and s(x) = 0∀x ∈ C \ C ′ .

Now, to estimate the margin of victory of the given election E, let ¯w and ¯ z be candidates with maximum and second maximum estimated score respectively. That is, ¯w ∈ arg maxx∈C {¯ s(x)} and ¯ z ∈ argmaxx∈C\{ ¯w}{¯ s(x)}. We define ¯M def == ¯ s( ¯w)-¯ s(¯ z) 2 the estimate of the margin of victory of the election E (and thus the output of the algorithm). Let A be the event that ∀x ∈ C, |¯ s(x) - s(x)| ≤ ε′n. We bound the success probability of the algorithm as follows.

The second equality follows from Lemma 2 and an argument analogous to the proof of Theorem 3. The third inequality follows from inequality 2. Now, by choosing ℓ = 12 ε2 ln 2k δ , we get a (0, ε, δ)-MOV algorithm. □

Note that, the sample complexity upper bound matches with the lower bound proved in Corollary 1 for the k-approval voting rule when k is a constant, irrespective of the number of candidates. For the approval voting rule, we have the following result.

Theorem 5. There is a polynomial time (0, ε, δ)-MOV algorithm for the approval rule with sample complexity 12 ε2 ln 2m δ .

4.2 Bucklin Voting Rule

Now, we consider the Bucklin voting rule. Given an election E = (V, C), a candidate x ∈ C, and an integer ℓ ∈ [m], we denote the number of votes in V in which x appears within the top ℓ positions by nℓ(x). We prove useful bounds on the margin of victory of any Bucklin election in Lemma 4.

Lemma 4. Let E = (V,C) be an arbitrary instance of a Bucklin election and w be the winner of E. Let us define a quantity ∆(E) as follows.

Then,

Proof: Pick any ℓ ∈ [m- 1] and x ∈ C \ {w} such that, nℓ(w) > n/2 and nℓ(x) ≤ n/2. Now by changing nℓ(w) - ⌊n/2⌋ many votes, we can ensure that w is not placed within the top ℓ positions in more than n/2 votes: choose nℓ(w) - ⌊n/2⌋ many votes where w appears within top ℓ positions and swap w with candidates placed at the last position in those votes. Similarly, by changing ⌊n/2⌋ + 1 - nℓ(x) many votes, we can ensure that x is placed within top ℓ positions in more than n/2 votes. Hence, by changing at most nℓ(w) - ⌊n/2⌋ + ⌊n/2⌋ + 1 - nℓ(x) = nℓ(w) - nℓ(x) + 1 many votes, we can make w not win the election. Hence, MBucklin(E) ≤ nℓ(w) - nℓ(x) + 1. Now, since we have picked an arbitrary ℓ and an arbitrary candidate x, we have MBucklin(E) ≤ ∆(E).

For the other inequality, since the margin of victory is MBucklin(E), there exists an ℓ′ ∈ [m - 1], a candidate x ∈ C \ {w}, and MBucklin(E) many votes in V such that, we can change those votes in such a way that in the modified election, w is not placed within top ℓ′ positions in more than n/2 votes and x is placed within top ℓ′ positions in more than n/2 votes. Hence, we have the following.

Notice that, given an election E, ∆(E) can be computed in polynomial amount of time. Lemma 4 leads us to the following Theorem.

Theorem 6. There is a polynomial time ( 13 , ε, δ)-MOV algorithm for the Bucklin rule with sample complexity 12 ε2 ln 2m δ .

4.3 Maximin Voting Rule

Next, we show the result for the maximin voting rule.

Lemma 5. Let E = (V,C) be any instance of a maximin election. If w and z are the candidates that receive highest and second highest maximin score respectively in E, then,

Proof: Each vote change can increase the value of s(z) by at most two and decrease the value of s(w) by at most two. Hence, we have s(w) - s(z) ≤ 4Mmaximin(E).

Let x be the candidate that minimizes DE(w, x), that is, x ∈ argminx∈C\{w}{DE(w, x)}. Let v ∈ V be a vote where w is preferred over x. We replace the vote v by the vote v′ = z ≻ x ≻ · · · ≻ w. This vote change reduces the score of w by two and does not reduce the score of z. Hence, s(w) - s(z) ≥ 2Mmaximin(E). □

Theorem 7. There is a polynomial time ( 13 , ε, δ)-MOV algo-

rithm for the maximin rule with sample complexity 24 ε2 ln 2m δ . Proof sketch: Let E = (V,C) be an instance of maximin election. Let x and y be any two candidates. We sample ℓ votes uniformly at random from the set of all votes with replacement. Let Xi(x, y) be a random variable taking value 1 if x ≻ y in the ith sample vote and -1 otherwise. Define ¯ DE(x, y) = nℓ ∑ℓi=1 Xi(x, y). By using the Chernoff bound and union bound, we have the following.

We define ¯M def == ¯ s( ¯w)-¯ s(¯ z) 3 , the estimate of the margin of victory of E, where ¯w ∈ argmaxx∈C{¯ s(x)} and ¯ z ∈ argmaxx∈C\{ ¯w}{¯ s(x)}. Now, using Lemma 5, we can complete the rest of the proof in a way that is analogous to the proof of Theorem 3. □

4.4 Copelandα Voting Rule

Now, we present our result for the Copelandα voting rule. Xia introduced the brilliant quantity called the relative margin of victory (see Section 5.1 in [Xia, 2012]) which is a crucial ingredient in our algorithm for the Copelandα voting rule. Given an election E = (V,C), a candidate x ∈ C, and an integer (may be negative also) t, s′t (V, x) is defined as follows.

For every two distinct candidates x and y, the relative margin of victory, denoted by RM(x, y), between x and y is defined as the minimum integer t such that, s′-t (V, x) ≤ s′t (V, y). Let w be the winner of the election E. We define a quantity Γ(E) to be minx∈C\{w}{RM(w, x)}. Notice that, given an election E, Γ(E) can be computed in a polynomial amount of time. Now we have the following lemma.

Theorem 8. For the Copelandα voting rule, there is a polynomial time (1-O ( 1 log m ) , ε, δ)-MOV algorithm whose sample complexity is 96 ε2 ln 2m δ .

Proof: Let E = (V,C) be an instance of a Copelandα election. For every x, y ∈ C, we compute ¯ DE(x, y), which is an estimate of DE(x, y), within an approximation factor of (0, ε′ ), where ε′ = ε4 . This can be achieved with an error probability at most δ by sampling 96 ε2 ln 2m δ many votes uniformly at randomwith replacement (the argument is same as the proof of Theorem 3). We define ¯ s′t (V, x) = |{y ∈ C : y ̸= x,DE(y, x) < 2t}| + α|{y ∈ C : y ̸= x,DE(y, x) = 2t}|. We also define RM(x, y) between x and y to be the minimum integer t such that, ¯ s′-t (V, x) ≤ s′t (V, y). Let ¯w be the winner of the sampled election, ¯ z = arg minx∈C\{ ¯w}{RM(w, x)}, w the winner of E, and z = argminx∈C\{w}{RM(w, x)}. Since, ¯ DE(x, y) is an approximation of DE(x, y) within a factor of (0, ε′ ), we have the following for every candidate

Define ¯Γ(E) = RM( ¯w, ¯ z) to be the estimate of Γ(E). We show the following claim.

Claim 1. With the above definitions of w, z, ¯w, and ¯ z, we have the following.

Proof: Below, we show the upper bound for ¯Γ(E).

The second inequality follows from the fact that ¯ DE (x, y) is an approximation of DE(x, y) by a factor of (0, ε′ ). The third inequality follows from the definition of ¯ z, and the fourth inequality uses inequality 3. Now, we show the lower bound for ¯Γ(E).

The third inequality follows from inequality 3 and the fourth inequality follows from the definition of z. □ We define ¯M, the estimate of MCopelandα(E), to be 4(log m+1) 2 logm+3 ¯Γ(E). The following argument shows that ¯M is a (1-O ( 1 log m ) , ε, δ)-estimate of MCopelandα(E).

The second inequality follows from Claim 1 and the third inequality follows from Lemma 6. Analogously, we have:

The second line follows Claim 1 and the third line follows from Lemma 6. □

The approximation factor in Theorem 8 is weak when we have a large number of candidates. The main difficulty for showing a better approximation factor for the Copelandα voting rule is to find a polynomial time computable quantity (for example, Γ(E) in Lemma 6) that exhibits tight bounds with margin of victory. We remark that, existence of such a quantity will not only imply a better estimation algorithm, but also, a better approximation algorithm (the best known approximation factor for finding the margin of victory for the Copelandα voting rule is O(logm) and it uses the quantity Γ(E)). However, we remark that Theorem 8 will be useful in applications, for example, post election audit and polling, where the number of candidates is often small.

5 Conclusion

We have introduced the (c, ε, δ)-MOV problem and presented efficient sampling based algorithms for solving it for many commonly used voting rules. Besides closing the gap in the sample complexity, an interesting future direction is to study how the knowledge of social network structure among the voters impacts sample complexity. Characterizing voting rules for which the sample complexity of this problem is independent of m and n is another interesting research direction to pursue.