# a_parameterized_perspective_on_protecting_elections__bdde5898.pdf

A Parameterized Perspective on Protecting Elections

Palash Dey1 , Neeldhara Misra2 , Swaprava Nath3 and Garima Shakya3

1Indian Institute of Technology, Kharagpur, India 2Indian Institute of Technology, Gandhinagar, India 3Indian Institute of Technology, Kanpur, India palash.dey@cse.iitkgp.ac.in, neeldhara.m@iitgn.ac.in, {swaprava, garima}@cse.iitk.ac.in

We study the parameterized complexity of the optimal defense and optimal attack problems in voting. In both the problems, the input is a set of voter groups (every voter group is a set of votes) and two integers ka and kd corresponding to respectively the number of voter groups the attacker can attack and the number of voter groups the defender can defend. A voter group gets removed from the election if it is attacked but not defended. In the optimal defense problem, we want to know if it is possible for the defender to commit to a strategy of defending at most kd voter groups such that, no matter which ka voter groups the attacker attacks, the outcome of the election does not change. In the optimal attack problem, we want to know if it is possible for the attacker to commit to a strategy of attacking ka voter groups such that, no matter which kd voter groups the defender defends, the outcome of the election is always different from the original (without any attack) one. We show that both the optimal defense problem and the optimal attack problem are computationally intractable for every scoring rule and the Condorcet voting rule even when we have only 3 candidates. We also show that the optimal defense problem for every scoring rule and the Condorcet voting rule is W[2]-hard for both the parameters ka and kd, while it admits a ﬁxed parameter tractable algorithm parameterized by the combined parameter (ka, kd). The optimal attack problem for every scoring rule and the Condorcet voting rule turns out to be much harder it is W[1]- hard even for the combined parameter (ka, kd). We propose two greedy algorithms for the OPTIMAL DEFENSE problem and empirically show that they perform effectively on reasonable voting proﬁles.

1 Introduction The problem of election control asks if it is possible for an external agent, usually with a ﬁxed set of resources, to inﬂuence the outcome of the election by altering its structure in some limited way. There are several speciﬁc manifestations of this problem: for instance, one may ask if it is pos-

sible 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, stufﬁng 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 efﬁcient

Proceedings of the Twenty-Eighth International Joint Conference on Artiﬁcial Intelligence (IJCAI-19)

Parameters OPTIMAL DEFENSE OPTIMAL ATTACK Scoring rules Condorcet Scoring rules Condorcet kd W[2]-hard [Theorem 3] W[2]-hard [Theorem 4] W[2]-hard [Theorem 3] W[2]-hard [Theorem 4] ka W[2]-hard [Theorem 5] W[2]-hard [Theorem 5]

W[1]-hard [Theorem 6] W[1]-hard [Theorem 6] (ka, kd) O (kkd a ) [Theorem 7] No poly kernel [Corollary 4] m para-NP-hard [Corollary 3] para-co NP-hard [Corollary 3]

Table 1: Summary of parameterized complexity results. kd : the maximum number of voter groups that the defender can defend. ka : the maximum number of voter groups that the attacker can attack. m : the number of candidates.

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 deﬁned 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 deﬁned 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 efﬁciently tackled by solvers. Our main contribution is to study this problem in a parameterized setting and provide a reﬁned 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 deﬁnitions, 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 ﬁnding an optimal defense is tractable when both the attacker and the defender have limited resources. Speciﬁcally, we show that the problem is ﬁxed-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 ﬁxed 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 ﬁxed-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 ﬁrst, 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 co NP-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 ﬁnally 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 proﬁle. Often it is convenient to view a preference proﬁle as a multi-set consisting of its votes. The view we are taking will

