Protecting Elections by Recounting Ballots

1 Introduction

Democratic societies use elections to select their leaders. However, in societies without a strong democratic tradition, elections may be used as a way to legitimize the status quo: voters are asked to cast their ballots, but the election authorities do not count these ballots correctly, in order to produce an outcome that favors a specific candidate. There are multiple reports of such cases in Russia 1 , Congo 2 and Colombia 3 , as well as a number of other countries. Even when the election authorities are trustworthy, election results may be corrupted by an external party, for instance, by means of hacking electronic voting machines [Springall et al., 2014; Halderman and Teague, 2015].

There are several ways to counteract electoral fraud. One approach is to send observers to polling stations, to ensure that only eligible voters participate in the election and their ballots are counted correctly. However, it may be infeasible for the party that wants to protect the election (the defender) to send observers to all polling stations. Consequently, the election manipulator (the attacker) may observe which polling stations remain unprotected, and focus their effort on these stations. Thus, under this approach the attacker benefits from the second-mover advantage.

1 https://reut.rs/2Gf2FD5

2 https://on.ft.com/2SW7ggy

3 https://bit.ly/2V45gDV

An alternative approach that the defender can explore is to request recounts in some of the voting districts. While recounts cannot protect from all forms of attacks on election integrity (e.g., a recount is of limited use if voters have been bribed to vote in a specific way, or if the polling station has been burned down), they are feasible in a range of settings and offer the defender the second-mover advantage. Indeed, there are several examples where a recount changed the election outcome. For instance, in the 2008 United States Senate election in Minnesota the Democratic candidate Al Franken won the seat after a recount revealed that 953 absentee ballots were wrongly rejected 4 and in the 2004 race for governor in Washington the Democratic candidate Gregoire was declared the winner after three consecutive recounts 5 .

However, recounts can be costly. In Gregoire's case, the Democratic party paid $730000 for a statewide manual recount, and in the 2016 US Presidential Election the fee to initiate a recount in Wisconsin was $3.5 million. Thus, a party that would like to initiate a recount in order to rectify the election results should allocate its budget carefully. Of course, the attacker also incurs costs to carry out the fraud: local election officials may need to be bribed or intimidated, and the more districts are corrupted, the higher is the risk that the election results will not be accepted.

Our Contribution

In this paper we analyze the strategic game associated with vote recounting. In our model, there are two players: the attacker, who modifies some of the votes in order to make his preferred candidate p the election winner, and the defender, who observes the attacker's actions and tries to restore the correct outcome (or, more broadly, to ensure that a candidate better than p wins the election) by means of recounting some of the votes. We assume that the set of voters is partitioned into electoral districts, and both the defender and the attacker make their choices at the level of districts rather than individual votes. The attacker selects a subset of at most BA districts and changes the vote counts in the selected districts, and the defender can then restore the vote counts in at most BD districts to their original values. We assume that both players have full information about the true votes and each other's budgets, and the defender can observe the attacker's actions. While the full information assumption is not entirely realistic, we note that in a district-based model both parties only need to know the vote counts in each district rather than individual votes, and one can get fairly accurate districtlevel information from independent polls. Also, verifying whether the votes in a district have been tampered with is possible using risk-limiting audits [Lindeman and Stark, 2012; Sch¨urmann, 2016].

4 https://bit.ly/2S2PMxY

5 https://bit.ly/2tnO4gG

For simplicity, we focus on the Plurality voting rule, where each voter votes for a single candidate. We consider two implementations of this rule: (1) Plurality over Voters, where districts are only used for the purpose of collecting the ballots and the winner is selected among the candidates that receive the largest number of votes in total, and (2) Plurality over Districts, where each district selects a preferred candidate using the Plurality rule, and the overall winner is chosen among the candidates supported by the largest number of districts; we also consider a variant of the latter rule where districts have weights, and the measure of a candidate's success is the total weight of districts that support her. Both of these rules are widely used in practice: Plurality over Voters is commonly used in gubernatorial elections in the US, while Plurality over Districts is used in the US Presidential elections.

