A Parameterized Perspective on Protecting Elections

1 Introduction

The problem of election control asks if it is possible for an external agent, usually with a fixed set of resources, to influence the outcome of the election by altering its structure in some limited way. There are several specific manifestations of this problem: for instance, one may ask if it is possible to change the winner by deleting k voter groups, presumably by destroying ballot boxes or rigging electronically submitted votes. Indeed, several cases of violence at the ballot boxes have been placed on record [Bhattacharjya, 2010; RT, 2013], and in 2010, Halderman and his students exposed serious vulnerabilities in the electronic voting systems that are in widespread use in several states [Hal, 2010]. A substantial amount of the debates around the recently concluded presidential elections in the United States revolved around issues of potential fraud, with people voting multiple times, stuffing ballot boxes, etc. all of which are well recognized forms of election control. For example, [Wolchok et al., 2012] studied security aspects on Internet voting systems.

The study of controlling elections is fundamental to computational social choice: it is widely studied from a theoretical perspective, and has deep practical impact. The pioneering work of [Bartholdi et al., 1992] initiated the study of these problems from a computational perspective, hoping that computational hardness of these problems may suggest a substantial barrier to the phenomena of control: if it is, say NP-hard to control an election, then the manipulative agent may not be able to compute an optimal control strategy in a reasonable amount of time. This basic approach has been intensely studied in various other scenarios [Faliszewski et al., 2011; Mattei et al., 2014; Dey, 2018; Dey et al., 2018; 2017; Dey and Misra, 2017; Dey et al., 2015; Dey, 2019].

Exploring parameterized complexity of various control problems has also gained a lot of interest. For example, [Betzler and Uhlmann, 2009] studied parameterized complexity of candidate control in elections and showed interesting connection with digraph problems, [Liu and Zhu, 2010; 2013] studied parameterized complexity of control problem by deleting voters for many common voting rules, and so on [Dey et al., 2016; 2019a]. Studying election control from a game theoretic approach using security games is also an active area of research. See, for example, the works of [An et al., 2013; Letchford et al., 2009].

The broad theme of using computational hardness as a barrier to control has two distinct limitations: one is, of course, that some voting rules simply remain computationally vulnerable to many forms of control, in the sense that optimal strategies can be found in polynomial time. The other is that even NP-hard control problems often admit reasonable heuristics, can be approximated well, or even admit efficient exact algorithms in realistic scenarios. Therefore, relying on NP-hardness alone is arguably not a robust strategy against control. To address this issue, the work of [Yin et al., 2016] explicitly defined the problem of protecting an election from control, where in addition to the manipulative agent, we also have a "defender", who can also deploy some resources to spoil a planned attack. In this setting, elections are defined with respect to voter groups rather than voters, which is a small difference from the traditional control setting. The voter groups model allows us to consider attacks on sets of voters, which is a more accurate model of realistic control scenarios.

In [Yin et al., 2016], the defense problem is modeled as a Stackelberg game in which limited protection resources (say kd) are deployed to protect a collection of voter groups and the adversary responds by attempting to subvert the election (by attacking, say, at most ka groups). They consider the plurality voting rule, and show that the problem of choosing the minimal set of resources that guarantee that an election cannot be controlled is NP-hard. They further suggest a Mixed-Integer Program formulation that can usually be efficiently tackled by solvers. Our main contribution is to study this problem in a parameterized setting and provide a refined complexity landscape for it. We also introduce the complementary attack problem, and extend the study to voting rules beyond plurality. We now turn to a summary of our contributions.

1.1 Contribution

We refer the reader to Section 2 for the relevant formal definitions, while focusing here on a high-level overview of our results. Recall that the OPTIMAL DEFENSE problem asks for a set of at most kd voter groups which, when protected, render any attack on at most ka voter groups unsuccessful. In this paper, we study the parameterized complexity of OPTIMAL DEFENSE for all scoring rules and the Condorcet voting rule (these are natural choices because they are computationally vulnerable to control - - the underlying "attack problem" can be resolved in polynomial time). We show that the problem of finding an optimal defense is tractable when both the attacker and the defender have limited resources. Specifically, we show that the problem is fixed-parameter tractable with the combined parameter (ka, kd) by a natural bounded-depth search tree approach. We also show that the OPTIMAL DEFENSE problem is unlikely to admit a polynomial kernel under plausible complexity theoretic assumption. We observe that both these parameters are needed for fixed parameter tractability, as we show W[2]-hardness when OPTIMAL DEFENSE is parameterized by either ka or kd.

