Toward Completing the Picture of Control in Schulze and Ranked Pairs Elections

1 Introduction

Elections play a fundamental role in decision-making processes of societies. Both the Schulze method [Schulze, 2011; Schulze, 2023] and the ranked pairs method [Tideman, 1987] satisfy many natural, desirable axioms.

The Schulze method is a relatively new voting rule and has gained unusual popularity over the past decade due to its outstanding axiomatic properties. In the real world, organizations like the Wikimedia Foundation, Kubernetes, or the Debian Vote Engine [Schulze, 2023] have used it in their decision-making processes. Although winner determination with the Schulze method is fairly complicated compared to most other voting rules, it can still be done in polynomial time [Schulze, 2011; Sornat et al., 2021]. The ranked pairs method was specifically designed to satisfy the independence of clones criterion [Tideman, 1987]. In general, its axiomatic properties are as outstanding as Schulze's. That ranked pairs is barely widespread might be due to the fact that winner determination strongly depends on the handling of ties: When using "parallel universe tiebreaking" [Conitzer et al., 2009], the winner determination problem is NP-complete. However, it becomes tractable when defining ranked pairs as a resolute rule by using a fixed tie-breaking method [Brill and Fischer, 2012].

The supplementary material for this paper [Maushagen et al., 2024] can be found here: https://arxiv.org/abs/2405.08956.

We study electoral control where a so-called election chair (or, simply chair) attempts to change the outcome of an election by changing its structure. Common examples are adding, deleting, partitioning [Bartholdi III et al., 1992; Hemaspaandra et al., 2007], or replacing [Loreggia et al., 2015] candidates or voters. In addition to these control types, we also study multimode control [Faliszewski et al., 2011] where the chair can combine several attacks into one. For each corresponding electoral control problem, there is a constructive case [Bartholdi III et al., 1992] where the goal is to make a favored candidate win the election, and a destructive case [Hemaspaandra et al., 2007] where the chair's aim is to prevent a despised candidate from winning. It is natural to assume that it is beneficial for a voting rule to be immune to control, i.e., it is impossible to change the outcome of an election by that control type. However, immunity to control types does not occur often. 1 In fact, most voting rule are susceptible to control [Faliszewski and Rothe, 2016], i.e., control is possible in a least some instances. Computational intractability can then be seen as a form of resistance to control: If it is computationally hard for an agent to decide if the goal of the attack can be achieved, it may deter the attacker from spending resources on this task. On the other hand, not all forms of control are malicious. In many cases, deciding if a control action can be achieved in polynomial time is beneficial for deciding whether to allocate resources to, e.g., a voter drive or spawning new nodes in the context of large clusters. We call a voting rule vulnerable to a control type if the corresponding decision problem can be decided in polynomial time.

While many standard control types have already been studied for Schulze and ranked pairs (Table 1), control by replacing candidates or voters and exact multimode control remained open. There are many real world situations where a chair must adhere to a specific number of candidates, e.g., if the election's size is predetermined and a fixed number of candidates are already nominated, forcing the chair to nominate exactly the missing number of candidates. The restriction makes control impossible in some situations, where control by adding fewer candidates would be successful. Other (practical) settings include autonomous agents where, e.g., the size of the cluster is predetermined. A chair may be able to influence some part of the cluster, but is forced to adhere to the overall determined size (examples can be found in the supplementary material).

1 Immunity to control corresponds to strategyproofness against manipulation (a.k.a. strategic voting), since both notions formalize the impossibility to reward strategic behaviour with success.

RelatedWork: Bartholdi et al. [1992] introduced constructive control types and Hemaspaandra et al. [2007] the corresponding destructive cases. Control by replacing candidates or voters was introduced by Loreggia et al. [2015], while Faliszewski et al. [2011] introduced and studied multimode control. Erd´elyi et al. [2021] provide an extensive study and overview of various control problems, including replacing candidates or voters and also multimode control. 2

Other types of strategic influence on elections are manipulation, where a voter or a group of voters state their preferences strategically (i.e., untruthfully), and bribery, where a controlling agent bribes voters to change their preferences (see, e.g., [Bartholdi III and Orlin, 1991; Bartholdi III et al., 1989; Conitzer and Sandholm, 2006; Faliszewski et al., 2009a; Faliszewski et al., 2009b]). Control, bribery, and manipulation have been studied for a wide range of voting rules, as surveyed by Faliszwski and Rothe [2016] (bribery and control) and Conitzer and Walsh [2016] (manipulation), see also [Baumeister and Rothe, 2015].