We provide a detailed analysis of the computational complexity of the algorithmic problems faced by the attacker and the defender. Our main results are summarized in Table 1. Briefly, assuming that the vote counts and the weights of the districts are specified in binary, most of the problems we consider are computationally hard; however, the defender's problem appears to be easier than that of the attacker, and we also get some tractability results for the former. Towards the end of the paper, we consider a variant of our model where the attacker is limited to only transferring support to his preferred candidate; we show that, while this assumption reduces the attacker's ability to achieve his goals, it lowers the complexity of some of the problems we consider.

Related Work

There is a very substantial literature on voting manipulation and bribery; we point the readers to the excellent surveys of Conitzer and Walsh [2016] and Faliszewski and Rothe [2016]. In much of this literature it is assumed that the malicious party can change some of the votes subject to various constraints, and the challenge is to determine whether the attacker's task is computationally feasible; there is no defender that can counteract the attacker's actions. While there is a number of papers that apply game-theoretic analysis to the problem of voting manipulation, they typically consider interactions among several manipulators, with possibly conflicting goals (e.g., see the recent book by Meir [2018]), rather than a manipulator and a socially-minded actor. An important exception, which is similar in spirit to our paper, is the recent work of Yin et al. [2018], who investigate a pre-emptive approach to protecting elections. In their model the defender allocates resources to guard some of the electoral districts, so that the votes there cannot be corrupted; notably, in this model the defender has to commit to its strategy first, and the attacker can observe the defender's actions before deciding on its response. The leader-follower (defender-attacker) structure of this model is in the spirit of a series of successful applications of Stackelberg games to security resource allocation problems [Tambe, 2011]. Li et al. [2017] analyze a variant of the model of Yin et al. where the goal is to minimize resource consumption, and Chen et al. [2018] study a similar scenario, in which manipulation is achieved through bribing the voters. The key difference between our work and the above papers is the action order of the players: in all prior work on election protection that we are aware of the defender makes the first move.

2 The Model

We consider elections over a candidate set C, |C| = m. There are n voters who are partitioned into k pairwise disjoint districts D1, . . . ,Dk, k ≤ n; for each i ∈ [k], let ni = |Di|. For each i ∈ [k], district Di has a weight wi, which is a positive integer; we say that an election is unweighted if wi = 1 for all i ∈ [k]. Each voter votes for a single candidate in C. For each i ∈ [k] and each a ∈ C let via denote the number of votes that candidate a gets from voters in Di; we refer to the list v = (via)i∈[k],a∈C as the vote profile.

Let ≻ be a linear order over C; a ≻ b indicates that a is favored over b. We consider the following two voting rules, which take the vote profile v as their input.

• Plurality over Voters (PV). The winner a∗ is chosen from the set argmaxa∈C ∑i∈[k] via, with ties broken according to ≻. Note that district weights wi are not

relevant for this rule.

• Plurality over Districts (PD). For each i ∈ [k] the winner ai in Di is chosen from the set arg maxa∈C via, with ties broken according to ≻. Then, for each i ∈ [k], a ∈ C, we set wia = wi if a = ai and wia = 0 otherwise. The winner a∗ is chosen from the set argmaxa ∑i∈[k] wia, with ties broken according to ≻.

For PV and PD, we define the social welfare of a candidate a ∈ C as the total number of votes that a gets and the total weight that a gets, respectively:

Hence, each voting rule selects a candidate that maximizes the respective social welfare.

We consider scenarios where an election may be manipulated by an attacker, who wants to change the election result a∗ in favor of his preferred candidate p ∈ C. The attacker has a budget BA ∈ [k], which means that he can manipulate at most BA districts. For each i ∈ [k], we are given an integer γi, 0 ≤ γi ≤ ni, which indicates how many votes the attacker can change in district i if he chooses to manipulate it. Formally, a manipulation is described by a set M ⊆ [k], |M| ≤ BA, and a vote profile ˜v = (˜ via)i∈[k],a∈C such that ˜ via = via for all i ̸∈ M, a ∈ C, and for all i ∈ [k] it holds that ∑a∈C ˜ via = ni and ∑a∈C max{0, ˜ via - via} ≤ γi.