Another popular parameter considered for voting problems is m, the number of candidates - as this is usually small compared to the size of the election in traditional application scenarios. Unfortunately, we show that OPTIMAL DEFENSE is NP-hard even when the election has only 3 candidates, eliminating the possibility of fixed-parameter algorithms (and even XP algorithms). This strengthens a hardness result shown in [Yin et al., 2016]. Our hardness results on a constant number of candidates rely on a succinct encoding of the information about the scores of the candidates from each voter group. We also observe that the problem is polynomially solvable when only two candidates are involved.

We introduce the complementary problem of attacking an election: here the attacker plays her strategy first, and the defender is free to defend any of the attacked groups within the budget. The attacker wins if she is successful in subverting the election no matter which defense is played out. This problem turns out to be harder: it is already W[1]-hard when parameterized by both ka and kd, which is in sharp contrast to the OPTIMAL DEFENSE problem. This problem is also hard in the setting of a constant number of candidates - specifically, it is coNP-hard for the plurality voting rule [Corollary 1] and the Condorcet voting rule [Corollary 2] even when we have only three candidates if every voter group is encoded as the number of plurality votes every candidate receives from that voter group. Our demonstration of the hardness of the attack problem is another step in the program of using computational intractability as a barrier to undesirable phenomenon, which, in this context, is the act of planning a systematic attack on voter groups with limited resources.

We finally propose two simple greedy algorithms for the OPTIMAL DEFENSE problem and empirically show that it may be able to solve many instances of practical interest.

2 Preliminaries

Let C = {c1, c2, . . . , cm} be a set of candidates and V = {v1, v2, . . . , vn} a set of voters. If not mentioned otherwise, we denote the set of candidates by C, the set of voters by V, the number of candidates by m, and the number of voters by n. Every voter vi has a preference or vote ≻i which is a complete order over C. We denote the set of all complete orders over C by L(C). We call a tuple of n preferences (≻1,≻2, · · · ,≻n) ∈ L(C)n an n-voter preference profile. Often it is convenient to view a preference profile as a multi-set consisting of its votes. The view we are taking will be clear from the context. A voting rule (often called voting correspondence) is a function r : ∪n∈NL(C)n -→ 2C \ {∅} which selects, from a preference profile, a nonempty set of candidates as the winners. We refer the reader to [Brandt et al., 2016] for a comprehensive introduction to computational social choice. In this paper we will be focusing on two voting rules - the scoring rules and the Condorcet voting rule which are defined as follows.

2.1 Scoring Rule

A collection of m-dimensional vectors -→ sm = (α1, α2, . . . , αm) ∈ Rm 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 the highest score. Given a set of candidates C, a score vector -→α of length |C|, a candidate x ∈ C, and a profile P, we denote the score of x in P by s-→α P (x). When the score vector -→α is clear from the context, we omit -→α from the superscript. A straight forward observation is that the scoring rules remain unchanged if we multiply every αi by any constant λ > 0 and/or add any constant µ. Hence, we assume without loss of generality that for any score vector -→ sm, there exists a j such that αj - αj+1 = 1 and αk = 0 for all k > j. We call such a score vector a normalized score vector.

2.2 WeightedMajority Graph and Condorcet Voting Rule

Given an election E = (C, (≻1,≻2, . . . ,≻n)) and two candidates x, y ∈ C, let us define NE(x, y) to be the number of votes where the candidate x is preferred over y. We say that a candidate x defeats another candidate y in pairwise election if NE (x, y) > NE (y, x). Using the election E , we can construct a weighted directed graph GE = (U = C, E) as follows. The vertex set U of the graph GE is the set of candidates C. For any two candidates x, y ∈ C with x ̸= y, let us define the margin DE (x, y) of x from y to be NE (x, y) - NE (y, x). We have an edge from x to y in GE if DE(x, y) > 0. Moreover, in that case, the weight w(x, y) of the edge from x to y is DE(x, y). A candidate c is called the Condorcet winner of an election E if there is an edge from c to every other vertices in the weighted majority graph GE. The Condorcet voting rule outputs the Condorcet winner if it exists and outputs the set C of all candidates otherwise.