Proceedings of the Twenty-Eighth International Joint Conference on Artiﬁcial Intelligence (IJCAI-19)

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 proﬁle, 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 deﬁned 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 deﬁnes 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 proﬁle 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 Weighted Majority Graph and Condorcet Voting Rule Given an election E = (C, ( 1, 2, . . . , n)) and two candidates x, y C, let us deﬁne 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 deﬁne 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 deﬁned by [Yin et al., 2016]. It is deﬁned 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. Deﬁnition 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 deﬁned 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). Deﬁnition 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 ﬁnite alphabet. A central notion is ﬁxed 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 ﬁxedparameter tractable. The main classes in this hierarchy are: FPT W[1] W[2] W[P] XP. We now deﬁne the notion of parameterized reduction [Cygan et al., 2015]. Deﬁnition 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 show W-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 deﬁned as follows. Deﬁnition 4 (k-SUM). Given a set of n positive integers W = {wi, i [n]}, and two positive integers k n and

Proceedings of the Twenty-Eighth International Joint Conference on Artiﬁcial Intelligence (IJCAI-19)

M, does there exist an index set I [n] with |I| = k such that P 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 proﬁle Py x consisting of m votes such that we have the following. s Py x(x) + 1 = s Py x(y) 1 = s Py x(a) for every a C \ {x, y}

For any two candidates x, y C, x = y, we use Py x to denote the proﬁle as deﬁned 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 < Pn i=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 > Pn i=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 Pc a (as deﬁned in Lemma 1) and M wi copies of Pc b. Hence, we have the following. s Gi(c) = s Gi(a) + M + wi = s Gi(b) + 2M wi We have one voter group ˆG consisting of (k M +M)/2 3 copies of Pa c , (k M M)/2 1 copies of Pb c, and (k M M)/2 1 copies of Pb a. We have the following. s ˆG(c) = s ˆG(a) (k M +M 6) = s ˆG(b) (2k M M 6)

Let Q be the resulting proﬁle; that is Q = n i=1Gi ˆG. We have s Q(c) = s Q(a) + (n k)M + Pn i=1 wi M + 6 = s Q(b) + (n 2k)M + M Pn i=1 wi + 6. Since n > 2k and M > Pn i=1 wi, we have s Q(c) > s Q(a) and s Q(c) > s Q(b). Thus the candidate c wins the election uniquely. We deﬁne kd, the maximum number of voter groups that the defender can defend, to be k. We deﬁne ka, the maximum number of voter groups that the attacker can attack, to be n + 1.

This ﬁnishes 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 P i I wi = M. Let us consider the defense strategy where the defender protects the voter groups Gi for every i I. Since P i I wi = M, we have P i I(M wi) = k M M. Let H be the proﬁle of voter groups corresponding to the index set I; that is, H = i IGi. Let H be the proﬁle 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 s H ˆG(c) = s H ˆG(a)+k M +P i I wi (k M +M 6) = s H ˆG(a)+6 and s H ˆG(c) = s H ˆG(b)+2k M P i I wi (2k M M 6) = s H ˆ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 s H ˆG(c) s H ˆG(a)+6 and s H ˆG(c) s H ˆG(b) + 6. Hence, the candidate c wins uniquely in the resulting proﬁle 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 P i I wi M. Suppose not, then let us assume that P i I wi < M. Since, wi is divisible by 8 and positive for every i [n] and m is divisible by 8, we have P i I wi M 8. Let H be the proﬁle of voter groups corresponding to the index set I; that is, H = i IGi. We have s H ˆG(c) = s H ˆG(a)+k M +P i I wi (k M +M 6) s H ˆG(a) + M 8 M + 6 = s H ˆ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 P i I wi M. We now claim that P i I wi M. Suppose not, then let us assume that P i I wi > M. Since, wi is divisible by 8 and positive for every i [n] and m is divisible by 8, we have P i I wi M +8. Let H be the proﬁle of voter groups corresponding to the index set I; that is, H = i IGi. We have s H ˆG(c) = s H ˆG(b) + 2k M P i I wi (2k M M 6) s H ˆG(b) (M + 8) + M + 6 = s H ˆ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 P i I wi M. Therefore we have P 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