After the attack, a defender with budget BD ∈ {0} ∪ [k] can demand a recount in at most BD districts. Formally, a defender's strategy is a set R ⊆ M with |R| ≤ BD; after the defender acts, the vote counts in all districts in R are restored to their original values, i.e., the resulting vote profile u = (uia)i∈[k],a∈C satisfies uia = via for each i ∈ R, a ∈ C and uia = ˜ via for each i ∈ [k] \ R, a ∈ C. Then the underlying voting rule R ∈ {PV, PD} is applied to u with ties broken according to ≻; let a′ denote the candidate selected in this manner. The defender chooses her strategy R so as to maximize SWR(a′ ), breaking ties using ≻.

We say that the attacker wins if he has a strategy (M, ˜v) such that, once the defender responds optimally, candidate p is the winner in the resulting vote profile u; otherwise we say that the attacker loses. We note that if BD ≥ BA, the defender can always ensure that a′ = a∗ , i.e., the winner at u is the winner at the original vote profile v, so in what follows we assume that BD < BA.

Example 2.1. Consider an election with five districts D1, . . . ,D5 over a candidate set C = {a, b, p}, where p is the attacker's preferred candidate; suppose that ties are broken according to the priority order p ≻ a ≻ b. In each of D1 and D2 there are 7 voters who vote for a, and in each of D3, D4 and D5 there are 3 voters who vote for b. Suppose that γi = ni and wi = (ni)2 for each i ∈ [5], and BA = 2, BD = 1.

If the voting rule is PV, then the attacker does not have a winning strategy. Indeed, consider an attacker's strategy (M, ˜v). If M ̸= {1, 2}, the defender can set R = M∩{1, 2}; in the recounted vote profile a gets at least 14 votes, so it is the election winner. If M = {1, 2}, the defender can set R = {1}: in the recounted vote profile p gets at most 7 votes, while b gets at least 9 votes, so the winner is a or b (a can win if, e.g., the attacker chooses to transfer exactly 4 votes from a to p in D2, in which case a gets 10 votes after the recount). Note that even if the winner in u is b rather than a, the defender still prefers recounting D1 to no recounting: even though she cannot restore the correct result, she prefers b to p, since SWPV (b) = 9 > 0 = SWPV (p).

If the voting rule is PD, then the attacker can win by choosing M = {1, 2} and transferring the majority of votes from a to p in both manipulated districts. Indeed, even if the defender demands a recount in one of these districts, p still wins the remaining district, leading to a vote weight of 49 in the recounted profile. Since a's vote weight is 49 and b's vote weight is 27, p wins by the tie-breaking rule.

We assume that both the defender and the attacker have full information about the game. Both parties know the true vote profile v, the parameters wi and γi for each district i ∈ [k] and each others' budgets. Moreover, the defender observes the strategy (M, ˜v) of the attacker.

We can now define the following decision problems for each R ∈ {PV, PD}:

• R-MAN: Given a vote profile v, the attacker's preferred candidate p, budgets BA and BD, and district parameters (wi, γi)i∈[k], does the attacker have a winning strategy?
• R-REC: Given a vote profile v, a distorted vote profile ˜v with winner b, a candidate a ̸= b, a budget BD, and district weights (wi)i∈[k], can the defender recount the votes in at most BD districts so that a gets elected?

We will also consider an optimization version of R-REC, where a is not part of the input and the goal is to maximize the social welfare of the eventual winner.

Unless specified otherwise, we assume that the vote counts via and the district weights wi are given in binary; we explicitly indicate which of our hardness results still hold if these numbers are given in unary. All problems considered in this paper admit straightforward greedy algorithms for m = 2, so in what follows we focus on the case m ≥ 3. When the voting rule R ∈ {PV,PD} is clear from context, we write SW(a) instead of SWR(a). Due to space constraints, most proofs are omitted.

3 Plurality over Voters

In this section we focus on Plurality over Voters. We first take the perspective of the defender, and then the perspective of the attacker.

Unfortunately, the defender's problem turns out to be computationally hard, even if there are only three candidates or if the input vote counts are given in unary.

Theorem 3.1. PV-REC is NP-complete even when

• (i) m= 3, or
• (ii) the input vote profile is given in unary.