For Schulze and ranked pairs, Parkes and Xia [2012], Xia et al. [2009], Menton and Singh [2013], and Gaspers et al. [2013] studied constructive and destructive control by adding or deleting voters or candidates, bribery, and manipulation. Table 1 gives an overview of known results. Hemaspaandra et al. [2013] showed fixed-parameter tractability for bribing, controlling, and manipulating Schulze and ranked pairs elections with respect to the number of candidates and provided algorithms with uniform polynomial running time that are independent of the number of candidates. Menton and Singh [2013] also provided results on control by partition and runoff partition of candidates and partition of voters for Schulze and further showed some results for all Condorcetconsistent voting rules.

2 Preliminaries

An election is a pair (C, V ), where C = {c1, . . . , cm} is a set of candidates and V is a list of n votes in form of preferences over all candidates in C. In this paper, preferences are expressed as a strict linear order over C, 3 where voters rank the candidates in descending order from most to least preferred. We write c ≻vi d to express that a voter vi ∈ V prefers candidate c over d. When it is clear from the context, we omit ≻vi and simply write c d. For a set of candidates A ⊆ C, we refer to the lexicographic order (we first consider the alphabetic order and then the subscript) of those candidates by simply writing -→A , and ←- A for the reverse. To shorten notation of votes we will sometimes include sets of candidates in the votes. If a set A occurs in a vote, the candidates from A are ranked in lexicographic order at the given place of the voters ranking. For example, cA is the same as c -→A and denotes the vote that ranks c first and then all candidates from A follow in increasing lexicographic order. For a set of candidates C and two candidates c, d ∈ C, we will write W(c, d) for the two votes c d ------→ C \ {c, d} and ←------ C \ {c, d} c d. For a given election (C, V ), let NV (c, d) be the number of votes, in which candidate c is ranked above candidate d. We call this the pairwise comparison between c and d. Similarly, let DV (c, d) = NV (c, d) - NV (d, c). Note that we omit the list of votes if it is clear from the context. Before we introduce the procedures for winner determination in Schulze and ranked pairs election, we first introduce the weighted majority graph (WMG). A WMG for an election (C, V ) is a weighted directed graph G = ( ˆ V ,E,w), where ˆ V = C and (c, d) ∈ E with weight w(c, d) = DV (c, d) for each ordered pair of candidates c, d ∈ C. Note that, since the votes are expressed as strict orders, we have DV (c, d) = -DV (d, c). Therefore, we omit edges with a negative weight in depictions.

2 Besides for voting, control has also been studied in, e.g., judgment aggregation [Baumeister et al., 2020] and for weighted voting games [Rey and Rothe, 2018; Kaczmarek and Rothe, 2024] and graph-restricted weighted voting games [Kaczmarek et al., 2023].

3 Some voting rule (notably, e.g., Schulze voting [2011]) allow voters to express preferences as weak orders. Following previous work (e.g., [Menton and Singh, 2013; Parkes and Xia, 2012; Hemaspaandra et al., 2013]), we restrict them here to linear orders.

A voting rule r : {(C, V ) | (C, V ) is an election} → 2C determines the set of winners of an election (C, V ). We focus on the voting rules Schulze and ranked pairs. A candidate c ∈ C is a Condorcet winner of an election (C, V ) if NV (c, d) > NV (d, c) holds for all d ∈ C with c ̸= d. A candidate c ∈ C is a weak Condorcet winner if NV (c, d) ≥ NV (d, c) for all d ∈ C with c ̸= d. Note that there can be at most one Condorcet winner but possibly multiple weak Condorcet winners. Both Schulze and ranked pairs are Condorcet-consistent voting rules, meaning they choose the Condorcet winner whenever there is one.

Schulze. Let the strength of a path p (str(p)) be the weight of the weakest edge, i.e., the minimum weight, in a directed path p between two candidates in the WMG. For each distinct pair of candidates c, d ∈ C, let the strength of the strongest path be P(c, d) = max{str(p) | p is a path from c to d}. A candidate c ∈ C is a Schulze winner of (C, V ) if P(c, d) ≥ P(d, c) for each d ∈ C \ {c}. To find these candidates one can build a second directed graph, which has an edge from c to d if and only if P(c, d) > P(d, c). Each candidate with an in-degree of zero in this graph is a Schulze winner. There can be multiple Schulze winners.

