Closing the gap of control complexity in Borda elections: Solving ten open cases Marc Neveling and Jörg Rothe Institut für Informatik Heinrich-Heine-Universität Düsseldorf 40225 Düesseldorf, Germany {neveling, rothe}@cs.uni-duesseldorf.de Abstract. We consider the problem of control in elections where an election chair seeks to either make a designated candidate win, or prevent her from win- ning, via actions such as adding, deleting, or partitioning either candidates or voters. These scenarios have been studied for many voting systems and the re- lated control problems have been classified in terms of their complexity. How- ever, for one of the most prominent natural voting systems, the Borda Count, complexity results are known for only half of these cases. We settle the complex- ity for ten missing cases in the unique-winner model, leaving just one case open. We also show that Borda is vulnerable to control for this one open case in the nonunique-winner model. An interesting consequence is that Borda is vulnera- ble to another type of control in the nonunique-winner model, yet it is resistant to it in the unique-winner model. This is one of the few known cases where the complexity of control problems differs depending on the winner model chosen. Keywords: Computational social choice, voting, control, Borda election 1 Introduction Much work has been done in computational social choice to show that complexity can help to protect election outcomes from being tampered with by manipulation, control, and bribery attacks. For a comprehensive overview of related results, we refer to the book chapters by Conitzer and Walsh [5], Faliszewski and Rothe [11], and Baumeister and Rothe [3]. Here, we focus on the standard control scenarios in elections—including adding, deleting, or partitioning either candidates or voters—introduced by Bartholdi et al. [2] and Hemaspaandra et al. [16].1 In particular, Bartholdi et al. [2] defined con- structive control scenarios where an election chair seeks to make a given candidate win an election, while Hemaspaandra et al. [16] introduced the corresponding destructive control scenarios where the chair seeks to ensure that a given candidate does not win. Each of these scenarios has been thoroughly discussed in the literature (for ex- ample, in the book chapters mentioned above), and motivating real-world applications 1 To take certain restrictions (e.g., geographical constraints) into account, other models of con- trol have been proposed and studied by Puppe and Tasnádi [27], Erdélyi et al. [8], Lewenberg and Lev [21], and Bachrach et al. [1]. C CRPC-TE D CRPC-TP C CPC-TE C CPV-TE C CPC-TP C CPV-TP C CAUC C CDV C CDC D CAC D CAV control type D D D D D D D D C C C Borda R† V‡ R$ V£ R❄ V£ R♣ V♮ R◦ ? R♦ V¶ R△ R R§ V§ R♠ V§ R♥ V§ R⊕ R⊗ Table 1: Control complexity in Borda elections (unique-winner model), with standard notation of control types [3, 11]. “R” means resistance, “V” vulnerability, and “?” indi- cates an open question. New results are in boldface: Thm. 1 (†), Thm. 2 (‡), Thm. 3 (♦; alternative proof of a result by Neveling and Rothe [25] that can be used to show Thm. 4 as well), Thm. 4 (♣), Thm. 5 (♮), Cor. 1 (¶), Thm. 6 (), Thm. 8 (◦), Cor. 3 (△), Thm. 9 (⊕), and Thm. 10 (⊗). Previously known results are grey and due to Russel [28] (marked by §), Elkind et al. [6] ($), Loreggia et al. [22] (£), Chen et al. [4] (❄), and Neveling and Rothe [25] (marked by ♠—this result also follows from a dichotomy result of Hemaspaandra and Schnoor [20]—, ♥, and ♦). have been presented for each scenario. While they have been studied intensively for many voting systems, such as for plurality, Condorcet, approval [2, 16], Copeland [10], Bucklin [7], Schulze [26], certain variants of approval and range voting [9, 24], and veto [23], one of the most prominent natural voting systems, the Borda Count, is still heavily underexplored. The purpose of this paper is to fill this gap. The eleven results previously known for control in Borda are due to Russel [28], Elkind et al. [6], Loreggia et al. [22], Chen et al. [4], and Neveling and Rothe [25]. Table 1 presents an overview of their results (marked in grey) and of our ten new results (marked in boldface). In this table, an “R” stands for resistance (which in Section 2 is defined as NP-hardness of the corresponding control problem) and “V” stands for vulnerability (which in Section 2 is defined as polynomial-time solvability of the cor- responding control problem). Further, we use the standard names of the control prob- lems that correspond to the standard control scenarios (see, e.g., [3, 11]). For example, CCDC stands for “constructive control by deleting candidates” and DCDC denotes the destructive variant of this problem. Each control problem for which we provide a new result in Borda elections will be formally defined in Sections 3 and 4, and the unique-winner versus the nonunique-winner model will be discussed in Section 2. As Table 1 shows, Borda is now known to be resistant to every standard type of constructive control, whereas it is vulnerable to most of the destructive control types (resistance is known only for destructive control by run-off partition of candidates and by partition of voters, both in the so-called “ties-promote” (TP) model formally defined in Section 3). One case of destructive candidate control remains open (namely, DCPC- TP, marked by “?” in Table 1) in the unique-winner model. Interestingly, we can show Borda to be vulnerable to this control type in the nonunique-winner model (Theorem 7). Even more interesting is a consequence of this result (Corollary 2): In the nonunique- winner model, Borda-DCRPC-TP (which is known to coincide with Borda-DCPC-TP in the nonunique-winner model [15] but not to coincide with it in the unique-winner model) is in P as well, yet it is NP-hard in the unique-winner model (Theorem 6). 2 Preliminaries An election is a pair (C,V ) that contains a set C of candidates and a list V of votes describing the voters’ preferences—as linear orders—over the candidates. We will rep- resent a vote over C as a string that ranks the candidates from left (most preferred) to right (least preferred); for example, if C = {a, b, c, d}, a vote c d b a means that this voter prefers c to d, d to b, and b to a. A voting rule determines a set of winners from each given election. Positional scoring rules are an important class of such rules, and among those we will only consider the perhaps most prominent one, the Borda Count, which works as follows: Given m candidates, every candidate in position i of the voters’ rankings scores m − i points, and all candidates scoring the most points win. Let score(C,V ) (x) denote the number of points candidate x obtains in a Borda election (C,V ), and let dist(C,V ) (x, y) = score(C,V ) (x) − score(C,V ) (y). For a subset X ⊆ C of → − candidates, X in a vote denotes a ranking of these candidates in an arbitrary but fixed ←− order, and X denotes their ranking in reverse order. The control types considered here will be formally defined in Sections 3 and 4, and we refer to the book chapters by Faliszewski and Rothe [11] and Baumeister and Rothe [3] (and to the references therein) for all other standard control types and for real-world scenarios that motivate them. A voting rule is said to be susceptible to a type of control (e.g., constructive control by adding candidates) if there is some election for which the chair can reach her goal (e.g., turning a nonwinning candidate into a winner) by exerting this type of control. If a voting rule is not susceptible to a control type, it is said to be immune to it. Borda is susceptible to each standard control type, in particular to those considered here. A voting system that is susceptible to some type of control is said to be vulnerable to it if the associated control problem can be solved in polynomial time, and it is said to be resistant to it if the associated control problem is NP-hard. Our control problems will be defined in Sections 3 and 4 in the unique-winner model (see also Table 1). That is, a constructive (destructive) control action is viewed as being successful only if the designated candidate can be made a unique winner (not a unique winner) by this action. We note, however, that using essentially the same constructions and slightly modifying the arguments in our proofs, most of our results also work in the nonunique-winner model, which means that for a constructive (destructive) control action to be successful, it is enough to make the designated candidate only a winner (she can be made not even a winner) by this action. The only exception is destructive control by run-off partition of candidates in the ties-promote model (to be defined in Section 3) to which Borda will be shown resistant in the unique-winner model (Theorem 6), yet vulnerable in the nonunique-winner model (Corollary 2).2 In our proofs, we will sometimes use the following result due to Hemaspaandra et al. [15] (see their technical report [14] for the proof of Fact 1), which shows that some of the destructive control cases (to be defined in the next section) can collapse depending on the chosen winner model. 2 Our only other result explicitly shown in the nonunique-winner model is Theorem 7: Borda is vulnerable to destructive control by partition of candidates in the ties-promote model. The corresponding case in the unique-winner model is still open (again, see Table 1). Fact 1 (Hemaspaandra et al. [15]) DCRPC-TE = DCPC-TE in the unique-winner model and DCRPC-TE = DCPC-TE and DCRPC-TP = DCPC-TP in the nonunique- winner model. 3 Candidate control for Borda We solve all open problems for candidate control in Borda elections except one, starting with constructive control by adding an unlimited number of candidates. Borda-CCAUC and Borda-DCAUC. Elkind et al. [6] showed that Borda is resistant to constructive control by adding a limited number of candidates (i.e., a bound k on the number of candidates that may be added is part of the problem instance), and Loreggia et al. [22] showed that Borda is vulnerable to the destructive variant of this control type (see Table 1). Originally, however, Bartholdi et al. [2] defined control by adding candidates in an unlimited variant where no such bound is given. The definition of the limited variant is due to Faliszewski et al. [10], who also proved that the two variants of the problem can have different complexity: Two special cases of Copelandα elections (namely, Copeland0 and Copeland1, the latter a.k.a. Llull elections) are resistant to the constructive, limited variant (the corresponding problem denoted by CCAC), whereas they are vulnerable to the constructive, unlimited variant, which we define below. In the problem Borda-C ONSTRUCTIVE -C ONTROL - BY-A DDING - AN -U NLIMITED - N UMBER - OF -C ANDIDATES (Borda-CCAUC) we ask, given a set C of candidates, an additional set A of candidates, C ∩ A = 0,/ a set V of voters with preferences over C ∪ A, and a distinguished candidate p ∈ C, whether there is a subset A′ ⊆ A such that p is the unique Borda winner of (C ∪ A′ ,V ).3 The proof of Theorem 1 makes use of a reduction from X3C to Borda-CCAUC. First, Lemma 1 below, which was proven by Elkind et al. [6, Lemma B.3],4 allows us to construct votes conveniently. Lemma 1 (Elkind et al. [6]). Let C = {c1 , . . . , c2t−1 , d}, t ≥ 2, be a set of candidates and let A = {a1 , . . . , as } be a set of spoiler candidates. Let L = 2t − 1. Then there is a polynomial-time computable preference profile R = (R1 , . . . , R2L ) over C ∪ A such that for each A′ ⊆ A the Borda scores in the election (C ∪ A′ , R ) are as follows: (a) For each ci ∈ C, score(ci ) = L(2|A′ | + |C| − 1) + 1; (b) score(d) = L(2|A′ | + |C| − 1) − L; and (c) for each ai ∈ A′ , score(ai ) ≤ L(2|A′ | + |C| − 1) − 2L. Theorem 1. Borda is resistant to constructive control by adding an unlimited number of candidates. Proof. Membership of Borda-CCAUC in NP is obvious. To show NP-hardness, we provide a reduction from X3C to Borda-CCAUC. Let (X, S ) be a given X3C instance 3 For convenience, whenever we have a list V of votes over a set C ∪ A and then consider an election with fewer candidates, C ∪ A′ with A′ ⊂ A, we use (C ∪ A′ ,V ) to denote the election with the votes in V tacitly assumed to be restricted to C ∪ A′ . 4 The original lemma by Elkind et al. [6] is slightly more general in that they consider nonneg- 2t−1 ative integers ℓ1 , . . . , ℓ2t−1 with L = ∑i=1 ℓi . For our purpose, it is enough to set ℓ1 = · · · = ℓ2t−1 = 1, so L = 2t − 1. with X = {x1 , . . . , xm }, m = 3k, k > 1, and S = {S1, . . . , Sn } with Si ⊆ X and |Si | = 3 for each i, 1 ≤ i ≤ n. Without loss of generality, we assume that k is even and k > 2 (this can be achieved by duplicating the instance if necessary). Construct from (X, S ) a Borda-CCAUC instance ((C,V ), p, k) as follows. Let C = X ∪ {u, p} with p being the distinguished candidate and A = {a1 , . . . , an } a set of spoiler candidates. Define V to consist of the following votes: → − −−−→ ←−−− ← − 1. For each i, 1 ≤ i ≤ n, there are two votes: Si u p X \ Si A and X \ Si p u ai Si A\ {ai }. → − − → ← − ← − 2. Three times, there are two votes of the form u A p X and X p u A . 3. All votes we obtain by applying Lemma 1 to the candidate set C with each xi taking the role of a ci , p that of c3k+1 , and u that of d. (Here, we need k to be even.) Note that p ranks ahead of every a j ∈ A′ in all but three votes in the second group of voters. The point deficit from those three votes is always offset by the other votes in this group, so we can disregard the points of every a j ∈ A′ from now on, since p always defeats them. For the point differences of p to the other candidates in the election (C ∪ A′ ,V ) for any A′ ⊆ A, we have dist(p, u) = 3k + 2 − 3|A′ | and dist(p, xi ) = |{a j ∈ A′ | xi ∈ S j }|. If A′ = 0, / we have dist(p, xi ) = 0, so p is not winning (C,V ) alone. We claim that (X, S ) is a yes-instance of X3C if and only if (C, A,V, p) is a yes- instance of Borda-CCAUC. From left to right, suppose there is an exact cover S ′ ⊆ S . Let A′ = {a j ∈ A | S j ∈ S }. Then we have dist(p, xi ) = |{a j ∈ A′ | xi ∈ S j }| = 1 for every xi ∈ X, since every xi ∈ X is contained in one element of the exact cover S ′ of X exactly once. Furthermore, we have k = |S ′ | = |A′ |. Thus dist(p, u) = 3k + 2 − 3k = 2, so p defeats every candidate and is the only Borda winner of (C ∪ A′ ,V ). From right to left, suppose that p can be made the only Borda winner by adding the candidates of a subset A′ ∈ A. Therefore, p defeats every candidate in (C ∪ A′ ,V ), so we have dist(p, u) > 0 and dist(p, xi ) > 0 for every xi ∈ X (recall that p always defeats every a j ∈ A′ ). Since dist(p, xi ) = |{a j ∈ A′ | xi ∈ S j }| > 0 for every xi ∈ X, the subfamily S ′ = {S j ∈ S | a j ∈ A′ } covers X. Thus we have |S ′ | ≥ k, as there are 3k elements in X and every subset of S contains three elements. Furthermore, we have dist(p, u) = 3k + 2 − 3|A′| > 0, so |S ′ | = |A′ | ≤ k. Overall, we have that S ′ covers X and |S ′ | = k, which means that S ′ is an exact cover of X. ❑ For the destructive variant, we provide a polynomial-time algorithm to show that Borda-DCAUC is in P. The proof of Theorem 2 is omitted due to space limitations, and so are the upcoming proofs of Theorems 4, 5, 6, 7, 8, and 10 and of Corollary 3. Theorem 2. Borda is vulnerable to destructive control by adding an unlimited number of candidates. Borda-CCRPC-TE and Borda-CCPC-TE. In the problem Borda-C ONSTRUCTIVE - C ONTROL - BY-RUN -O FF -PARTITION - OF -C ANDIDATES -TE (Borda-CCRPC-TE) we ask, given an election (C,V ) and a distinguished candidate p ∈ C, whether the candidate set C can be partitioned into two subsets C1 and C2 such that p is the unique Borda winner of the final run-off among the Borda winners of subelections (C1 ,V ) and (C2 ,V ), where only unique subelection winners move forward in the ties-eliminate (TE) model. The proof of Theorem 3 below makes use of a reduction from the standard NP-complete satisfiability problem (3SAT) [12]: Given a boolean formula ϕ in 3-CNF (i.e., with exactly three literals per clause), does there exist a satisfying truth assignment to ϕ? For a boolean formula ϕ, we denote by #i the number of literals occurring in the ith clause that are negated variables. Theorem 3. Borda is resistant to constructive control by run-off partition of candidates in the ties-eliminate model. Proof. Again, membership of Borda-CCRPC-TE in NP is obvious. To show NP- hardness, we now provide a reduction from 3SAT to Borda-CCRPC-TE. Given a 3SAT instance ϕ(x1 , . . . , xn ), construct a Borda-CCRPC-TE instance ((C,V ), p) as follows. Let X = {x1 , x2 , . . . , xn } be the set of variables and let K = {K1 , . . . , Km } be (1) (2) (3) the set of clauses of ϕ, where Ki = (ℓi ∨ ℓi ∨ ℓi ), 1 ≤ i ≤ m. Furthermore, let D = {d1 , . . . , d6 } and Di = {d j | 1 ≤ j ≤ i} ⊆ D. Define the candidate set by C = X ∪ K ∪ {p, r, r∗ } ∪ D with p being the distinguished candidate the chair wants to make a unique winner. Define V to consist of the following votes: −−−−−−−−−−→ 1. For each i, 1 ≤ i ≤ m, there are two votes: C \ ({p, Ki } ∪ D) p D2#i Ki D \ D2#i and ←−−−−−−−−−− Ki d6 p C \ ({p, Ki } ∪ D) D5 . (1) (2) (3) 2. For each i, 1 ≤ i ≤ m, and for each literal ℓi , ℓi , and ℓi , there are four votes: −−−−−−−−−−−−−→ ←−−−−−−−−−−−−− either twice Ki x j p C \ ({Ki , x j , p} ∪ D) D and twice C \ ({Ki , x j , p} ∪ D) p Ki x j D −−−−−−−−−−−−−→ if ℓki = x j is a negated variable, or twice C \ ({Ki , x j , p} ∪ D) p x j Ki D and twice ←−−−−−−−−−−−−− Ki p C \ ({Ki , x j , p} ∪ D) x j D if ℓki = x j is a positive variable. →→ − − ← −← − 3. There are m votes of the form r∗ r K D p X and m votes of the form r p D K r∗ X. Since dist(C,V ) (p, r) = m(−6 − m − 2) = −m(m + 8) < 0, p does not win in (C,V ). Note that p and r score the same number of points in the first two groups of votes. Later on, we will also need the following argument. Consider a clause candidate Ki . In the first group of votes, p scores 2#i − 1 points more than candidate Ki , with #i being the number of negated variables in clause Ki . In the second group of votes, p gains two more points with respect to candidate Ki for each positive variable in clause Ki , and p loses two points with respect to candidate Ki for each negated variable in clause Ki . Since p and Ki score the same number of points in the third group of votes, we have dist(C,V ) (p, Ki ) = −2#i + 2(3 − #i ) + (2#i − 1) = 5 − 2#i . Assuming that one variable candidate x j is assigned to the other subelection than p and Ki , if x j is a negated variable in clause Ki then p gains two points with respect to candidate Ki , and if x j is a positive variable in clause Ki then p loses two points with respect to Ki . Further, if C′ is the set of candidates obtained by removing from C all variable candidates corresponding to positive variables in clause Ki , then dist(C′ ,V ) (p, Ki ) = 5 − 2#i − 2(3 − #i) = −1 because p is losing as many points with respect to Ki as there are positive variables in clause Ki . That is, p is defeated by Ki in their subelection if all variable candidates corresponding to positive variables in clause Ki are removed from the subelection containing p and Ki (and are assigned to the other subelection) and all variable candidates corresponding to negated variables in clause Ki remain in the subelection with p and Ki . For p to defeat Ki , either the subelection containing them also contains at least one variable candidate corresponding to a positive variable in clause Ki , or the other subelection contains at least one variable candidate corresponding to a negated variable in clause Ki , or both. We show that ϕ is a yes-instance of 3SAT if and only if ((C,V ), p) is a yes-instance of Borda-CCRPC-TE. From left to right, suppose there is a satisfying truth assignment to the variables of ϕ(x1 , . . . , xn ), say α. Let X+ ⊆ X denote the set of variables set to true under α, and let X− ⊆ X denote the set of variables set to false under α. Partition C into C1 = {p} ∪ D ∪ K ∪ X+ and C2 = {r, r∗ } ∪ X− . The Borda winners of subelection (C2 ,V ) are r and r∗ , since they score more points than the candidates in X− due to the third voter group and the same number of points in the other two voter groups. Due to TE, no candidate proceeds to the final run-off from this subelection. In subelection (C1 ,V ), p defeats all candidates from D, since p scores more points than these candidates in the first voter group and the same number of points in the other two voter groups. p also defeats all candidates from X+ , since p scores at least m(m + 5) points more than any candidate in X+ in the third voter group, at most m points fewer than any candidate from X+ in the second voter group (which is the case if some positive variable occurs in all clauses), and the same number of points in the first voter group. What about the clause candidates? The truth assignment (giving rise to X+ and X− ) satisfies ϕ, so each clause Ki of ϕ is satisfied. Thus, for every i, 1 ≤ i ≤ m, at least one positive variable in Ki is assigned to true or at least one negated variable in Ki is assigned to false. In the former case, the corresponding variable candidate is in X+ and thus in the same subelection as p; in the latter case, the corresponding variable candidate is in X− and thus not in the same subelection as p. By the above argument, p scores more points than Ki . Summing up, since p defeats all other candidates in her subelection and no one moves forward to the final run-off from the other subelection, p alone is the overall Borda winner. From right to left, suppose that p is the unique overall Borda winner for some par- tition of the candidates. This implies that p also is the unique Borda winner of one subelection. Since r scores more points than p due to the third voter group, p and r must be in different subelections (regardless of who else participates in them). With- out loss of generality, assume that p is in C1 and r is in C2 . Consider C2 first. r cannot be the unique Borda winner in subelection (C2 ,V ), since otherwise p would not win the run-off. Therefore, there must be candidates that either tie or defeat r in (C2 ,V ). Clause candidates, variable candidates, and candidates from D lose too many points in the third voter group (that cannot be made up for in the first and second voter groups) to tie-or-defeat r. Only candidate r∗ remains. However, r∗ cannot be the unique Borda winner of subelection (C2 ,V ), since p and r∗ would score the same number of points in the run-off, contradicting that p is the unique run-off winner. Thus there must be a tie between r and r∗ in (C2 ,V ), which prevents them both from proceeding to the run-off due to the TE model. Therefore, neither candidates from D nor from K can be in C2 , for otherwise the balance of points between r and r∗ would be perturbed due to the third voter group. Variable candidates, however, may be in C2 , since they get fewer points than either r and r∗ and would not interfere with their point balance. Thus C1 contains p and all candidates from D and K and some variable candidates. Let X+ denote the set of variable candidates in C1 . Note that p defeats the candidates in D by the first voter group and the candidates in X+ by the third voter group. Since p also defeats each clause can- didate Ki , the variable candidates must be distributed among C1 and C2 according to the argument given earlier. Now, if we assign the value true to all variables corresponding to variable candidates in X+ and the value false to all variables corresponding to variable candidates not in X+ , we obtain a satisfying truth assignment to ϕ(x1 , . . . , xn ). ❑ Borda-C ONSTRUCTIVE -C ONTROL - BY-PARTITION - OF -C ANDIDATES -TE (Borda- CCPC-TE) is defined as follows. Given an election (C,V ) and a distinguished candi- date p ∈ C, we ask whether the candidate set C can be partitioned into two subsets C1 and C2 such that p is the unique Borda winner of the final election in which the Borda winner of subelection (C1 ,V )—if there exists one (again, in model TE, only unique subelection winners move forward)—faces all candidates from C2 . For the (omitted) proof of Theorem 4 below, our reduction from 3SAT to Borda- CCRPC-TE from the proof of Theorem 3 works as well. Theorem 4. Borda is resistant to constructive control by partition of candidates in the ties-eliminate model. Borda-DCPC-TE and Borda-DCRPC-TE. We now turn to the destructive variants of the previous two problems. Unlike in the constructive case, we can give a polynomial- time algorithm for Borda-DCPC-TE. By Fact 1, Borda-DCPC-TE is the same as Borda-DCRPC-TE in the unique-winner model, which gives Corollary 1. Theorem 5. Borda is vulnerable to destructive control by partition of candidates in the ties-eliminate model. Corollary 1. Borda is vulnerable to destructive control by run-off partition of candi- dates in the ties-eliminate model. Borda-DCPC-TP and Borda-DCRPC-TP. Next, we consider the same two problems as above, but with the ties-promote (TP) instead of the ties-eliminate rule, which means that all subelection winners move forward to the final round. Theorem 6. Borda is resistant to destructive control by run-off partition of candidates in the ties-promote model. Borda-DCPC-TP is the only problem considered here (see Table 1) whose com- plexity in the unique-winner model remains open. However, we can show the following in the nonunique-winner model. Theorem 7. In the nonunique-winner model, Borda is vulnerable to destructive control by partition of candidates in the ties-promote model. By Fact 1, Borda-DCPC-TP and Borda-DCRPC-TP are identical in the nonunique- winner model. Therefore, Theorem 7 implies Corollary 2. In light of Theorem 6, this is somewhat surprising, as it shows that the complexity of Borda-DCRPC-TP starkly differs depending on the winner model. Corollary 2. In the nonunique-winner model, Borda is vulnerable to destructive con- trol by run-off partition of candidates in the ties-promote model. Borda-CCPC-TP and Borda-CCRPC-TP. Finally, we turn to the constructive vari- ants of the above two problems. Note that a slight modification of the (omitted) proof of Theorem 8 yields Corollary 3. Theorem 8. Borda is resistant to constructive control by partition of candidates in the ties-promote model. Corollary 3. Borda is resistant to constructive control by run-off partition of candi- dates in the ties-promote model. 4 Control by partition of voters with ties-promote for Borda We now solve the only two problems that still were open for voter control in Borda elec- tions (recall Table 1): constructive and destructive control by partition of voters when ties promote. In Borda-CCPV-TP, we are given an election (C,V ) and a distinguished candidate p ∈ C, and we ask whether the votes V can be partitioned into two sublists V1 and V2 such that p is the unique Borda winner of the final election, where according to the TP rule all Borda winners of the two subelections (C,V1 ) and (C,V2 ) move forward to the final round. The destructive variant is denoted by Borda-DCPV-TP. Theorem 9. Borda is resistant to constructive control by partition of voters in the ties- promote model. Proof. Membership of Borda-CCPV-TP in NP is obvious. To show NP-hardness, we provide a reduction from X3C to Borda-CCPV-TP. Let (X, S ) be a given X3C instance with X = {x1 , . . . , xm }, m = 3k, k > 1, and S = {S1 , . . . , Sn } with Si ⊆ X and |Si | = 3 for each i, 1 ≤ i ≤ n. Note that we assume that every xi ∈ X appears in exactly three subsets S j ∈ S . This restricted version of X3C was proven to be NP-complete by Gonzalez [13]. From this restriction it follows that n = 3k. Construct from (X, S ) a Borda-CCPV-TP in- stance ((C,V ), p) as follows. First we construct a large but polynomial number of buffer candidates B = B1 ∪ B2 ∪ · · · ∪ B6k+3 with B2i , 1 ≤ i ≤ 3k, containing 6k(3k + 2) − 1 candidates; B2i−1 , 1 ≤ i ≤ 3k, containing 9k(3k + 2) + 4 candidates; B6k+1 contain- ing 6k(3k + 2)(2k − 1) candidates; B6k+2 containing 3k(9k(3k + 2) + 4 + 6k(3k + 2)) candidates; and B6k+3 containing 6k(3k + 2)(k + 1) − 1 candidates. Note that all Bi , 1 ≤ i ≤ 6k + 3 are pairwise disjunct. Let C = {p, r, r∗ } ∪ X ∪ B with p being the distin- guished candidate. Define V to consist of the following groups votes V1 , V2 , V3 , and V4 : → − 1. V1 contains a single vote of the form r B6k+1 r∗ B6k+2 p X B \ (B6k+1 ∪ B6k+2 ). ←− 2. V2 contains a single vote of the form r B6k+3 r∗ X p B \ B6k+3. 3. V3 contains a vote v j of the form X \ Si p B2 j−1 r∗ B2 j r x′ x′′ x′′′ B \ (B2 j−1 ∪ B2 j ) for every S j = {x′ , x′′ , x′′′ } ∈ S . ← − 4. V4 contains 3k votes of the form r X p r∗ B. Note that in the way these votes are set up, every buffer candidate b j ∈ B is behind some candidate from C \ B in every vote (as a matter of fact, b j is behind every candidate from C \ B in all votes but one). This lets us conveniently disregard all buffer candidates, since they are eliminated in all possible subelections and can never reach the final. Note that p is not winning in (C,V ), since dist(C,V ) (p, r) ≤ −(3k(9k(3k + 2) + 4 + 6k(3k + 2)) + 1) + 3k(6k(3k + 2) + 9k(3k + 2) + 4) < 0. We claim that (X, S ) is a yes- instance of X3C if and only if (C, A,V, p) is a yes-instance of Borda-CCPV-TP. Suppose there exists an exact cover S ′ ⊆ S . Let Vb = {v j | S j ∈ S ′ }. Partition V into V ′ = V1 ∪ (V3 \ V b ) ∪V4 and V ′′ = V2 ∪ Vb . In the subelection (C,V ′ ), r∗ beats every other candidate, since dist(C,V ′ ) (r∗ , r) = 3k(3k + 2)− 1 − (3k + 2) > 0, dist(C,V ′ ) (r∗ , p) = 3k(9k(3k + 2) + 6k(3k + 2) + 5) − 2k(9k(3k + 2) + 5) − 3k > 0, and dist(C,V ′ ) (r∗ , xi ) ≥ dist(C,V ′ ) (r∗ , p) + 1 − (2k − 2)(3k − 3) − 9k2 > 0 for every xi ∈ X. In the other subelec- tion (C,V ′′ ), p is the only Borda winner, since dist(C,V ′′ ) (p, r∗ ) = k(9k(3k + 2) + 5) − (3k + 1) > 0, dist(C,V ′′ ) (p, r) = −6k(k + 1)(3k + 2) − (3k + 1) + 5k(3k(3k + 2) + 1) > 0 and dist(C,V ′′ ) (p, xi ) ≥ −3k − (k − 1)(3k − 3) + 15k(3k + 2) + 6 > 0. In the final election ({p, r∗ },V ), p is the only Borda winner, since dist({p,r∗ },V ) (p, r∗ ) = 6k − 2 > 0. For the converse, suppose there is no exact cover. We now show that p cannot be made the only Borda winner by partitioning the votes. Since no buffer candidate reaches the final, for a subset X ′ ⊆ X only the following final elections with p participat- ing are possible: ({p, r, r∗ } ∪ X ′,V ), ({p, r} ∪ X ′ ,V ), ({p, r∗ } ∪ X ′ ,V ) and ({p} ∪ X ′,V ). It is easy to see that p wins alone only if r∗ participates and X ′ = 0. / Without loss of generality, assume that V1 ⊆ V ′ . Then p cannot win (C,V ′ ), since the deficit of 2k(6k(3k + 2)) + 3k(15k(3k + 2) + 5) to r cannot be made up for, not even with all the votes from V3 . Therefore, p can only win (C,V ′′ ). For p to beat every xi ∈ X in (C,V ′′ ), there need to be votes Vb ⊆ V3 in V ′′ so that for every xi ∈ X there is a vj ∈ Vb with xi ∈ S j . Otherwise, p would be behind xi in every vote of V ′′ . Since there is no exact cover, we need at least k + 1 to ensure that p is not beaten by a candi- date xi ∈ X in (C,V ′′ ). Now, for r∗ to reach the final, she needs to either tie with p in (C,V ′′ ) or win (C,V ′ ). Since Vb ⊆ V3 , r∗ cannot make up the deficit of at least k(9k(3k + 2) + 4) points to p, as she is ahead of r∗ in all votes of V4 and the vote of V2 would give r∗ only 3k + 1 points more than p. So r∗ needs to win (C,V ′ ). With V1 ⊆ V ′ , it follows that V2 ⊆ V ′′ , or else the point deficit of r∗ to r in (C,V ′ ) from votes of V1 and V2 cannot be made up for by at most 2k − 1 votes from V3 , since −(6k(3k + 2)(2k − 1) + 1) − (6k(3k + 2)(k + 1)) + 6k(3k + 2)(2k − 1) < 0. But still, with only 2k − 1 votes of V3 in V ′ and any number of votes from V4 in V ′ , we have dist(C,V ′ ) (r∗ , r) < 0, so r∗ is not winning in (C,V ′ ) and cannot reach the final. There- fore, without an exact cover, either p or r∗ cannot reach the final. ❑ Theorem 10. Borda is resistant to destructive control by partition of voters in the ties- promote model. 5 Conclusions and future work We have solved ten open problems about the complexity of standard control scenarios in Borda elections (recall Table 1), leaving just one case open: destructive control by partition of candidates in the ties-promote model. In particular, complementing previous results, we have now shown that Borda is resistant to every standard type of constructive control, whereas it is vulnerable to most of the destructive control types. We have also identified one of the rare cases where the complexity of a control problem in the unique- winner model parts company from that in the nonunique-winner model. As future work for control in Borda elections, we propose (a) to solve the one open question mentioned above, (b) to provide a parameterized complexity analysis of the cases where resistance is known, and (c) to study online control for sequential Borda elections (see Hemaspaandra et al. [17, 18] for the model of online control in sequential elections and Neveling and Rothe [25] for the first such results for sequential Borda). Another challenging task is to settle the complexity of control for all scoring rules, ideally by establishing dichotomy results in the style of Hemaspaandra et al. [19, 20]. Acknowledgments: This work was supported in part by DFG grant RO-1202/15-1. References 1. Y. Bachrach, O. Lev, Y. Lewenberg, and Y. Zick. Misrepresentation in district voting. In Proceedings of the 25th International Joint Conference on Artificial Intelligence, pages 81– 87. AAAI Press/IJCAI, July 2016. 2. J. Bartholdi III, C. Tovey, and M. Trick. How hard is it to control an election? Mathematical and Computer Modelling, 16(8/9):27–40, 1992. 3. D. Baumeister and J. Rothe. Preference aggregation by voting. In J. Rothe, editor, Eco- nomics and Computation. An Introduction to Algorithmic Game Theory, Computational So- cial Choice, and Fair Division, Springer Texts in Business and Economics, chapter 4, pages 197–325. Springer-Verlag, 2015. 4. J. Chen, P. Faliszewski, R. Niedermeier, and N. Talmon. Elections with few voters: Candidate control can be easy. In Proceedings of the 29th AAAI Conference on Artificial Intelligence, pages 2045–2051. AAAI Press, Jan. 2015. 5. V. Conitzer and T. Walsh. Barriers to manipulation in voting. In F. Brandt, V. Conitzer, U. Endriss, J. Lang, and A. Procaccia, editors, Handbook of Computational Social Choice, chapter 6, pages 127–145. Cambridge University Press, 2016. 6. E. Elkind, P. Faliszewski, and A. Slinko. Cloning in elections: Finding the possible winners. Journal of Artificial Intelligence Research, 42:529–573, 2011. 7. G. Erdélyi, M. Fellows, J. Rothe, and L. Schend. Control complexity in Bucklin and fallback voting: A theoretical analysis. Journal of Computer and System Sciences, 81(4):632–660, 2015. 8. G. Erdélyi, E. Hemaspaandra, and L. Hemaspaandra. More natural models of electoral con- trol by partition. In Proceedings of the 4th International Conference on Algorithmic Deci- sion Theory, pages 396–413. Springer-Verlag Lecture Notes in Artificial Intelligence #9346, September 2015. 9. G. Erdélyi, M. Nowak, and J. Rothe. Sincere-strategy preference-based approval voting fully resists constructive control and broadly resists destructive control. Mathematical Logic Quarterly, 55(4):425–443, 2009. 10. P. Faliszewski, E. Hemaspaandra, L. Hemaspaandra, and J. Rothe. Llull and Copeland voting computationally resist bribery and constructive control. Journal of Artificial Intelligence Research, 35:275–341, 2009. 11. P. Faliszewski and J. Rothe. Control and bribery in voting. In F. Brandt, V. Conitzer, U. En- driss, J. Lang, and A. Procaccia, editors, Handbook of Computational Social Choice, chap- ter 7, pages 146–168. Cambridge University Press, 2016. 12. M. Garey and D. Johnson. Computers and Intractability: A Guide to the Theory of NP- Completeness. W. H. Freeman and Company, 1979. 13. T. Gonzalez. Clustering to minimize the maximum intercluster distance. Theoretical Com- puter Science, 38:293–306, 1985. 14. E. Hemaspaandra, L. Hemaspaandra, and C. Menton. Search versus decision for election manipulation problems. Technical Report arXiv:1202.6641 [cs.GT], Computing Research Repository, arXiv.org/corr/, 2012. 15. E. Hemaspaandra, L. Hemaspaandra, and C. Menton. Search versus decision for election ma- nipulation problems. In Proceedings of the 30th Annual Symposium on Theoretical Aspects of Computer Science, volume 20 of LIPIcs, pages 377–388. Schloss Dagstuhl – Leibniz- Zentrum für Informatik, Feb. 2013. 16. E. Hemaspaandra, L. Hemaspaandra, and J. Rothe. Anyone but him: The complexity of precluding an alternative. Artificial Intelligence, 171(5–6):255–285, 2007. 17. E. Hemaspaandra, L. Hemaspaandra, and J. Rothe. The complexity of controlling candidate- sequential elections. Theoretical Computer Science, 678:14–21, 2017. 18. E. Hemaspaandra, L. Hemaspaandra, and J. Rothe. The complexity of online voter control in sequential elections. Journal of Autonomous Agents and Multi-Agent Systems, 31(5):1055– 1076, 2017. 19. E. Hemaspaandra, L. Hemaspaandra, and H. Schnoor. A control dichotomy for pure scoring rules. In Proceedings of the 28th AAAI Conference on Artificial Intelligence, pages 712–720. AAAI Press, July 2014. 20. E. Hemaspaandra and H. Schnoor. Dichotomy for pure scoring rules under manipulative electoral actions. In Proceedings of the 22nd European Conference on Artificial Intelligence, pages 1071–1079. IOS Press, August/September 2016. 21. Y. Lewenberg and O. Lev. Divide and conquer: Using geographic manipulation to win district-based elections. In U. Grandi and J. Rosenschein, editors, Proceedings of the 6th International Workshop on Computational Social Choice, Toulouse, France, June 2016. 22. A. Loreggia, N. Narodytska, F. Rossi, B. Venable, and T. Walsh. Controlling elections by replacing candidates or votes (extended abstract). In Proceedings of the 14th International Conference on Autonomous Agents and Multiagent Systems, pages 1737–1738. IFAAMAS, May 2015. 23. C. Maushagen and J. Rothe. Complexity of control by partitioning veto and maximin elections and of control by adding candidates to plurality elections. In Proceedings of the 22nd European Conference on Artificial Intelligence, pages 277–285. IOS Press, Au- gust/September 2016. 24. C. Menton. Normalized range voting broadly resists control. Theory of Computing Systems, 53(4):507–531, 2013. 25. N. Neveling and J. Rothe. Solving seven open problems of offline and online control in Borda elections. In Proceedings of the 31st AAAI Conference on Artificial Intelligence, pages 3029–3035. AAAI Press, Feb. 2017. 26. D. Parkes and L. Xia. A complexity-of-strategic-behavior comparison between Schulze’s rule and ranked pairs. In Proceedings of the 26th AAAI Conference on Artificial Intelligence, pages 1429–1435. AAAI Press, July 2012. 27. C. Puppe and A. Tasnádi. Optimal redistricting under geographical constraints: Why “pack and crack” does not work. Economics Letters, 105(1):93–96, 2009. 28. N. Russel. Complexity of control of Borda count elections. Master’s thesis, Rochester Institute of Technology, 2007.