Proof. This problem is clearly in NP. The hardness proof in part (i) follows by a reduction from SUBSET SUM; we omit the details. For part (ii), we give a reduction from EXACT COVER BY 3-SETS (X3C). An instance of this problem is a set E of size 3ℓ and a collection S of s 3-element subsets of E; it is a yes-instance if there exists a sub-collection Q ⊆ S of size ℓ such that ∪S∈QS = E. Given an instance of X3C, we construct the following PV-REC instance. Without loss of generality, we assume that ∩S∈SS = ∅.

• Let C = {je : e ∈ E} ∪ {a, b}, |C| = 3ℓ + 2.
• For each subset S ∈ S, there is a district DS with true votes vS,a = 2, vS,b = 6, vS,je = 2 for all e /∈ S, and vS,je = 0 for all e ∈ S. The attacker distorts the votes in these districts to ˜ vS,j = 2 for every j ∈ C \ {b}, ˜ vS,b = 0.
• There is a district Di∗ with true votes vi∗ ,a = 6ℓs, vi∗ ,b = 0, and vi∗ ,je = 6ℓs + 1 for every e ∈ E, which is not distorted.
• The budget of the defender is BD = ℓ.

Candidate a is the true winner with 2s+6ℓs votes, compared to the 6s votes of b and the 2|{S ∈ S : e /∈ S}| + 6ℓs + 1 ≤ 2s + 6ℓs - 1 votes of je for every e ∈ E. In the distorted profile ˜v candidate a gets 2s + 6ℓs votes, candidate b gets 0 votes, and each candidate in C\{a, b} gets 2s+6ℓs+1 votes. The goal of the defender is to restore candidate a.

Recounting a district DS reduces by 2 the votes of each candidate je such that e ∈ S, leading to a getting more votes than these candidates; b cannot get more than 6s votes no matter what the defender does. Therefore, a can be restored as the winner by recounting ℓ districts if and only if E can be covered by ℓ sets from S.

If the number of candidates is bounded by a constant and the input is given in unary, an optimal set of districts to recount can be identified in time polynomial in the input size by means of dynamic programming.

Theorem 3.2. PV-REC can be solved in time O(k·BD ·nm).

We obtain similar hardness results for the attacker's problem. However, it is not clear if PV-MAN is in NP. Indeed, it may belong to a higher level of the polynomial hierarchy: it is not hard to see that PV-MAN is in ΣP2 , and it is plausible that this problem is hard for this complexity class.

Theorem 3.3. PV-MAN is NP-hard even when BD = 0, γi = ni for all i ∈ [k] and

• (i) m= 3, or
• (ii) the input vote profile is given in unary.

In the hardness reductions in the proof of Theorem 3.3 the defender's budget is 0. This indicates that the attacker's problem remains NP-hard even if the defender is known to use a heuristic (e.g., a greedy algorithm) to compute her response.

We remark that PV-REC and PV-MAN with BD = 0 are very similar in spirit to combinatorial (shift) bribery [Bredereck et al., 2016]. In both models, a budget-constrained agent needs to select a set of vote-changing actions, with each action affecting a group of voters. However, there are a few technical differences between the models. For instance, in our model different actions are associated with non-overlapping groups of voters, which is not the case in combinatorial shift bribery. On the other hand, in shift bribery under the Plurality rule votes can only be transferred to/from the manipulator's preferred candidate p, while our model does not impose this constraint (see, however, Section 5). Consequently, it appears that the technical results in our paper cannot be derived from known results for combinatorial shift bribery.

4 Plurality over Districts

In this section we study Plurality over Districts. For the defender's problem, we can replicate the results we obtain for Plurality over Voters, by using similar techniques; in particular, for both of our hardness results it suffices to set wi = ni for each i ∈ [k].

Theorem 4.1. PD-REC is NP-complete even when

• (i) m= 3, or
• (ii) the input vote profile and district weights are given in unary.

Theorem 4.2. PD-REC can be solved in time O(k·BD ·nm).

We also obtain a positive result that does not have an analogue in the PV setting; if all districts have the same weight, the recounting problem can be solved efficiently.

Theorem 4.3. PD-REC can be solved in polynomial time if wi = 1 for all i ∈ [k].