Ranked pairs. For an election (C, V ), we first calculate DV (c, d) for all pairs of distinct candidates c, d ∈ C, and order the pairs by weight from highest to lowest, i.e., we order the values of DV (c, d). Now in each step, we consider the top pair (c, d) of this weight order, which has not yet been considered. Following Parkes and Xia [2012], we break ties according to a fixed tie-breaking rule. We add an edge (c, d) to a directed graph G = (V ′ ,E) where V ′ = C, unless inserting this edge would create a cycle, in which case the pair (edge) is disregarded. When all pairs have been considered, the ranked pairs winner of (C, V ) (subject to the fixed tiebreaking) is the candidate corresponding to the source of G. 4

For examples of the Schulze and ranked pairs method we refer to the supplementary material. Note that Tideman [1987] originally gives an irresolute procedure and corresponding function for ranked pairs, which considers all possible ways of breaking ties and is NP-complete [Brill and Fischer, 2012]. Interestingly, the full ranking of candidates and winner determination including ties can be computed in polynomial time for Schulze [2023]. For our reductions, it is important that the procedures run in polynomial time (which we achieve by using a fixed tie-breaking scheme for ranked pairs), but it is not necessary to be highly efficient. Consequently, there may be other procedures that are faster (see, e.g., [Sornat et al., 2021] for Schulze) or handle ties in a different way for ranked pairs (see, e.g., [Brill and Fischer, 2012; Wang et al., 2019]).

We study various types of electoral control, starting with constructive control by deleting candidates (CCDC) as defined by Bartholdi et al. [1992] for a voting rule E:

E-CONSTRUCTIVE CONTROL BY DELETING CANDIDATES

Given: An election (C, V ), a distinguished candidate p ∈ C, and ℓ ∈ N.

Question: Is it possible to make p the unique winner of the E election resulting from (C, V ) by deleting at most ℓ candidates?

In the setting of replacing candidates or voters [Loreggia et al., 2015; Erd´elyi et al., 2021], the chair must not alter the size of the election and instead must add a candidate or voter for each one she deletes. Formally, in E-CONSTRUCTIVE CONTROL BY REPLACING CANDIDATES (E-CCRC) we are given two disjoint sets of candidates, C and D, a list of votes over C ∪D, a distinguished candidate p ∈ C, and ℓ ∈ N, and we ask if it is possible to make p the unique winner of the E election resulting from (C, V ) by replacing at most ℓ candidates C ′ ⊆ C with candidates D′ ⊆ D, where |C ′ | = |D′ |. E-CONSTRUCTIVE CONTROL BY REPLACING VOTERS (ECCRV) is defined analogously by asking whether it is possible to make a preferred candidate p the unique winner by replacing at most ℓ votes V ′ ⊆ V with votes U ′ ⊆ U such that |V ′ | = |U ′ |, where U is a list of as yet unregistered votes.

4 In the original definition, the voting rule ranked pairs [Tideman, 1987] returns a complete ranking of the candidates. We use a slightly simplified definition of ranked pairs introduced by Berker et al. [2022] that only returns the winner of the election.

In these control scenarios, a chair's goal is to make a preferred candidate the unique winner. A chair may also be interested in preventing a candidate from winning. This setting is known as destructive control [Hemaspaandra et al., 2007]. Instead of asking whether a candidate can be made the winner, we ask whether the sole victory of a candidate can be prevented (note that for a control action to be successful, it is enough to have the candidate be a winner among others). We write E-DCDC for E-DESTRUCTIVE CONTROL BY DELETING CANDIDATES, E-DCRC for E-DESTRUCTIVE CONTROL BY REPLACING CANDIDATES, and E-DCRV for EDESTRUCTIVE CONTROL BY REPLACING VOTERS. Aside from the unique-winner model which is used in the previous definitions, in the nonunique-winner model we ask whether a preferred candidate can be made a winner (possibly among others) in the constructive case, and whether a despised candidate can be prevented from winning altogether in the destructive case. Note that when interpreting a voting rule as resolute (i.e., to always yield exactly one winner), the unique-winner and nonunique-winner models are the same.

In addition to the above control problems, we also study variations of multimode control as introduced by Faliszewski et al. [2011], where several of the standard control attacks and bribery can be combined into one action:

E -CONSTRUCTIVE CONTROL BY AC+DC+AV+DV+B

Given: Two disjoint sets of candidates, C andD, two disjoint lists of votes over C ∪ D, V and U, a distinguished candidate p ∈ C, and ℓAC, ℓDC, ℓAV , ℓDV , ℓB ∈ N.

Question: Is it possible to find two sets, C′ ⊆ C \{p} and D′ ⊆