Proceedings of the Twenty-Eighth International Joint Conference on Artiﬁcial Intelligence (IJCAI-19)

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 co NP-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 co NP-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-co NP-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. Theorem 6. 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.

Proceedings of the Twenty-Eighth International Joint Conference on Artiﬁcial Intelligence (IJCAI-19)

P P P P P P P

V V V V V V V

B B B B B B B

B Plurality Veto Borda

2 3 4 5 6 7 8 9 10 kd

optimal and defended optimal but not defended not optimal

Figure 1: Performances of GREEDY 1 and GREEDY 2 for uniform voting proﬁle generation model.

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 proﬁles 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 proﬁle and a voting rule, the defending strategy ﬁnds 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 proﬁles 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 proﬁle and kd protected classes, it is easy to ﬁnd 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 ﬁnd 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 ﬁnd out in poly-time), the strategy chooses to protect kd classes uniformly at random. Call this strategy GREEDY 2.

P P P P P P

V V V V V V

B B B B B B

B Plurality Veto Borda

2 3 4 5 6 7 8 9 10 kd

optimal and defended optimal but not defended not optimal

Figure 2: Performances of GREEDY 1 and GREEDY 2 for voting proﬁle generation model with two major contesting candidates.

6.2 Voting Proﬁle Generation Fix m = 5. We generate 1000 preference proﬁles 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 proﬁles 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 ﬁx ka = 12 kd. The upper plot of Figure 1 shows the fraction of the proﬁles 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% proﬁles having a ﬁxed alternative a on top and the strict order of the (m 1) alternatives is picked uniformly at random, a similar 40% proﬁles 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 difﬁcult.

Proceedings of the Twenty-Eighth International Joint Conference on Artiﬁcial Intelligence (IJCAI-19)

References [An et al., 2013] Bo An, Matthew Brown, Yevgeniy Vorobeychik, and Milind Tambe. Security games with surveillance cost and optimal timing of attack execution. In International conference on Autonomous Agents and Multi-Agent Systems, AAMAS 13, Saint Paul, MN, USA, May 6-10, 2013, pages 223 230, 2013. [Bartholdi et al., 1992] John J. Bartholdi, Craig A. Tovey, and Michael A. Trick. How hard is it to control an election? Mathematical and Computer Modelling, 16(8):27 40, 1992. [Baumeister et al., 2011] Dorothea Baumeister, Magnus Roos, and J org Rothe. Computational complexity of two variants of the possible winner problem. In The 10th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pages 853 860, 2011. [Betzler and Uhlmann, 2009] Nadja Betzler and Johannes Uhlmann. Parameterized complexity of candidate control in elections and related digraph problems. Theor. Comput. Sci., 410(52):5425 5442, 2009. [Bhattacharjya, 2010] Satarupa Bhattacharjya. Low turnout and invalid votes mark ﬁrst post war general polls. http://www. sundaytimes.lk/100411/News/nws 16.html, 2010. [Brandt et al., 2016] Felix Brandt, Vincent Conitzer, Ulle Endriss, J erˆome Lang, and Ariel Procaccia. Handbook of computational social choice, 2016. [Cormen et al., 2009] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Third Edition. The MIT Press, 3rd edition, 2009. [Cygan et al., 2015] Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, D aniel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. [Dey and Misra, 2017] Palash Dey and Neeldhara Misra. On the exact amount of missing information that makes ﬁnding possible winners hard. In Proc. 42nd International Symposium on Mathematical Foundations of Computer Science, MFCS, pages 57:1 57:14, 2017. [Dey et al., 2015] Palash Dey, Neeldhara Misra, and Y. Narahari. Detecting possible manipulators in elections. In Proc. International Conference on Autonomous Agents and Multiagent Systems, AAMAS, pages 1441 1450, 2015. [Dey et al., 2016] Palash Dey, Neeldhara Misra, and Y. Narahari. Kernelization complexity of possible winner and coalitional manipulation problems in voting. Theor. Comput. Sci., 616:111 125, 2016. [Dey et al., 2017] Palash Dey, Neeldhara Misra, and Y. Narahari. Frugal bribery in voting. Theor. Comput. Sci., 676:15 32, 2017. [Dey et al., 2018] Palash Dey, Neeldhara Misra, and Y. Narahari. Complexity of manipulation with partial information in voting. Theor. Comput. Sci., 726:78 99, 2018. [Dey et al., 2019a] Palash Dey, Neeldhara Misra, and Y. Narahari. Parameterized dichotomy of choosing committees based on approval votes in the presence of outliers. Theor. Comput. Sci., 2019. [Dey et al., 2019b] Palash Dey, Neeldhara Misra, Swaprava Nath, and Garima Shakya. A parameterized perspective on protecting elections. Co RR, abs/1905.11838, 2019. [Dey, 2018] Palash Dey. Manipulative elicitation - A new attack on elections with incomplete preferences. Theor. Comput. Sci., 731:36 49, 2018.