Proof. We reduce our problem to nonuniform bribery [Faliszewski, 2008]. An instance of nonuniform bribery under the Plurality rule is given by a set of voters and a set of candidates; for each voter i and each candidate c there is a price pic for making voter i vote for c, and the briber's goal is to make her preferred candidate the Plurality winner 6 while staying within a budget B. This problem is known to be in P [Faliszewski, 2008]. To reduce PD-REC to nonuniform bribery, we map each district Di to a single voter i; if the true winner in Di is x, and in the distorted profile the winner in Di is y, we set piy = 0, piz = +∞ for z ∈ C \ {x, y}, and if x ̸= y (i.e., if the attacker has changed the outcome in Di), we set pix = 1. Then for any candidate c ∈ C it holds that in PDREC the defender can make c win by recounting at most BD districts if and only if in our instance of nonuniform bribery the briber can make c win by spending at most BD.

We now consider the attacker's problem. Interestingly, for the PD rule, we can actually show a ΣP2 -hardness result. Our reduction uses a variant of the SUBSET SUM problem, which we term SUB-SUBSET SUM (SSS); this problem may be of independent interest. An instance of this problem is a set X ⊆ Z and a positive integer ℓ. It is a yes-instance if there is a subset X′ ⊆ X with |X′ | = ℓ such that ∑x∈X′′ x ̸= 0 for every non-empty subset X′′ ⊆ X′ . Our proof proceeds by establishing that SSS is ΣP2 -complete (Lemma 4.4), and then reducing this problem to PD-MAN.

PD-MAN remains computationally hard when the input is given in unary; actually, we conjecture that it remains ΣP2 - complete, but we were only able to prove NP-hardness. If we further assume that all districts have the same weight, the problem can be shown to be NP-complete. These results are summarized in Theorem 4.5.

6 Faliszewski [2008] assumes that ties are broken in favor of the briber, but his results extend to lexicographic tie-breaking.

Lemma 4.4. SSS is ΣP2 -complete.

Theorem 4.5. PD-MAN is NP-hard, and more specifically:

• (i) ΣP2 -complete, even when m = 3;
• (ii) NP-hard, even when BD = 0 and the input vote profile and district weights are given in unary;
• (iii) NP-complete when wi = 1 for all i ∈ [k].

Proof. We give the proof for part (i). The hardness results in parts (ii) and (iii) follow by reductions from the INDEPENDENT SET problem.

Clearly, PD-MAN is in ΣP2 . To prove hardness, we reduce from SSS. Given an instance 〈X, ℓ〉 of SSS, we construct an instance of PD-MAN with three candidates {a, b, p}. Let X+ = {x ∈ X : x > 0} and X- = X \ X+. Set y = ∑x∈X 3|x|. In what follows we describe the votes in each district Di as a list (via, vib, vip). The districts are partitioned into three sets I1, I2 and I3:

• I1 has a district with votes (0, 3x, 0) for each x ∈ X+, and a district with votes (0, 0, -3x) for each x ∈ X-.
• I2 consists of a single district with votes (0, y + 3, 0).
• I3 consists of three districts with votes (2y + 5, 0, 0), (0, y - ∑x∈X+ 3x, 0), and (0, 0, 2y + 4 + ∑x∈X- 3x).

For every district Di we set wi = ni. The attacker is allowed to change all votes in each district in I1 and I2, but none in I3. Finally, let BA = ℓ + 1 and BD = ℓ. The true winner in this profile is candidate a with weight 2y + 5, compared to the weight 2y + 3 of b and 2y + 4 of p.

Given a set of integers Y ⊆ X, let I1(Y ) be the corresponding set of districts in I1. Assume that there is a subset X′ ⊆ X with |X′ | = ℓ such that no X′′ ⊆ X′ has sum equal to 0. The attacker can then exchange the weights of b and p in the districts in I1(X′ ) and the district in I2. This way, p becomes the winner with weight 3y + 7 + ∑x∈X′ 3x ≥ 2y + 7, compared to the weight 2y + 5 of a and the weight y - ∑x∈X′ 3x ≤ 2y of b.