D, and two sublists of votes, V ′ ⊆ V and U ′ ⊆ U, such that p is the unique winner of the E election that results from ((C\C′ )∪D′ , (V \V ′ )∪U ′ ) by bribing at most ℓB votes in (V \ V ′ ) ∪U ′ ), and |D′ | ≤ ℓAC, |C′ | ≤ ℓDC, |U ′ | ≤ ℓAV , and |V ′ | ≤ ℓDV ?

We abbreviate multimode control problems in the obvious way; e.g., we use the shorthand E-CCAC+DC+AV+DV+B for the above problem. Faliszewski et al. [2011] define a method to classify all 25 - 1 variants of multimode control for a voting rule, called classification rule A. Using the classification rule A and the known results for adding and deleting candidates or voters and for bribery (see Table 1), it immediately follows that, except for Schulze-DCAC+DC, Schulze is resistant to any multimode attack. Since ranked pairs is resistant to all single-pronged attacks, it clearly also resists all combinations of multimode control.

In any instance of E-EXACT CONSTRUCTIVE CONTROL BY AC+DC+AV+DV+B, it must hold that |D′ | = ℓAC,

|C ′ | = ℓDC, |U ′ | = ℓAV , |V ′ | = ℓDV , and exactly ℓB voters in (V \ V ′ ) ∪ U ′ are bribed. Each corresponding nonexact control problem polynomial-time Turing reduces to the exact control problem. The destructive variants EDESTRUCTIVE CONTROL BY AC+DC+AV+DV+B and EEXACT DESTRUCTIVE CONTROL BY AC+DC+AV+DV+B are defined analogously by asking whether it is possible to make p not a (unique) winner, and we again use the obvious shorthands. Sometimes, we exclude certain actions from multimode control, considering, e.g., only candidate control (E-DCAC+DC) and omit the unneeded input parameters.

Note that we do not allow candidates in D or voters in U to be deleted, as we do not consider it realistic to remove a candidate or voter from an election right after adding. Even though this does not make a difference for the nonexact problems (as it is allowed to simply add or delete fewer candidates or voters), it may affect the result for exact multimode control as shown in the supplementary material.

3 Schulze Resists Constructive Control by Deleting Candidates

In this section, we prove the following result by describing and fixing a flaw in the proof of Menton and Singh [2013]. 5

Theorem 1. Schulze-CCDC is NP-complete in the nonunique-winner model.

Proof. The proof of this result, due to Menton and Singh [2013, Thm. 2.2], shows a clever reduction from 3SAT, but it is technically flawed. We briefly present their reduction and give a counterexample showing that it is not correct.

In the 3-SATISFIABILITY problem (3SAT), we are given a set X of variables and a set Cl = {Cl1, . . . ,Clk} of clauses over X, each having exactly three literals, and we ask whether there is a satisfying assignment for ϕ, where ϕ is the conjunction of all clauses Cli ∈ Cl. Given a 3SAT instance (X, Cl), Menton and Singh [2013] construct a Schulze-CCDC instance ((C, V ′ ), p, k) as follows. The set of candidates C contains k+1 clause candidates c1i , . . . , ck+1 i for each clause Cli ∈ Cl, three literal candidates x1i , x2i , x3i for each clause Cli, where xji is the jth literal in clause Cli, k+1 negation candidates n1i,j,m,n , . . . , nk+1 i,j,m,n for each pair of literals xji , xnm, where one is the negation of the other, and the distinguished candidate p and an additional candidate a. Let Ci = {c1i , . . . , ck+1 i } be the set of all clause candidates for clause Cli ∈ Cl and let K = ⋃k+1 i=1 Ci be the set of all clause candidates. Let Li = {x1i , x2i , x3i } be the set of literal candidates for the clause Cli and let L = ⋃ki=1 Li be the set of all literal candidates. Let Nijmn = {n1ijmn , . . . , nk+1 ijmn } be the set of negation candidates for the literals xji , xnm that are a negation of each other, and let N be the set of all such negation candidates. For a positive integer z, we write [z] = {1, . . . , z} as a shorthand.

5 Menton and Singh agree that our construction fixes their flaw. Menton writes (private email communication on December 5, 2023), "I have tried my best to understand the old proof and your correction of it. The diagrams in your paper were very helpful for this! [. . . ] Your solution changes the votes so there are lower weight edges in the graph and additional paths from p back to the clause candidates such that there is an equal weight path from p to the clause candidates to those persisting paths. Deleting the appropriate literal candidates is still necessary to break the higher-weight paths from the clause candidates to p. Looks good to me!"

