=Paper=
{{Paper
|id=Vol-1949/ICTCSpaper12
|storemode=property
|title=Closing the Gap of Control Complexity in Borda Elections: Solving ten open cases
|pdfUrl=https://ceur-ws.org/Vol-1949/ICTCSpaper12.pdf
|volume=Vol-1949
|authors=Marc Neveling,Jörg Rothe
|dblpUrl=https://dblp.org/rec/conf/ictcs/NevelingR17
}}
==Closing the Gap of Control Complexity in Borda Elections: Solving ten open cases ==
https://ceur-ws.org/Vol-1949/ICTCSpaper12.pdf
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.