Since SW(p) > SW(b), to defeat the attacker, the defender needs to restore a as the winner. To this end, she must recount the district in I2, as otherwise p's weight will remain at least 2y + 7. Hence she can recount at most ℓ - 1 manipulated districts in I1. Let the set of non-recounted districts in I1 be I1(X′′ ) for some X′′ ⊆ X′ ; note that X′′ ̸= ∅, so by assumption, ∑x∈X′′ x ̸= 0. Then, the weight of b is 2y+3∑x∈X′′ 3x and the weight of p is 2y + 4 + ∑x∈X′′ 3x. At least one of these numbers is greater than or equal to 2y + 6; thus, a cannot be restored as the winner.

Conversely, suppose that for every subset X′ ⊆ X of size ℓ there exists a non-empty X′′ ⊆ X′ such that ∑x∈X′′ x = 0. Then, the attacker cannot win. Indeed, let M be the set of manipulated districts. If a district is changed in favor of a, the defender can recount all other districts in M. On the other hand, if all districts in M are won by b or p, the defender can identify a non-empty subset of M ∩ I1 such that the corresponding integers sum up to 0, and request a recount of all other districts in M. Such a recount recovers the correct weights of b and p, and a is restored as the winner.

The second hardness result of Theorem 4.5 holds even for BD = 0, but for the first and the third part of this theorem this is not the case. In fact, PD-MAN is in NP when BD = 0, since the attacker simply needs to guess a manipulation and check whether it makes p the winner. The unweighted case (part (iii)) can be shown to be in P when BD = 0, using a reduction to nonuniform bribery similar to the one in the proof of Theorem 4.3. Thus, recounting has a clear impact on the complexity of the attacker's problem.

5 Regular Manipulations

In our model, the attacker does not have to transfer votes to his preferred candidate p in the manipulated districts; indeed, he may even choose to transfer votes from p to another candidate. However, manipulations that give additional votes to candidates other than p are counterintuitive and may be difficult to implement in practice. Therefore, in this section we study what happens if the attacker is limited to transferring votes (in case of PV) or vote weight (in case of PD) to his preferred candidate p.

Definition 5.1 (Regular manipulation). Let p be the preferred candidate of the attacker. A manipulation (M, ˜v) is said to be regular if for every district i ∈ M it holds that

• the voting rule is PV and ˜ via ≤ via for all a ∈ C \ {p};
• the voting rule is PD and in ˜v candidate p is the winner in each district inM.

The difference between our general model and the one where the attacker is limited to using regular manipulations is similar to the difference between swap bribery and shift bribery [Elkind et al., 2009]: in swap bribery the attacker can change the vote in any way he likes subject to budget constraints, while in shift bribery he is limited to shifting his preferred candidate in voters' rankings.

One may expect that the restriction to regular manipulations is without loss of generality: indeed, why would the attacker want to transfer votes to candidates other than p? However, our next example shows that this intuition is incorrect.

Also, BA = 2, BD = 1, and γi = ni for all i ∈ [12]. The true winner is candidate a with 9 votes, compared to the 6 votes of p and the 4 votes of b. No regular manipulation can make p win: no matter what the attacker does, by recounting at most one district the defender can ensure that a gets at least 8 votes and p gets at most 7 votes.

Now, consider a non-regular manipulation that distorts all votes in D1 in favor of b, and all votes in D2 in favor of p.

Then in the distorted profile a has 6 votes and p has 3 votes, and b wins with 10 votes. If the defender does not recount D1, b remains the winner after recounting, and if she does recount it, p becomes the winner. Crucially, since SW(b) < SW(p), the defender prefers the latter option, so p wins after the recount.

Example 5.2 shows that only considering regular manipulations may be suboptimal for the attacker. However, the attacker may be limited to regular manipulations by practical considerations. For instance, the election officials in the manipulated districts may find it difficult to follow complex instructions. Thus, it is interesting to understand if focusing on regular manipulations affects the complexity of the problems we consider. It turns out that this is indeed the case.