Menton and Singh [2013] define the following list of votes V ′ (which we will change later to fix the proof):

The deletion limit is k, the number of clauses. Menton and Singh [2013] argue that p can be made a Schulze winner by deleting at most k candidates from C if and only if there is a truth assignment that makes the given 3SAT instance true.

We now briefly present our counterexample, where we map a yes-instance of 3SAT to a no-instance of SchulzeCCDC. Let (X, Cl) be our given 3SAT instance, with X = {x1, x2, x3} and Cl = {(x1 ∨ x2 ∨ ¬x3), (¬x1 ∨ x2 ∨ x3)}, i.e., we consider the CNF formula

A detailed description of this counterexample is given in the supplementary material. Their reduction is quite clever, but unfortunately wrong, as shown by the counterexample. However, by modifying it appropriately, we can ensure that p can indeed be made a Schulze winner of the election by deleting at most k candidates if and only if (X, Cl) is a yes-instance of 3SAT. For our modifications, it is only necessary to change the list of votes. For votes (A) through (F) we adjust the number of votes to 2. Additionally, we add 1 vote W(a, c) for each c ∈ K. The graph in Figure 1 shows the weighted majority graph for the 3SAT instance from our counterexample adapted to the new reduction. We claim that (X,Cl) is a yes-instance of 3SAT if and only if ((C, V ), p, k) is a yesinstance of Schulze-CCDC in the nonunique-winner model.

From left to right, let (X,Cl) be a yes-instance of 3SAT. Since we have a yes-instance of 3SAT, we have a truth assignment that makes at least one literal in each clause Cli ∈ Cl true. We claim that p can be made a Schulze winner by deleting one literal candidate corresponding to some true literal for each clause. The only path with weight four from a clause candidate cji ∈ K to p is through the literal candidates: from x1i via x2i to x3i . Since we deleted one literal candidate for each clause, there no longer exists a weight-4 path from a clause candidate to p and P(p, c) = 2 ≥ P(c, p) for c ∈ K. For each c ∈ L ∪ {a}, we have P (p, c) = 4 ≥ P (c, p). Since we deleted only literal candidates where the corresponding literal was assigned to be true, we never have the case that we deleted two literal candidates xji , xnm, which negate each other. Thus we still have a weight-2 path from p to each negation candidate and P(p, c) = 2 = P(c, p) for each c ∈ N. It follows that ((C, V ), p, k) is a yes-instance of SchulzeCCDC in the nonunique-winner model.

From right to left, let (X,Cl) be a no-instance of 3SAT. Thus, for each assignment of the literals, there exists a clause which is false. To ensure that p is a winner of the election, it is necessary that P(p, c) ≥ P(c, p) for each c ∈ C \ {p}. Since P (p, c) = 2 < 4 = P (c, p) for each c ∈ K, we have to destroy each path of weight greater than two from the clause candidates to p, in particular the path through the literal candidates xji ∈ Ci, j ∈ {1, 2, 3}. Due to the deletion limit k = |Cl|, it is necessary to delete one literal candidate for each clause. Consider any subset of literals of size k such that for each clause one literal is contained in the set. It follows that this set contains at least two literals, xji and xnm, that negate each other, otherwise, the formula would be satisfiable and we would have a yes-instance of 3SAT. By deleting the corresponding two literal candidates, we no longer have a path from p to the negation candidates n ∈ Nijmn. It follows that P(p, n) < P(n, p) and it is impossible to make p a Schulze winner of the election by deleting at most k candidates. Therefore, ((C, V ), p, k) is a no-instance of SchulzeCCDC in the nonunique-winner model.

From right to left, let ((C, V ), p, k) be a yes-instance of Schulze-CCDC. To ensure that p is a winner of the election, it is necessary that P(p, c) ≥ P(c, p) for each c ∈ C \ {p}. Since P (p, c) = 2 < 4 = P (c, p) for each c ∈ K, we have to destroy each path of weight greater than two from the clause candidates to p, in particular the path through the literal candidates xji ∈ Ci, j ∈ {1, 2, 3}. Due to the deletion limit k = |Cl|, it is necessary to delete one literal candidate for each clause. Consider any subset of literals of size k such that for each clause one literal is contained in the set. If all of these subsets contained at least two literals, xji and xnm, that negate each other, i.e., if the 3SAT formula were not satisfiable, by deleting the corresponding two literal candidates, we would no longer have a path from p to the negation candidates n ∈ Nijmn. That is, it would hold that P(p, n) < P(n, p) and it would be impossible to make p a Schulze winner by deleting at most k candidates. Thus, since we have a yesinstance of Schulze-CCDC, there must exist at least one subset of literals, such that for each clause one literal is contained in the set, i.e., set to true and we have 3SAT-yes.