Let r be a voting rule. We study the r-OPTIMAL DEFENSE problem which was defined by [Yin et al., 2016]. It is defined as follows. Intuitively, the r-OPTIMAL DEFENSE problem asks if there is a way to defend kd voter groups such that, irrespective of which ka voter groups the attacker attacks, the output of the election (that is the winning set of candidates) is always same as the original one. A voter group gets deleted if only if it is attacked but not defended.

Definition 1 (r-OPTIMAL DEFENSE). Given n voter groups Gi, i ∈ [n], two integers ka and kd, does there exist an index set I ⊆ [n] with |I| ⩽ kd such that, for every I ′ ⊂ [n]\I with |I ′ | ⩽ ka, we have r((Gi)i∈[n]\I ′ ) = r((Gi)i∈[n])? The integers ka and kd are called respectively attacker's resource and defender's resource. We denote an arbitrary instance of the r-OPTIMAL DEFENSE problem by (C, {Gi : i ∈ [n]}, ka, kd).

We also study the r-OPTIMAL ATTACK problem which is defined as follows. Intuitively, in the r-OPTIMAL ATTACK problem the attacker is interested to know if it is possible to attack ka voter groups such that, no matter which kd voter groups the defender defends, the outcome of the election is never same as the original (that is the attack is successful).

Definition 2 (r-OPTIMAL ATTACK). Given n voter groups Gi, i ∈ [n], two integers ka and kd, does there exist an index set I ⊆ [n] with |I| ⩽ ka such that, for every I ′ ⊆ [n] with |I ′ | ⩽ kd, we have r((Gi)i∈[n]\(I\I ′ )) ̸= r((Gi)i∈[n])? We denote an arbitrary instance of the r-OPTIMAL ATTACK problem by (C, {Gi : i ∈ [n]}, ka, kd).

Encoding of the Input Instance: In both the r-OPTIMAL DEFENSE and r-OPTIMAL ATTACK problems, we assume that every input voter group G is encoded as follows. The encoding lists all the different votes ≻ that appear in the voter group G along with the number of times the vote ≻ appear in G. Hence, if a voter group G contains only k different votes over m candidates and consists of n voters, then the encoding of G takes O(km log m log n) bits of memory.

2.3 Parameterized complexity

A parameterized problem Π is a subset of Γ∗ ×N, where Γ is a finite alphabet. A central notion is fixed parameter tractability (FPT) which means, for a given instance (x, k), solvability in time f(k) · p(|x|), where f is an arbitrary function of k and p is a polynomial in the input size |x|. There exists a hierarchy of complexity classes above FPT, and showing that a parameterized problem is hard for one of these classes is considered evidence that the problem is unlikely to be fixedparameter tractable. The main classes in this hierarchy are: FPT ⊆ W[1] ⊆ W[2] ⊆ · · · ⊆ W[P] ⊆ XP. We now define the notion of parameterized reduction [Cygan et al., 2015].

Definition 3. Let A,B be parameterized problems. We say that A is fpt-reducible to B if there exist functions f, g : N → N, a constant α ∈ N and an algorithm Φ which transforms an instance (x, k) of A into an instance (x′ , g(k)) of B in time f(k)|x|α so that (x, k) ∈ A if and only if (x′ , g(k)) ∈ B.

To showW-hardness, it is enough to give a parameterized reduction from a known hard problem.

3 Classical Complexity Results

[Yin et al., 2016] showed that the OPTIMAL DEFENSE problem is polynomial time solvable for the plurality voting rule when we have only 2 candidates. On the other hand, they also showed that the OPTIMAL DEFENSE problem is NPcomplete when we have an unbounded number of candidates. We begin with improving their NP-completeness result by showing that the OPTIMAL DEFENSE problem becomes NPcomplete even when we have only 3 candidates and the attacker can attack any number of voter groups. Towards that, we reduce the k-SUM problem to the OPTIMAL DEFENSE problem. The k-SUM problem is defined as follows.