[Dey, 2019] Palash Dey. Local distance restricted bribery in voting. In Proc. 18th International Conference on Autonomous Agents and Multi Agent Systems, AAMAS, pages 1925 1927, 2019. [Downey and Fellows, 1999] Rod G Downey and Michael Ralph Fellows. Parameterized Complexity, volume 3. springer Heidelberg, 1999. [Faliszewski et al., 2011] Piotr Faliszewski, Edith Hemaspaandra, and Lane A. Hemaspaandra. Multimode control attacks on elections. J. Artif. Intell. Res. (JAIR), 40:305 351, 2011. [Hal, 2010] Alex halderman strengthens democracy using software, Popular Science, http://www.popsci.com/brilliant-10-alexhalderman-strengthens-democracy-using-software, 2010. [Letchford et al., 2009] Joshua Letchford, Vincent Conitzer, and Kamesh Munagala. Learning and approximating the optimal strategy to commit to. In Algorithmic Game Theory, Second International Symposium, SAGT 2009, Paphos, Cyprus, October 18-20, 2009. Proceedings, pages 250 262, 2009. [Liu and Zhu, 2010] Hong Liu and Daming Zhu. Parameterized complexity of control problems in maximin election. Inf. Process. Lett., 110(10):383 388, 2010. [Liu and Zhu, 2013] Hong Liu and Daming Zhu. Parameterized complexity of control by voter selection in maximin, copeland, borda, bucklin, and approval election systems. Theor. Comput. Sci., 498:115 123, 2013. [Mattei et al., 2014] Nicholas Mattei, Nina Narodytska, and Toby Walsh. How hard is it to control an election by breaking ties? In Torsten Schaub, Gerhard Friedrich, and Barry O Sullivan, editors, ECAI, volume 263 of Frontiers in Artiﬁcial Intelligence and Applications, pages 1067 1068. IOS Press, 2014. [RT, 2013] Election day bombings sweep pakistan: Over 30 killed, more than 200 injured. https://www.rt.com/news/ pakistan-election-day-bombing-136, 2013. [Wolchok et al., 2012] Scott Wolchok, Eric Wustrow, Dawn Isabel, and J. Alex Halderman. Attacking the washington, D.C. internet voting system. In Financial Cryptography and Data Security - 16th International Conference, FC 2012, Kralendijk, Bonaire, Februray 27-March 2, 2012, Revised Selected Papers, pages 114 128, 2012. [Yin et al., 2016] Yue Yin, Yevgeniy Vorobeychik, Bo An, and Noam Hazon. Optimally protecting elections. In Proc. Twenty Fifth International Joint Conference on Artiﬁcial Intelligence, IJCAI 2016, New York, NY, USA, 9-15 July 2016, pages 538 545, 2016.

Proceedings of the Twenty-Eighth International Joint Conference on Artiﬁcial Intelligence (IJCAI-19)