Finally, it is easy to see that Schulze-CCDC is in NP.

Previously, Schulze-CCDC was only studied in the nonunique-winner model. By slightly adapting the previous construction (see the supplementary material), we can now also show NP-completeness in the unique-winner model.

Theorem 2. Schulze-CCDC is NP-complete in the uniquewinner model.

4 Destructive Control by Deleting Candidates and Variants Thereof

In this section, we examine a peculiarity of standard destructive control by deleting candidates for Schulze elections, which allows us to reduce the number of candidates we need to consider for deletion. Using this approach, we are able to re-establish the result that DCDC is polynomial-time solvable for Schulze elections, which Menton and Singh claimed in an early version (v1) of their arXiv preprint [Menton and Singh, 2012]. However, Menton and Singh removed this result (and the corresponding result for Schulze-DCAC) from all subsequent versions of the arXiv preprint and from their IJCAI 2013 paper [Menton and Singh, 2013], stating these two control problems as open. Additionally, we consider the relationship of variations of destructive control by deleting candidates to variations of s-t vertex cut. All omitted proofs can be found in the supplementary material.

We first introduce a variant of s-t vertex cut defined by Menton and Singh [2013]: PATH-PRESERVING VERTEX CUT. Recall that for destructive control in Schulze elections to be successful, one candidate must be boosted to beat the despised candidate and that by deleting candidates we can only lower the strength of the strongest path but can never increase it. Hence, we need to cut paths such that the best remaining path to the despised candidate is stronger than all paths from the despised to our chosen boosted candidate. Menton and Singh [2013] capture this notion of pathpreserving vertex cut by defining the problem as essentially asking whether there exists an s-t vertex cut (destroying the stronger paths from s to t) of size at most k, while at least one path from t to s must remain intact. When searching for candidates to delete (so as to boost some candidate to beat the despised candidate), it is useful if we can reduce the search space. We will at times refer to these candidates as rivals of the despised candidate. For the standard control problem we show that this is indeed possible and the chair can limit the search to the in-neighborhood of the boosted candidate.

Theorem 3. If destructive control by deleting candidates is possible for a given Schulze election, then there exists some candidate c ∈ C who can beat the despised candidate w by only deleting candidates who directly beat c (i.e., are inneighbors of c in the WMG). 6

Proof. Let c ∈ C be some candidate where P(w, c) ≥ P(c,w), i.e., w has a stronger (or equally strong) path to c than the other way round. Assume that c can beat w by deleting the minimal number of candidates needed (with regards to the number necessary for making other candidates beat w). We claim that either those deleted candidates are direct neighbors of c, or there exists some other candidate c∗ ∈ C for which we can reach the same goal by deleting equally many or even fewer candidates in the neighborhood of c∗ .

First, we define some notation. Let Delcw be the minimal number of removed candidates needed to make c beat w. Note that these candidates form a path-preserving vertex cut. We say that x is before z if x is closer to w than z. Let N +(c) be the in-neighborhood of a candidate c, i.e., N +(c) contains all candidates with a direct edge to c. Finally, we define Indcw as the candidates belonging to the connected component of c as induced by the vertex cut Delcw . Intuitively, Indcw contains all candidates on stronger paths from w to c that are broken by deleting candidates and where the cut is before the candidate.

Clearly, any z∗ ∈ Indcw also beats w as first, P(z∗ , c) ≥ P(c,w) and thus P(z∗ ,w) ≥ P(c,w), and second, no path from w to z∗ with strength greater than P(c,w) can exist. It follows that |Delz∗ w | ≤ |Delcw |. We distinguish two cases.

Case 1: Indcw = ∅. Since Delcw is a minimal cut, we have Delcw ⊆ N +(c).

Case 2: Indcw ̸= ∅. Let F = {f ∈ Indcw | N +(f)∩Delcw ̸= ∅} be the set of all candidates in the connected component of c, where we deleted some candidates in the inneighborhood of c. On the one hand, if |F | = 1 we have a candidate f ∈ F who also beats w by deleting Delcw . Since Delcw is minimal, it follows that Delfw = Delcw , and therefore, for a successful control action against w, it suffices to delete from N +(f). On the other hand, if |F| > 1, then N +(f) ∩ Delcw = N +(g) ∩ Delcw for all f, g ∈ F. For a contradiction, assume there are two candidates f, g ∈ F who do not share the same inneighbors in Delcw . Deleting either N +(f) ∩ Delcw or N +(g) ∩Delcw is sufficient to make the respective candidate beat w. Since N +(f) ∩Delcw ̸= N +(g) ∩Delcw , we have a contradiction to Delcw being minimal.