Definition 4 (k-SUM). Given a set of n positive integers W = {wi, i ∈ [n]}, and two positive integers k ⩽ n and M, does there exist an index set I ⊂ [n] with |I| = k such that ∑i∈I wi = M?

The k-SUM problem can be easily proved to be NPcomplete by modifying the NP-completeness proof of the Subset Sum problem in [Cormen et al., 2009]. We also need the following structural result for normalized scoring rules which has been used before [Baumeister et al., 2011; Dey et al., 2016].

Lemma 1. Let C = {c1, . . . , cm} be a set of candidates and -→α a normalized score vector of length |C|. Let x, y ∈ C, x ̸= y, be any two arbitrary candidates. Then there exists a profile P y x consisting of m votes such that we have the following. sP y x (x) + 1 = sP y x (y) - 1 = sP y x (a) for every a ∈ C \ {x, y}

For any two candidates x, y ∈ C, x ̸= y, we use P y x to denote the profile as defined in Lemma 1. We are now ready to present our NP-completeness result for the OPTIMAL DEFENSE problem for the scoring rules even in the presence of 3 candidates only. In the interest of space, we defer proof of some of our results to the full version of this paper [Dey et al., 2019b].

Theorem 1. The OPTIMAL DEFENSE problem is NPcomplete for every scoring rule even if the number of candidates is 3 and the attacker can attack any number of the voter groups.

Proof. For the interest of space, we only prove NP-hardness. Let -→α be any normalized score vector of length 3. The OPTIMAL DEFENSE problem for the scoring rule based on -→α belongs to NP. Let (W = {w1, . . . , wn}, k,M) be an arbitrary instance of the k-SUM problem. We can assume, without loss of generality, that 8 divides M and wi for every i ∈ [n]; if this is not the case, we replace M and wi by respectively 8M and 8wi for every i ∈ [n] which clearly is an equivalent instance of the original instance. Let us also assume, without loss of generality, that 2k < n (if not then add enough copies of M + 1 to W) and M < ∑ni=1 wi (since otherwise, it is a trivial NO instance). We construct the following instance of the OPTIMAL DEFENSE problem for the scoring rule based on -→α . Let M ′ be an integer such that M ′ > ∑ni=1 wi and 8 divides M ′ . We have 3 candidates, namely a, b, and c. We have the following voter groups.

• For every i ∈ [n], we have a voter group Gi consisting of wi copies of P c a (as defined in Lemma 1) and M ′ - wi copies of P c b . Hence, we have the following. sGi (c) = sGi (a) + M ′ + wi = sGi (b) + 2M ′ - wi
• We have one voter group ˆ G consisting of (kM′+M)/2 - 3 copies of P a c , (kM′-M)/2 - 1 copies of P b c , and (kM′-M)/2 - 1 copies of P b a . We have the following. s ˆ G (c) = s ˆ G (a)-(kM ′+M-6) = s ˆ G (b)-(2kM ′-M-6)

Let Q be the resulting profile; that is Q = ∪ni=1Gi ∪ ˆ G. We have sQ(c) = sQ(a) + (n - k)M ′ + ∑ni=1 wi - M + 6 = sQ(b) + (n - 2k)M ′ + M - ∑ni=1 wi + 6. Since n > 2k and M ′ > ∑ni=1 wi, we have sQ(c) > sQ(a) and sQ(c) > sQ(b). Thus the candidate c wins the election uniquely. We define kd, the maximum number of voter groups that the defender can defend, to be k. We define ka, the maximum number of voter groups that the attacker can attack, to be n + 1.

This finishes the description of the OPTIMAL DEFENSE instance. We claim that the two instances are equivalent.

