We consider the problem of control in elections where an election chair seeks to either make a designated candidate win, or prevent her from winning, via actions such as adding, deleting, or partitioning either candidates or voters. These scenarios have been studied for many voting systems and the related control problems have been classified in terms of their complexity. However, 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 complexity 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 vulnerable 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.
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 [
Each of these scenarios has been thoroughly discussed in the literature (for
example, 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
control have been proposed and studied by Puppe and Tasnádi [
C U A C C D
C A C C D
C D C C D
E T C P C C D
P T C P C C D
E
T
C
P
R
C
C D
have been presented for each scenario. While they have been studied intensively for
many voting systems, such as for plurality, Condorcet, approval [
The eleven results previously known for control in Borda are due to Russel [
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,
DCPCTP, 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
nonuniquewinner model, Borda-DCRPC-TP (which is known to coincide with Borda-DCPC-TP
in the nonunique-winner model [
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 represent 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 [
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. [
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. [
In the problem Borda-CONSTRUCTIVE-CONTROL-BY-ADDING-AN-UNLIMITEDNUMBER-OF-CANDIDATES (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. [
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. [
We claim that (X , S ) is a yes-instance of X3C if and only if (C, A,V, p) is a yesinstance 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-CONSTRUCTIVECONTROL-BY-RUN-OFF-PARTITION-OF-CANDIDATES-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) [
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 NPhardness, 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 the set of clauses of ϕ, where Ki = (ℓi(1) ∨ ℓi(2) ∨ ℓi(3)), 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. 2. For each i, 1 ≤ i ≤ −m−,−a−n−d−f−o−r−e−a−ch−−l→iteral ℓi(1), ℓi(2), ←an−d−−ℓi(−3−),−t−h−er−e−a−r−e−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 ℓik ←=−x−j−i−s−a−n−e−g−a−te−d−−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 ℓik = 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 partition 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). Without 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 candidate 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-CONSTRUCTIVE-CONTROL-BY-PARTITION-OF-CANDIDATES-TE (BordaCCPC-TE) is defined as follows. Given an election (C,V ) and a distinguished candidate 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 BordaCCRPC-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 polynomialtime 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 candidates 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 complexity 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 nonuniquewinner 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 control by run-off partition of candidates in the ties-promote model.
Borda-CCPC-TP and Borda-CCRPC-TP. Finally, we turn to the constructive variants 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 candidates in the ties-promote model. 4
We now solve the only two problems that still were open for voter control in Borda elections (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 tiespromote 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 [
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 yesinstance 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 ) ∪ V4 and V ′′ = V2 ∪ Vb. In the subelection (C,V ′), r∗ beats every b 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 subelection (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 participating 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 v j ∈ 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 candidate 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. Therefore, 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 tiespromote model. 5
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 uniquewinner 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. [