This result can be used to design an algorithm for SchulzeDCDC in the nonunique-winner model, which runs in polynomial time. Unfortunately, we cannot easily transfer our algorithm to work in the unique-winner model. The complete algorithm, proof of correctness (based on Theorem 3), and further explanation as well as an example of why the algorithm cannot solve the unique-winner model can be found in the supplementary material. Intuitively, for a despised candidate d, the algorithm works by considering every candidate c ∈ C \ {d} as a possible rival of d and testing whether c is successful by considering the part of the in-neighborhood of c that intersects the stronger paths from d to c for deletion.

6 This result can be extended to any pair of candidates c, w ∈ C where P(w, c) ≥ P(c,w) and we have a yes-instance of PATHPRESERVING VERTEX CUT for the graph induced by the paths between these two candidates.

Theorem 4. In the nonunique-winner model, SchulzeDCDC is solvable in polynomial time.

For variants of destructive control, we need to encode the restriction, which is imposed on the deletion set, into the vertex cut, essentially creating corresponding new PATHPRESERVING VERTEX CUT decision problems. There are several natural restrictions one may apply to Schulze-DCDC, e.g., some candidates may be protected from deletion or labeled candidates must be deleted together. We give examples and prove the relationship to vertex cut for some of these variants in the supplementary material.

5 Exact Multimode Control and Control by Replacing

Now we turn to exact multimode control and control by replacing candidates or voters. In the former control type, the chair must adhere to alter an exact number of candidates or voters or both. In the latter, the chair must add the same number of either candidates or voters as previously have been deleted, i.e., must replace them. Lorregia et al. [2015] showed that any voting rule that is resistant to constructive control by deleting candidates and satisfies insensitivity to bottomranked candidates (IBC) [Lang et al., 2013] is also resistant to constructive control by replacing candidates. A voting rule E is said to be insensitive to bottom-ranked candidates if, given an election (C, V ) and a new candidate x, the elections (C, V ) and (C ∪ {x}, V x ), where V x is the list of votes obtained by adding x as the least preferred alternative to each vote in V , have the same winners under E. We extend their result to also apply to E-ECCAC+DC and E-ECCRC.

Table 2 provides an overview of our results. All (full) proofs omitted in this section can be found in the supplementary material.

Lemma 1. Let E be a voting rule that satisfies IBC. In both the unique- and nonunique-winner model, if E-CCDC is NPhard, then so are E-ECCAC+DC and E-ECCRC.

Proof. We reduce E-CCDC to E-ECCAC+DC and EECCRC. Let (C, V, p, k) be an instance of E-CCDC. Define C ′ = C ∪ X with X = {x1, . . . , xk}, D = {d1, . . . , dℓAC }, ℓDC = ℓRC = k, and set ℓAC ∈ N arbitrarily. Let V ′ = vXD for every v ∈ V , i.e., add all candidates from X at the bottom of every vote and then add all candidates from D at the bottom of those votes. Construct an instance (C ′ , D, V ′ , p, ℓAC, ℓDC) of E-ECCAC+DC and an instance ((C ′ , V ′ ), p, ℓRC) of E-ECCRC.

Assume we have a yes-instance of E-CCDC. Then there exists a set C d ⊂ C with |C d | ≤ ℓDC such that p wins the election (C \ C d , V ). Delete all candidates in C d and some candidates in Xd ⊆ X such that exactly ℓDC candidates were deleted and add ℓAC arbitrary candidates Da ⊆ D to the election. Since E is IBC, candidate p is a winner of the election (C ′ ∪ Da \ (C d ∪ Xd ), V ′ ) and E-ECCAC+DC is also a yes-instance.

Now assume, we have a no-instance of E-CCDC. Then there is no set C d ⊂ C with |C d | ≤ k such that p wins the election (C \ C d , V ). Since E is IBC, deleting any set of candidates from X or adding any candidate from D has no influence on the winners of the election. Thus, to make p an E winner, we need to find a set of at most ℓDC candidates in C to delete, which is impossible as E-CCDC is a no-instance. The argument for E-ECCRC is analogous.

Lemma 2. Let E be a voting rule that satisfies IBC. In both the unique- and nonunique-winner model, if E-DCDC is NPhard, then so are E-EDCAC+DC and E-EDCRC.