In the forward direction, let the k-SUM instance be a YES instance and I ⊂ [n] with |I| = k be an index set such that ∑i∈I wi = M. Let us consider the defense strategy where the defender protects the voter groups Gi for every i ∈ I. Since ∑i∈I wi = M, we have ∑i∈I (M ′ -wi) = kM ′ -M. Let H be the profile of voter groups corresponding to the index set I; that is, H = ∪i∈IGi. Let H′ be the profile remaining after the attacker attacks some voter groups. Without loss of generality, we can assume that the attacker does not attack the voter group ˆ G since otherwise the candidate c continues to win uniquely. We thus obviously have H∪ ˆ G ⊆ H′ . We have sH∪ ˆ G (c) = sH∪ ˆ G (a)+kM ′ + ∑i∈I wi -(kM ′ +M -6) = sH∪ ˆ G (a)+6 and sH∪ ˆ G (c) = sH∪ ˆ G (b) + 2kM ′ - ∑i∈I wi - (2kM ′ - M - 6) = sH∪ˆ G (b) + 6. Since the candidate c receives as much score as any other candidate in the voter group Gi for every i ∈ [n], we have sH′∪ ˆ G (c) ⩾ sH′∪ ˆ G (a)+6 and sH′∪ ˆ G (c) ⩾ sH′∪ ˆ G (b) + 6. Hence, the candidate c wins uniquely in the resulting profile H′ after the attack and thus the defense is successful.

In the other direction, let the OPTIMAL DEFENSE instance be a YES instance. Without loss of generality, we can assume that the attacker does not attack the voter group ˆ G and thus the defender does not defend the voter group ˆ G. We can also assume, without loss of generality, that the defender defends exactly k voter groups since the candidate c receives as much score as any other candidate in the voter group Gi for every i ∈ [n]. Let I ⊂ [n] with |I| = k such that defending all the voter groups Gi, i ∈ I is a successful defense strategy. We claim that ∑i∈I wi ⩾ M. Suppose not, then let us assume that ∑i∈I wi < M. Since, wi is divisible by 8 and positive for every i ∈ [n] and m is divisible by 8, we have ∑i∈I wi ⩽ M - 8. Let H be the profile of voter groups corresponding to the index set I; that is, H = ∪i∈IGi. We have sH∪ ˆ G (c) = sH∪ ˆ G (a)+kM ′ + ∑i∈I wi -(kM ′ +M -6) ⩽ sH∪ ˆ G (a) + M - 8 - M + 6 = sH∪ˆ G (a) - 2. Hence attacking the voter groups Gi, i ∈ [n] \ I makes the score of c strictly less than the score of a. This contradicts our assumption that defending all the voter groups Gi, i ∈ I is a successful defense strategy. Hence we have ∑i∈I wi ⩾ M. We now claim that ∑i∈I wi ⩽ M. Suppose not, then let us assume that ∑i∈I wi > M. Since, wi is divisible by 8 and positive for every i ∈ [n] and m is divisible by 8, we have ∑i∈I wi ⩾ M +8. Let H′ be the profile of voter groups corresponding to the index set I; that is, H′ = ∪i∈IGi. We have sH′∪ ˆ G (c) = sH′∪ ˆ G (b) + 2kM ′ - ∑i∈I wi - (2kM ′ -M - 6) ⩽ sH′∪ ˆ G (b) - (M + 8) + M + 6 = sH′∪ ˆ G (b) - 2. Hence attacking the voter groups Gi, i ∈ [n] \ I makes the score of c strictly less than the score of b. This contradicts our assumption that defending all the voter groups Gi, i ∈ I is a successful defense strategy. Hence we have ∑i∈I wi ⩽ M. Therefore we have ∑i∈I wi = M and thus the k-SUM instance is a YES instance.

In the proof of Theorem 1, we observe that the reduced instance of the OPTIMAL DEFENSE problem viewed as an instance of the OPTIMAL ATTACK problem is a NO instance if and only if the k-SUM instance is a YES instance. Hence, the same reduction as in the proof of Theorem 1 gives us the following result for the OPTIMAL ATTACK problem.

Corollary 1. The OPTIMAL ATTACK problem is coNP-hard for every scoring rule even if the number of candidates is 3 and the attacker can attack any number of voter groups.

We now prove a similar hardness result as of Theorem 1 for the Condorcet voting rule.

Theorem 2. The OPTIMAL DEFENSE problem is NPcomplete for the Condorcet voting rule even if the number of candidates is 3 and the attacker can attack any number of voter groups.