Let R ∈ {PV, PD}, and consider a regular manipulation (M, ˜v). Note that if p is not a winner at ˜v, the attacker necessarily loses: since (M, ˜v) is regular, any recounts can only decrease the votes/weight of p and will not decrease the votes/weight of the current winner. Thus, we can assume that p is the winner at ˜v. The defender can then try the following greedy strategy. Initially, it defines the set of provisional winners to consist of p. Then, for each a ∈ C \ {p} such that SWR(a) > SWR(p) or SWR(a) = SWR(p) and a ≻ p the algorithm sorts the districts in M in non-increasing order of the quantity (via -vip)-(˜ via - ˜ vip) for PV, and the quantity (wia -wip)-( ˜wia - ˜wip) for PD; ties are broken arbitrarily. Next, it checks what happens if the first BD districts in this order are recounted; if this results in a candidate b ∈ C \ {p} with SWR(b) > SWR(p) or SWR(b) = SWR(p), b ≻ p winning the election, the defender adds b to the set of provisional winners. Finally, it outputs the provisional winner with the maximum social welfare, breaking ties according to ≻. We refer to this algorithm as greedy recounting; note that its running time is polynomial in the input size.

Lemma 5.3. Let R ∈ {PV,PD}. Suppose that the attacker uses a regular manipulation (M, ˜v). Then greedy recounting outputs p if and only if (M, ˜v) is a winning strategy for the attacker.

Notably, greedy recounting does not constitute an algorithm for R-REC: it is unable to decide whether there is a recounting strategy that results in a specific candidate becoming the election winner. However, Lemma 5.3 implies that if the attacker is limited to using regular manipulations, his decision problem R-MAN is in NP: he can guess a regular manipulation and use greedy recounting to verify whether it is successful. As the hardness proofs in Theorem 3.3 use regular manipulations, PV-MAN is NP-complete in this case.

Theorem 5.4. For regular manipulations, PV-MAN is NPcomplete. The hardness result holds even if m = 3 or if the input vote profile and district weights are given in unary.

In contrast, the hardness proofs for PD-MAN (Theorem 4.5) rely on the attacker using a non-regular strategy, and hence they do not imply that PD-MAN remains hard when the attacker is restricted to regular manipulations. In fact, this variant of PD-MAN is in P.

Theorem 5.5. For regular manipulations, PD-MAN can be solved in polynomial time.

Moreover, it turns out that greedy recounting serves as a 1/2-approximation algorithm for the defender: it outputs a candidate a such that for every candidate a′ that can be made a winner by recounting at most BD districts it holds that SW(a) ≥ SW(a′ )/2.

Theorem 5.6. For regular manipulations, greedy recounting is a 1/2-approximation algorithm for the optimization versions of PV-REC and PD-REC.

In fact, the bound on the approximation ratio provided by Theorem 5.6 is essentially tight.

Theorem 5.7. For regular manipulations and any constant ε > 0, neither PV-REC nor PD-REC admit a polynomialtime ( 1 2 + ε)-approximation algorithm unless P = NP, even when m = 3.

6 Conclusion and Open Problems

We have studied the problem of protecting elections by means of recounting votes in the manipulated districts. Our results offer an almost complete picture of the worst-case complexity of the problems faced by the defender and the attacker. Perhaps the most obvious open question is whether we can strengthen the NP-hardness results for PV-MAN and for PDMAN under unary representation to ΣP2 -completeness results. The next challenge is to extend our results beyond Plurality; e.g., leadership elections are often conducted using Plurality with Runoff, and it would be interesting to understand if similar results hold for this rule.

Our model is quite expressive: districts may have different weights, and an attacker may only be able to corrupt a fraction of votes in a district. These features of the model are intended to capture the challenges of real-world scenarios; in particular, it is typically infeasible for the attacker to change all votes in a district. However, it is important to understand their impact on the complexity of the problems we consider. We tried to indicate which of our hardness results hold for special cases of the model, and proved some easiness results under simplifying assumptions, but it would be good to obtain a more detailed picture, possibly using the tools of parameterized complexity. A concrete open question is whether our ΣP2 -hardness result holds if γi = ni for all i ∈ [k].

We contrasted out model with that of Yin et al. [2018], where the defender moves first and protects some of the districts from manipulation. In practice, the defender can use a variety of protective measures at different points in time, and an exciting direction for future work is to analyze what happens when the defender can split her resources among different activities, with some activities preceding the attack, and others (such as recounting) undertaken in the aftermath of the attack.

Acknowledgements

This work is supported by the European Research Council (ERC) under grant number 639945 (ACCORD), by the EPSRC International Doctoral Scholars Grant EP/N509711/1, by the MOE AcRF-T1-RG23/18 grant, and by the NTU SUG M4081985 grant.