The same construction and proof idea used in the proof of Lemma 1 works for Lemma 2 as well.

Lemma 3. Schulze and ranked pairs are insensitive to bottom-ranked candidates.

Corollary 1. In both the unique- and nonunique-winner model, Schulze-CCRC and Ranked-Pairs-CCRC are NPcomplete.

Corollary 2. In both the unique- and nonunique-winner model, Schulze-ECCAC+DC, Schulze-ECCRC, RankedPairs-ECCAC+DC, and Ranked-Pairs-ECCRC are NPcomplete.

Corollary 3. In both the unique- and nonunique-winner model, Ranked-Pairs-EDCAC+DC, Ranked-Pairs-EDCRC, and Ranked-Pairs-DCRC are NP-complete.

Schulze and ranked pairs are equally resistant to all constructive and destructive control actions of the voter list considered in this paper.

Theorem 5. In both the unique- and nonunique-winner model, Schulze-ECCAV+DV, Schulze-CCRV, SchulzeEDCAV+DV, and Schulze-DCRV are NP-complete.

Proof sketch. We reduce from RESTRICTED EXACT COVER BY 3-SETS (RX3C) [Gonzalez, 1985]: Given a set B = {b1, . . . , b3s} with s ≥ 1 and a list S = {S1, . . . , S3s}, where Si = {bi,1, bi,2, bi,3} and Si ⊆ B for all Si ∈ S and each bj is contained in exactly three sets Si ∈ S, does there exist an exact cover, i.e., a sublist S ′ ⊆ S such that each bi ∈ B occurs in exactly one Si ∈ S ′ ?

Let ℓAV = ℓDV = s for the Schulze-ECCAV+DV and Schulze-EDCAV+DV instances we construct, and let ℓRV =

s for the Schulze-CCRV and Schulze-DCRV instances. Further, let L ≫ s be a constant much greater than s. 7 From (B, S) we construct an election (C, V ) as depicted in Figure 2. Note that candidate w is the unique winner of the election. The list of additional votes U contains one vote

Let p be the distinguished candidate for the constructive case and w be the despised candidate for the destructive case.

By adapting the above construction, we obtain the same results for ranked pairs.

Theorem 6. In both the unique- and nonunique-winner model, Ranked-Pairs-ECCAV+DV, Ranked-Pairs-CCRV, Ranked-Pairs-EDCAV+DV, and Ranked-Pairs-DCRV are NP-complete.

6 Conclusion and FutureWork

We have studied electoral control for Schulze and ranked pairs elections: After fixing a flaw in the proof of Menton and Singh [2013, Theorem 2.2] for Schulze-CCDC and extending the new construction to the unique-winner model (Section 3), we have studied variants of s-t vertex cuts in graphs that are related to destructive control by deleting candidates in Schulze elections, and have re-established a corresponding vulnerability result (Section 4). Finally, in Section 5, we established a number of resistance results for control by replacing candidates or voters and exact multimode control. Hence, our work establishes both polynomial-time algorithms and NP-completeness results. Tables 1 and 2 provide a summary of our results in the context of related known results.

However, multiple variants of destructive control of the candidate set (see Section 4), such as destructive control by adding candidates both in the unique- and nonuniquewinner model and by deleting candidates in the uniquewinner model, remain open for Schulze elections. Lastly, to the best of our knowledge, most cases of control by partition are yet to be solved for ranked pairs elections.

7 The precise value of L is not important; all that matters is that when used as an edge weight in a WMG, L is large enough, such that any edge changed by the control actions must not change in direction, i.e., the sign of the edge weight must not flip. Recall that the strength of a path in a WMG is specified as the weight of the weakest edge on the path.

Ethical Statement

The subject of this paper-electoral control-is an ethically sensitive topic. The goal of our work is not to help strategic parties to control elections but to 'audit' some voting rules with respect to their vulnerability to electoral control. In particular, our resistance results are clearly helpful to society since they may help protect society from attacks against elections, and our vulnerability results are clearly helpful to society since they can be used to avoid voting rules that are vulnerable to certain types of electoral control that realistically may occur in the context of an election. Hence, the purpose of our research is to provide detailed information on the societal impact of voting rules and to ensure transparency.

Acknowledgments

We are grateful to Ulle Endriss, Piotr Faliszewski, Edith Hemaspaandra, Lane A. Hemaspaandra, and J´er ˆome Lang for their ethical advice. We thank the anonymous reviewers for helpful comments. This work was supported in part by DFG research grant RO-1202/21-1.