In the proof of Theorem 2, we observe that the reduced instance of OPTIMAL DEFENSE viewed as an instance of the OPTIMAL ATTACK problem is a NO instance if and only if the k-SUM instance is a YES instance. Hence, the same reduction as in the proof of Theorem 2 gives us the following result for the OPTIMAL ATTACK problem.

Corollary 2. The OPTIMAL ATTACK problem is coNP-hard for the Condorcet voting rule even if the number of candidates is 3 and the attacker can attack any number of voter groups.

4 W-Hardness Results

In this section, we present our hardness results for the OPTIMAL DEFENSE and the OPTIMAL ATTACK problems in the parameterized complexity framework. We consider the following parameters for both the problems - number of candidate (m), defender's resource (kd), and attacker's resource (ka). From Theorems 1 and 2 and Corollaries 1 and 2 we immediately have the following result for the OPTIMAL DEFENSE and OPTIMAL ATTACK problems parameterized by the number of candidates for both the scoring rules and the Condorcet voting rule.

Corollary 3. The OPTIMAL DEFENSE problem is para-NPhard parameterized by the number of candidates for both the scoring rules and the Condorcet voting rule. The OPTIMAL ATTACK problem is para-coNP-hard parameterized by the number of candidates for both the scoring rules and the Condorcet voting rule.

The NP-completeness proof for the OPTIMAL DEFENSE problem for the plurality voting rule by [Yin et al., 2016] is actually a parameter preserving reduction from the HITTING SET problem parameterized by the solution size.

Since the HITTING SET problem parameterized by the solution size k is known to be W[2]-complete [Downey and Fellows, 1999], the following result immediately follows from Theorem 2 of [Yin et al., 2016].

Observation 1 ([Yin et al., 2016]). The OPTIMAL DEFENSE problem for the plurality voting rule is W[2]-hard parameterized by kd.

We now generalize Observation 1 to any scoring rule by exhibiting a polynomial parameter transform from the HITTING SET problem parameterized by the solution size.

Theorem 3. The OPTIMAL DEFENSE and OPTIMAL ATTACK problems for every scoring rule is W[2]-hard parameterized by kd.

Next, we show the W[2]-hardness of the OPTIMAL DEFENSE and OPTIMAL ATTACK problems for the Condorcet voting rule parameterized by kd. This is also a parameterpreserving reduction from the HITTING SET problem.

Theorem 4. The OPTIMAL DEFENSE and OPTIMAL ATTACK problems for the Condorcet voting rule is W[2]-hard parameterized by kd.

We now show that the OPTIMAL DEFENSE problem for scoring rules is W[2]-hard parameterized by ka also by exhibiting a parameter preserving reduction from a problem closely related to HITTING SET, which is SET COVER problem parameterized by the solution size. This is a W[2]- complete problem [Downey and Fellows, 1999]. We now state our W[2]-hardness proof for the OPTIMAL DEFENSE problem for scoring rules and the Condorcet voting rule, parameterized by ka, by a reduction from SET COVER.

Theorem 5. The OPTIMAL DEFENSE problem for every scoring rule and Condorcet rule is W[2]-hard parameterized by ka.

We now show that the OPTIMAL ATTACK problem for the scoring rules is W[1]-hard even parameterized by the combined parameter ka and kd. Towards that, we exhibit a polynomial parameter transform from the CLIQUE problem parameterized by the size of the clique we are looking for which is known to be W[1]-complete.

Theorem6. The OPTIMAL ATTACK problem for every scoring rule and Condorcet rule is W[1]-hard parameterized by (ka, kd).

Once we have a parameterized algorithm for the OPTIMAL DEFENSE problem for the parameter (ka, kd), an immediate question is whether there exists a kernel for the OPTIMAL DEFENSE problem of size polynomial in (ka, kd). We know that the HITTING SET problem does not admit polynomial kernel parameterized by the universe size [Downey and Fellows, 1999]. It turns out that the reductions from the HITTING SET problem to the OPTIMAL DEFENSE and OPTIMAL ATTACK problems in Theorems 3, 4 and 6 are polynomial parameter transformations. Hence we immediately have the following corollary.

Corollary 4. The OPTIMAL DEFENSE and OPTIMAL ATTACK problems for the scoring rules and the Condorcet rule do not admit a polynomial kernel parameterized by (ka, kd).

5 The FPT Algorithm

We complement the negative results of Observation 1 and Theorem 5 by presenting an FPT algorithm for the OPTIMAL DEFENSE problem parameterized by (ka, kd). In the absence of a defender, that is when kd = 0, [Yin et al., 2016] showed that the OPTIMAL DEFENSE problem is polynomial time solvable for the plurality voting rule. Their polynomial time algorithm for the OPTIMAL DEFENSE problem can easily be extended to any scoring rule. Using this polynomial time algorithm, we design the following O∗ (kkd a ) time algorithm for the OPTIMAL DEFENSE problem for scoring rules.

Theorem 7. There is an algorithm for the OPTIMAL DEFENSE problem for every scoring rule and the Condorcet voting rule which runs in time O∗ (kkd a ).

6 Experiments

Though the previous sections show that the optimal defending problem is computationally intractable, it is a worst-case result. In practice, elections have voting profiles that are generated from some (possibly known) distribution. In this section, we conduct an empirical study to understand how simple defending strategies perform for two such statistical voter generation models. The defending strategies we consider are variants of a simple greedy policy.

6.1 Defending Strategy

For a given voting profile and a voting rule, the defending strategy finds the winner. Suppose the winner is a. The strategy considers a with every other candidate, and for each such pair it creates a sorted list of classes based on the winning margin of votes for a in those classes, and picks the top kd classes to form a sub-list. Now, among all these (m- 1) sorted sub-lists, the strategy picks the most frequent kd classes to protect. We call this version of the strategy GREEDY 1. For certain profiles an optimal attacker (a) may change the outcome by attacking some of the unprotected classes or (b) is unable to change the outcome. If (a) occurs, then there is a possibility that for the value of kd there does not exist any defense strategy which can guard the election from all possible strategies of the attacker. In that case, GREEDY 1 is optimal and is not optimal otherwise. It is always optimal for case (b). Note that, given a profile and kd protected classes, it is easy to find if there exists an optimal attack strategy, while it is not so easy to identify whether there does not exist any defending strategy if the GREEDY 1 fails to defend. We find the latter with a brute-force search for this experiment. A small variant of GREEDY 1 is the following: when GREEDY 1 is unable to defend (which is possible to find out in poly-time), the strategy chooses to protect kd classes uniformly at random. Call this strategy GREEDY 2.

6.2 Voting Profile Generation

Fix m = 5. We generate 1000 preference profiles over these alternatives for n = 12000, where each vote is picked uniformly at random from the set of all possible strict preference orders over m alternatives. The voters are partitioned into 12 classes containing equal number of voters. We consider three voting rules: plurality, veto, and Borda. The lower plot in Figure 1 shows the number of profiles which belongs to the three categories: (i) GREEDY 1 defends (is optimal), (ii) GREEDY 1 cannot defend but no defending strategy exists (is optimal), (iii) GREEDY 1 cannot defend but defending strategy exists (not optimal). The x-axis shows different values of kd and we fix ka = 12 - kd.

The upper plot of Figure 1 shows the fraction of the profiles successfully defended by GREEDY 2 where GREEDY 1 is not optimal (i.e., cannot defend but defending strategy exists) when GREEDY 2 uniformly at random picks kd classes 100 times. These fractions therefore serves as an empirical probability of successful defense of GREEDY 2 given GREEDY 1 is not optimal.

In an election where the primary contest happens between two major candidates, even though there are more candidates present, the generation model may be a little different. We also consider another generation model that generates 40% profiles having a fixed alternative a on top and the strict order of the (m - 1) alternatives is picked uniformly at random, a similar 40% profiles with some other alternative b on top, and the remaining 20% preferences are picked uniformly at random from the set of all possible strict preference orders. Similar experiments are run on this generation model and results are shown in Figure 2.

The results show that even though optimal defense is a hard problem, a simple strategy like greedy achieves more than 70% optimality. From the rest 30% non-optimal cases, the variant GREEDY 2 is capable of salvaging it into optimal with probability almost 5% for uniform generation model and above 5% for two-major contestant generation model for kd = ka = 6. This empirically hints at a possibility that defending real elections may not be too difficult.