# generalized_distance_bribery__21658ee7.pdf

The Thirty-Third AAAI Conference on Artiﬁcial Intelligence (AAAI-19)

Generalized Distance Bribery

Dorothea Baumeister, Tobias Hogrebe, Lisa Rey Institut f ur Informatik Heinrich-Heine-Universit at D usseldorf 40225 D usseldorf, Germany

The bribery problem in elections asks whether an external agent can make some distinguished candidate win or prevent her from winning, by bribing some of the voters. This problem was studied with respect to the weighted swap distance between two votes by Elkind et al. (2009). We generalize this deﬁnition by introducing a bound on the distance between the original and the bribed votes. The distance measures we consider include a restriction of the weighted swap distance and variants of the footrule distance, which capture some realworld models of inﬂuence an external agent may have on the voters. We study constructive and destructive variants of distance bribery for scoring rules and obtain polynomial-time algorithms as well as NP-hardness results. For the case of element-weighted swap and element-weighted footrule distances, we give a complete dichotomy result for the class of pure scoring rules.

1 Introduction

In an election in which voters inﬂuence the election s result by casting their votes they might not be the only agents interested in its outcome. A well known example of strategic inﬂuence on elections is bribery, formally introduced by Faliszewski et al. (2009) (see also the book chapter by Faliszewski and Rothe (2016)). By paying voters with a resource, e. g. money, to change their vote, an external agent tries to change the election outcome to her advantage. In the constructive case the aim is to make a speciﬁc candidate a winner of the election, while in the destructive case the briber tries to prevent a candidate from winning. Originally the number of voters that can be bribed is limited. However, there is no limitation to the amount of change within a vote. It is natural to assume that a voter s cost for changing her vote to a large extent is higher than the cost for making small adjustments. This intuition is modeled in the microbribery problem introduced by Faliszewski et al. (2009), and in the swap-bribery problem introduced by Elkind et al. (2009). In both models the briber has to pay certain prices for swaps of adjacent candidates. In order to obtain a more realistic model, we propose to imply a bound on the distance between the truthful and the bribed votes.

Copyright c 2019, Association for the Advancement of Artiﬁcial Intelligence (www.aaai.org). All rights reserved.

The idea of limiting the distance between originally cast votes and their altered versions in strategic inﬂuences is not restricted to bribery. Obraztsova and Elkind (2012) have introduced distances to manipulation, where a voter changes her vote in order to subjectively improve the election outcome. They focus on the unweighted swap distance and footrule distance, and the maximum displacement distance between the truthful and the strategic vote in the constructive case. We propose to extend the study of distances to both, the constructive and destructive bribery problem and use unweighted and weighted variants of the swap and footrule distance. One motivation for introducing a bound on the overall distance of the bribed proﬁle follows from the work by Obraztsova and Elkind (2012) on optimal manipulation. The distance between a truthful and a manipulative vote should be bounded since otherwise a manipulation may be detected more easily. In a more positive sense bribery can be seen as a form of campaign management where an external actor tries to make her desired candidate win by running speciﬁc campaigns. While the swap distance counts the inversions of pairs of candidates, it is a more realistic approach to assign a weight to a speciﬁc swap, as, in a natural election, voters are often very sure about the positioning of some candidates, while being less concerned with others. We show that different assumptions on how to calculate the weights have a crucial inﬂuence on the complexity. The restriction of element-weighted distance functions (studied by Kumar and Vassilvitskii (2010) for linear orders) assigns a weight to every candidate. The weight of a swap is the product of the corresponding candidate weights. This can be seen as an indicator of how sure a voter is about the position of a candidate in the vote. The same weight functions can also be applied to the footrule distance. Instead of inversions, here the positions a candidate is shifted by are counted. The idea is to measure the cumulative change in the candidate s standing in the vote, based on its position. In the weighted version, the inﬂuence of one candidate on the standing of another can be set by the weight function. Hence, the footrule distance is more realistic in terms of robustness or comparison of proﬁles.

We study the computational complexity of distance bribery for pure scoring rules with swap and footrule distances in the unweighted, element-weighted, and weighted case. This includes showing how to exploit the relation-

ships between the distances in order to transfer complexity results but also demonstrating the limits by giving examples for cases where the complexity differs. Weights only apply to the distances, votes remain unweighted. In particular, for the considered voting systems the destructive case is never harder than the constructive one. We present polynomial-time algorithms obtained through dynamic programming and NP-completeness results, solving a number of open questions from the literature. A detailed overview of our results is given in Section 2.2.

2 Preliminaries

An election is a pair (C, V ) with a set of candidates C and a list of voters V = (v1, . . . , vn) (also called proﬁle), where a vote vi is associated with a preference order >vi over the candidates. If the vote vi is clear from the context we omit the index or simply write >i. The set of all linear orders over the candidates in C will be denoted by L(C). The position of candidate c in vote vi will be denoted by pos(vi, c), and the candidate on position k in vote vi will be denoted by cand(vi, k). For two lists A = (a1, . . . , an) and B = (b1, . . . , bk) of votes let A B = (a1, . . . , an, b1, . . . , bk) be the concatenation of both lists. A voting rule is a function E that maps an election (C, V ) to an element of 2C. In this paper tie-breaking is not an issue since we focus on the socalled non-unique winner model, where a bribery action is successful if the designated candidate is one of the winning candidates in the constructive case and if she is none of the winners in the destructive case. However, our results can be adapted to the unique winner case by slight changes. We will consider different voting rules, all belonging to the class of scoring rules. Every scoring rule is characterized by a scoring vector α = (α1, α2, . . . , αm) with α1 α2 αm and value αj N0, for 1 j m, where m 2 is the number of candidates, and will be denoted by E α. Every candidate gets αj points according to her position j in each vote. The winners are the candidates with the maximum number of points. By score(C,V )(c) we denote the points that candidate c gets in the election (C, V ). We assume that at least two different entries in the scoring vector exist. A scoring rule for an arbitrary number of candidates is deﬁned as a series of scoring vectors for which we can determine the scoring vector for m candidates in polynomial-time depending on m. We will focus on so called pure scoring rules as deﬁned by Betzler and Dorn (2010). A pure scoring rule is a scoring rule, for which the scoring vector for m candidates can be obtained from inserting a legal entry in the vector for m 1 candidates. We call a pure scoring rule polynomially bounded, if α1 is bounded by a polynomial depending on m. This includes plurality, which gives only one point for a ﬁrst position and k-approval, where one point is given to every candidate placed in the top k positions of a vote. Accordingly this includes veto and k-veto, which give one point to all candidates but the candidate(s) in the last/last k positions who get zero points, and also Borda, characterized by the scoring vector (m 1, m 2, . . . , 1, 0) for an m-candidate election.

2.1 Distances Now we will introduce different distance measures. Formally, a distance measure d on a space A is a mapping d : A A R that fulﬁlls the following properties for all a, b, c A: (i) d(a, b) 0 (non-negativity), (ii) d(a, b) = 0 if and only if a = b (identity of indiscernibles), (iii) d(a, b) = d(b, a) (symmetry), and (iv) d(a, b) + d(b, c) d(a, c) (triangle inequality). We will focus on distances between votes. For a ﬁxed set of candidates this is a distance of the form d : L(C) L(C) R. As we will study the complexity of problems involving such distances we actually consider a family of distances (dm)m>1 that contains one distance function for each possible candidate set size m. The two basic distance measures we consider are the swap distance and the footrule distance. For two votes v and v from L(C) the swap distance swap(v, v ) counts the number of inverted pairs and is formally deﬁned as swap(v, v ) = |{(x, y) C C | x >v y and y >v x}|. Beside the swap distance, we will also consider the footrule distance. Instead of counting swaps, this distance counts the positions that a candidate needs to be shifted by to obtain the target order. The footrule distance fr(v, v ) is deﬁned as fr(v, v ) = P

y C |pos(v, y) pos(v , y)|. In addition to the well-known unweighted versions of these distance measures we also consider weighted forms. The most general form of the swap distance is the weighted swap distance which is also used for the swap bribery problem (see Elkind et al. (2009)). In order to deﬁne the weighted distance we introduce the general notion of a weight function π : C C N0, that assigns a weight to each pair of candidates. We will always assume that π(x, x) = 0 for every x C and π(x, y) = π(y, x) for every x, y C. This function is analogous to the price function in the context of swap bribery.

Deﬁnition 1 (Weighted swap/footrule distance) Let π be a weight function, the weighted swap distance between two votes v, v from L(C) is swapw π (v, v ) = P

(x,y) C C: x>vy and y>v x π(x, y), and the weighted footrule distance between v and v is frw π (v, v ) = P y C

x C: x>vy π(x, y) P

x C: x>v y π(x, y)

For matters of consistency we denote the unweighted distances by frπ and swapπ, where the weight function is π(x, y) = 1 for all x, y C, x = y. The following example illustrates how these distances are calculated.

Example 2 Consider the votes v : a > b > c > d > e and v : a > d > c > b > e. The swap distance is swap(v, v ) = |{(b, c), (b, d), (c, d)}| = 3. For a weight function π, the weighted swap distance is the sum of the weights of these pairs: swapw π (v, v ) = π(b, c) + π(b, d) + π(c, d). The unweighted footrule distance is fr(v, v ) = |2 4|+|4 2| = 4, whereas the weighted footrule distance for a weight function π is frw π (v, v ) = | π(d, b) π(c, b)|+|π(b, c) π(d, c)|+ |π(b, d) + π(c, d)|.

In addition to these general weighted distances we will consider a special weighted variant that corresponds to the

element-weighted distances described by Kumar and Vassilvitskii (2010). In the element-weighted swap/footrule distance (denoted by swapew π and frew π respectively), the function π is restricted to the form π(x, y) = ϕ(x) ϕ(y) for x y, where ϕ : C N0 is a function that assigns a weight to every candidate. While our distances are obviously heavily inspired by the weighted distances proposed by Kumar and Vassilvitskii (2010), they actually differ widely. Their distances are invariant, i. e., they are not dependent on the actual identity of each element but on the permutation between votes v and v . Our distances are not invariant for a good reason. They should depend on the identity of each candidate and the measurable differences or similarities between them. If weights of 0 are not allowed for a pair of two distinct candidates, the metric properties are still fulﬁlled for our deﬁnition of the element-weighted swap distance since it is a special case of the weighted swap distance, for which it is not hard to show these properties. For the triangle inequality, note that for a swap to appear between two candidates comparing a vote va to a vote vc this swap also has to appear comparing va to a third vote vb or vb to vc. This argument can be modiﬁed to show that the weighted footrule distance fulﬁlls the triangle inequality as well. Non-negativity, identity of indiscernibles, and symmetry are obviously also fulﬁlled by the weighted footrule distance. Note that if weights of 0 are allowed for a pair of two distinct candidates, all distance measures only fulﬁll the requirements for a pseudometric, i. e., the identity of indiscernibles is replaced by the property d(a, a) = 0. For the sake of readability we neglect identity of indiscernibles in some of our proofs. However, these proofs can be easily rewritten to fulﬁll this property. Even though the swap and footrule distances focus on different aspects of the differences between two votes, it can be shown that they are somehow related, and we will make use of this in our proofs. Lemma 3 For a set of candidates C, a weight function π over C, and v, v , v L(C) the following statements hold: swapπ(v, v ) frπ(v, v ) 2 swapπ(v, v ); (1)

swapew π (v, v ) frew π (v, v ) 2 swapew π (v, v ); (2)

2 ˆπ(v, v ) frw π (v, v ) 2 swapw π (v, v ) (3) with ˆπ(v, v ) = max{π(x, y) | x >v y and y >v x}. If v and v are 3-inversion free1, it holds that frw π (v, v ) = 2 swapw π (v, v ). (4)

The ﬁrst part is the well-known Diaconis-Graham inequality (see Diaconis and Graham (1977)). The remaining proofs can be shown by slight adaptions.

2.2 Distance Bribery Now we will deﬁne decision problems in order to study their computational complexity. For details on computational complexity we refer to the textbooks by Papadimitriou (1994) and Arora and Barak (2009). The study of the

1There is a 3-inversion between v and v if a >v b >v c and c >v b >v a for some candidates a, b, and c.

computational complexity of such manipulative actions is important, since in the context of voting in multi-agent systems it is crucial to know about the possibility of an external intervention. Of course, a worst-case complexity analysis is only the ﬁrst step and should be followed by a more ﬁnegrained analysis and the design of approximation algorithms and fast algorithms for the average case. The original bribery problem asks if for a given election a designated candidate can be turned into a winner of the election by bribing a speciﬁc number of voters, whereas the swap bribery problem (introduced by Elkind et al. (2009)) requires that the sum of the swaps weights may not exceed a budget. In the related shift bribery problem, also introduced by Elkind et al. (2009), only swaps involving the desired candidate are allowed. Note that there is a reduction of shift bribery to the element-weighted variant of our problem. However, it does not transfer any results to the problems studied in this paper. For a given distance function D and a voting rule E we deﬁne a generalization of the swap bribery problem as follows:

(D, E)-DISTANCE BRIBERY

Given: An election E = (C, V ), with V = (v1, . . . , vn), a weight function πi, 1 i n, for every voter, a positive integer K, and a distinguished candidate p C. Question: Is there a list of votes V = (v 1, . . . , v n) such that P

i {1,...,n} Dπi(vi, v i) K and p E(C, V )?

In the destructive variant (D, E)-DESTRUCTIVE DISTANCE BRIBERY we have the same input, but we ask whether there is an alternative proﬁle V = (v 1, . . . , v n) with P

i {1,...,n} Dπi(vi, v i) K and p E(C, V ). Hence, we want to prevent p from being a winner of the election. One restriction is that the weight function is identical for all voters. This follows the work on bribery where only a certain number of votes can be changed arbitrarily (see Faliszewski et al. (2009)). All our polynomial-time results obviously cover this restricted version, and we mention whether our NP-hardness results also hold in this special case. The most general problems are those for the weighted distances, while unweighted distances lead to the most restricted problems. Hence, polynomial-time algorithms for swapw π and frw π carry over to the corresponding problems for swapew π and frew π , and both to the corresponding problems for swapπ and frπ. At the same time, NP-hardness for the unweighted distances (swapπ and frπ) implies NP-hardness for the element-weighted distances (swapew π and frew π ) which in turn imply NP-hardness for the weighted distances (swapw π and frw π ). Obviously, all decision problems are contained in NP, since the winners for all voting rules considered here can be computed in polynomial time and as, given two votes, it is possible to compute all introduced distances in polynomial time. Results for the constructive and destructive variants for the different distances are summarized in Table 1. Whenever results were previously known (or follow by the above

described relations), the respective source is given. For all other cases, the number of the corresponding theorem, for which the proof is provided in this paper, is given in brackets. The results show that the introduction of weighted distances may turn the problem NP-complete. We study the scoring vector (2, 1, . . . , 1, 0), since this is a very simple scoring vector with only 3 different values. Interestingly this is an example for a scoring rule for which the result differs in the constructive case for the weighted swap distance and the weighted footrule distance. To the best of our knowledge, such a difference was not known before for other problems. Our results solve a number of open questions from the literature. Shiryaev et al. (2013) conjectured that swapw π DESTRUCTIVE DISTANCE BRIBERY is hard for many scoring rules, especially Borda and k-approval for any ﬁxed k 2. We conﬁrmed this conjecture for Borda (Corollary 11) but disproved it for k-approval (Corollary 6). Obraztsova and Elkind (2012) posed the question whether the swap bribery problem, where only one voter can be bribed, remains tractable for scoring rules. We give a negative answer in the case of Borda elections. In our NP-hardness proof of (swapw π , Borda)-DESTRUCTIVE DISTANCE BRIBERY (Theorem 10) there is only one voter that may be bribed. Thereby, the proof also shows that the corresponding optimal manipulation problem for weighted swap distances is NP-complete. In addition, Obraztsova and Elkind (2012) suggested to extend the study of optimal manipulation to other distances. Since the optimal manipulation problem is a special case of bribery where only one voter can be bribed, all our P results carry over to the corresponding optimal manipulation problems. Furthermore, all our hardness results for the destructive cases carry over, since in our reductions, there is only one voter that may be bribed.

Related Work Distance bribery is a general framework for many problems. Based on the distance used, and whether we look at the destructive or constructive variant, we get various possible motivations such as robustness (Shiryaev et al. (2013)), the standing of a non-winning candidate (Brelsford et al. (2008)), optimal manipulation (Obraztsova and Elkind (2012)), possible winner (Konczak and Lang (2005)), coalitional manipulation (Conitzer and Sandholm (2002)), tie-breaking, and so on. The use of individual prices for the change of each vote has been introduced by Faliszewski et al. (2009) for the priced bribery problem. There is however one price ﬁxed irrespective of the change in the vote. Distance restrictions on constructive and destructive bribery problems have also been studied by Yang et al. (2016) for the swap distance and the Hamming distance. The related bribery problems with distance restrictions introduced by Yang et al. additionally include an upper bound on the number of votes that can be bribed. Obviously, our hardness results also hold in this case. Since we follow the work on swap bribery we relate the upper bound of allowed bribery actions to the distance at hand. Furthermore, we consider the distance bound to be part of the input, whereas Yang et al. ﬁx it in the problem name. It is obvious that their distance restricted bribery problem

for an unlimited distance bound equals the ordinary bribery problem, as well as ours does, if one uses the discrete distance. Another difference is that Yang et al. bound the distance for each bribed voter, while we have a global bound on the distance, consistent with the swap bribery problem. Elkind et al. (2009) showed that the swap bribery problem is a generalization of the possible winner problem. In our notation the swap bribery problem corresponds to the distance bribery problem with the swapw π distance. However, there is no direct reduction for problems with other distance functions than the weighted swap distance. Even for the element-weighted swap distance their reduction no longer holds. On the one hand, our problem differs from the nonuniform bribery, which was introduced by Faliszewski (2008), since they use utility-based voting, while our deﬁnition applies to proﬁles where votes are linear orders over the candidates. On the other hand, it should be mentioned that our model can also be applied to various other preference representations, as well as to the approval vectors used by Faliszewski (2008), as long as meaningful distances can be deﬁned on that form of representation. Another related problem is the margin of victory in an election studied, e. g., by Magrino et al. (2011) and Xia (2012), and the robustness of an election studied by Shiryaev et al. (2013). They focus on the possibility to change the election winner through some changes in the votes. It is argued that the amount of change needed to obtain a different outcome can be seen as a measure for the robustness of a voting rule. Similar as for the optimal manipulation problem the motivation is again to detect fraud in elections. The latter problem is equivalent to destructive swap bribery, and the same arguments obviously apply to the bribery problem. Hence, the distance measures used in this paper also provide a way of measuring the robustness of a voting rule.

3 Results To construct relative scores in the reductions below, we use the circular block votes deﬁned by Betzler and Dorn (2010). This allows us to generate a set of votes with arbitrary scores that can be generated from the scoring vector, for an offset β and a dummy candidate d, which gets less than β points.

Destructive Distance Bribery In this section we will consistently denote the undesirable candidate as q and a possibly more preferable candidate as p. Before stating our results, we introduce a notion for the minimum necessary distance to improve the designated candidate p compared to some other candidate. For a given instance of (D, E)-DESTRUCTIVE DISTANCE BRIBERY with election (C, V ), and p, q C, let cost(C,V )(p, q, i, r) denote the minimum necessary distance to improve the relative score of p compared to q in vote vi by at least r, with 0 r α1 αm. We set cost(C,V )(p, q, i, r) to if the relative score cannot be improved by at least r.

Theorem 4 (D, E)-DESTRUCTIVE DISTANCE BRIBERY is in P for each distance function D and each polynomially bounded pure scoring rule E for which cost(C,V ) can be determined efﬁciently.

swapπ swapew π swapw π frπ frew π frw π

plurality/veto C P P P P, (12) P, (12) P, (12) D P P P P, (6) P, (6) P, (7)

k-approval C P NP-c., (16) NP-c. P, (14) NP-c., (16) NP-c., (16) D P P, (6) P, (6) P, (6) P, (6) P, (7)

(2, 1, . . . , 1, 0) C NP-c., (13) NP-c., (13) NP-c., (13) NP-c., (16) NP-c., (16) D P P, (6) P, (6) P, (6) P, (6) NP-c., (8)

Borda C NP-c., (15) NP-c., (15) NP-c. NP-c., (15) NP-c., (15) NP-c., (15) D P NP-c., (11) P, (9) NP-c., (11)

Table 1: Overview of complexity results for the constructive and destructive DISTANCE BRIBERY problems for various distances, where NP-c. stands for NP-complete. Results that were previously known (or directly follow from them) are marked by their corresponding source: Elkind et al. (2009), Dorn and Schlotter (2012), and Shiryaev et al. (2013). For all other results the reference to the corresponding theorem is given in brackets. The NP-completeness of constructive distance bribery for swapew π , frew π , swapw π , and frw π for k-approval holds for a ﬁxed k 2.

Proof. We will use the following method for each candidate p C \ {q}, to compute an overall distance minimal bribery making p better than q. To solve the decision problem, we then have to compare the minimum overall distance of the destructive bribery with the distance limit K. Given a set of candidates C with {p, q} C and a list of votes V = (v1, . . . , vn), such that score(C,V )(q) score(C,V )(p) (otherwise q is not a winner). The weight function for voter vi will be denoted by πi. Let δ = score(C,V )(q) score(C,V )(p) + 1 be the deﬁcit between q and p. The following formula is a straightforward generalization of the formula presented by Kaczmarczyk and Faliszewski (2016) for destructive shift bribery. By f(i, r) with i {1, 2, . . . , n} we denote the minimum overall distance for reducing the deﬁcit by at least r in the votes v1, v2, . . . , vi. The value of f(0, ) is only deﬁned as an initial value for technical reasons. For f it holds that

f(0, 0) = 0, f(0, g) = for g > 0, and

f(i, r) = min r r f(i 1, r r ) + cost(C,V )(p, q, i, r ) .

Therefore, the minimum necessary overall distance to eliminate the deﬁcit between p and q is given by f(n, δ) which can be determined in polynomial-time if cost(C,V ) can be determined efﬁciently. K

We apply this result and show that cost(C,V ) can be computed in polynomial time for a large class of rules.

Theorem 5 Let E be a pure scoring rule with a limited number of different values, and additionally only one value has an unlimited number of entries, then (D, E)- DESTRUCTIVE DISTANCE BRIBERY is in P for D {swapπ, swapew π , swapw π , frπ, frew π }.

Proof (sketch). First note that the above restriction on the pure scoring rule implies that it is polynomially bounded. Hence, due to Theorem 4 we only show that cost(C,V ) can be computed in polynomial time. This can indeed be done for all listed distances by a brute force approach.

For swap distances, the idea is to calculate the minimum necessary distance cost(C,V ) by looking at each possible distribution of candidates to the values. The minimum distance is obtained by placing the candidates of some value in their original order. Since there is only one value with an unlimited number of entries, the number of distributions is polynomially bounded by the number of candidates. By placing the candidates assigned to a value in the original order the minimum element-weighted footrule distance is produced. Therefore, it sufﬁces to show that every corrective swap in the unweighted footrule distance reduces or maintains the distance. This can be shown via a connection between the unweighted and element-weighted distance. K

Corollary 6 For plurality, veto, k-approval, and (2, 1, 1, . . . , 1, 0) elections (D, E)-DESTRUCTIVE DISTANCE BRIBERY is in P for D {swapπ, swapew π , swapw π , frπ, frew π }.

This corollary follows directly from Theorem 5. The approach cannot be extended to the weighted footrule distance since additional inversions can actually lower the distance. Consider the votes v : q > a > b > p, v : p > a > b > q, and v : p > b > a > q and the weight function given by π(a, b) = 4, π(a, p) = 1, π(a, q) = 4, π(b, p) = 4, π(b, q) = 1, and π(p, q) = 1. We receive the following distances: frw π (v, v ) = 18 and frw π (v, v ) = 14. Next, we show that for k-approval elections it is indeed possible to extend the approach to the weighted footrule distance. Note that for k = 1 this proof covers plurality, and a very similar approach can be used to show polynomial-time solvability for k-veto.

Theorem 7 (frw π , k-approval)-DESTRUCTIVE DISTANCE BRIBERY is in P.

Proof (sketch). Again, we will make use of Theorem 4. To adapt the proof for k-approval, it sufﬁces to show that the vote in which the candidates assigned to 1 and 0 maintain their original order respectively inﬂicts the minimum

weighted footrule distance. This holds, since one can show that correcting the leftor rightmost inversion of two adjacency candidates always lowers or maintains the weighted footrule distance. K

For (2, 1, . . . , 1, 0) elections it is indeed not possible to extend the previous result.

Theorem 8 (frw π , E(2,1,1,...,1,0))-DESTRUCTIVE DISTANCE BRIBERY is NP-complete.

Proof. NP-hardness will be shown via a reduction from the NP-complete problem SUBSET SUM (see Garey and Johnson (1979)). A SUBSET SUM instance consists of a set of integers A = {a1, a2, . . . , ah} and a positive integer T. The question is whether there exists a subset A A with P

ai A ai = T. We construct an instance of the destructive bribery problem as follows. The set of candidates is C = {p, q, s, u1, u2, . . . , uh}. The proﬁle contains the vote v1 : q > s > u1 > u2 > > uh > p and a list of votes Vd. The latter is constructed by using the circular block votes with some ui as the dummy candidate to ensure the following scores for some score offset β. The current winner of the election should be q with β + 3 points, followed by p with β points. Each other candidate should receive at most β 4 points. The weight function π1 is as follows: π1(p, ui) = ai, π1(p, s) = 0, π1(p, q) = 0, π1(q, ui) = 0, π1(q, s) = 2T, π1(s, ui) = 2ai, π1(ui, uj) = 0, for 1 i, j h. For every other voter we set the weights for every swap to K + 1, that means only v1 can be bribed. The distance limit is K = 2 P ai A ai + 2T. Since only v1 is bribable and only p can beat q, the only way of defeating q is to move p to the ﬁrst and q to the last position in v1. The resulting vote v 1 = p > s > u1 > u2 > > uh > q inﬂicts the distance frw π1(v1, v 1) = 2 P

ai A ai + 4T. Due to the weight function, the only way of lowering the distance, is to swap uis in front of s. Lowering the distance by 2T is possible if and only if there exists a subset A A, with P

ai A ai = T such that swapping each ui, where ai A , in front of s, lowers the term of s by 2T. Note that the term of each ui is not lowered by swapping with s. K

One can extend this proof to all pure scoring rules, which have two distinct values separated by entries of at least one other value, with the number of entries increasing at least linearly with a polynomial number of candidates. Next, we will consider the unweighted footrule distance.

Theorem 9 (frπ, E)-DESTRUCTIVE DISTANCE BRIBERY is in P for all pure scoring rules.

Proof. The approach used by Shiryaev et al. (2013) for the (swapπ, E)-DESTRUCTIVE DISTANCE BRIBERY regarding scoring rules, can be easily generalized to apply to all distances which are polynomially bounded depending on the number of candidates, for which one can efﬁciently determine the maximum deﬁcit reduction in a vote for a given bound on the distance. This is indeed possible for the unweighted footrule distance by testing every possible combination of positions of p and q and placing the remaining candidates according to their original order. K

We continue, by considering the destructive variant of distance bribery for Borda elections. It is known that destructive shift bribery and destructive unweighted swap bribery are in P for Borda (see, e. g., Kaczmarczyk and Faliszewski (2016) and Shiryaev et al. (2013)). In contrast we will show NP-completeness for DESTRUCTIVE DISTANCE BRIBERY for a class of pure scoring rules, including Borda, when using the weighted swap distance. We will call a pure scoring rule E separable with polynomial effort, if there exists a polynomially bounded function f : N N, so that for each integer r with m = f(r) and α as the scoring vector for m candidates the following holds: k {1, . . . , m 1} : αk > αk+1 and r k (m r). Intuitively this condition means that the candidates may be divided into two large enough groups that do not get the same number of points. The integer r determines the minimal size of these groups. Theorem 10 (D, E)-DESTRUCTIVE DISTANCE BRIBERY is NP-complete for D {swapw π , frw π } for every pure scoring rule E which is separable with polynomial effort, even if the weight functions are identical for all voters. The proof is a reduction from the NP-complete problem BALANCED BICLIQUE. The above theorem includes scoring rules like Borda, m

2 -approval and many more rules. Corollary 11 (D, Borda)-DESTRUCTIVE DISTANCE BRIBERY is NP-complete for D {swapw π , frw π }, even if the weight functions are identical for all voters.

Constructive Distance Bribery We now turn to the constructive case. For the sake of readability, candidate p will always be the candidate who should be made a winner of the election through the bribery action. Theorem 12 For plurality and veto (D, E)-DISTANCE BRIBERY is in P for D {frπ, frew π , frw π }. Proof. We show polynomial-time solvability for the weighted variant, which directly implies the results for the other two variants. Elkind et al. (2009) argue that for the bribery problem with the weighted swap distance for plurality and veto elections it sufﬁces to calculate the minimum distance for replacing the top or rearmost candidate with another speciﬁc candidate and use this value as input for the polynomial-time nonuniform-bribery algorithm by Faliszewski (2008). Hence, it is sufﬁcient to show that these values can be computed in polynomial time for the weighted footrule distance. The more general proof of Theorem 7 implies that for plurality the most efﬁcient way of transferring the points from candidate cand(vi, 1) to candidate cand(vi, j) with 2 j m is to shift cand(vi, j) to the top position while moving each candidate in between one position downwards. For veto the most efﬁcient way of transferring one point from cand(vi, j) with 1 j m 1 to cand(vi, m) is to shift cand(vi, j) downwards to position m while moving each candidate in between one position upwards. K

Theorem 13 (D, E(2,1,1,...,1,0))-DISTANCE BRIBERY is NP-complete for D {swapπ, swapew π , swapw π }, even if the weight functions are identical for all voters.

Proof. We show the result for the unweighted variant, which directly implies the results for the other two variants. NP-hardness will be shown via a reduction from the NPcomplete problem X3C (see Garey and Johnson (1979)). An X3C instance consists of a set U = {u1, . . . , u3q} of items and a family S = {S1, . . . , Sr} of 3-element subsets of U. The question is, whether there is an exact cover of U, i. e., a subset S S such that S

Si S Si = U. For the reduction, the set of candidates is given by C = U {p} {si, ci, di | 1 i r} {x1, x2, . . . , x12r}. The number of candidates is m = 3r + 12r + 3q + 1 and we assume q < r and r 5. The list of votes is V = Vs Vd. Vs contains the following three votes for each Si = {ui1, ui2, ui3}:

vi,1 :ui1 > X > > D r > si > p > dr; vi,2 :ui2 > X > > D r > dr > ci > p > si; vi,3 :ui3 > ci > X > > D r > p > dr.

Here X is a shorthand for the order x1 > > x12r, D r for the order d1 > > dr 1, and the ellipsis in the votes contains all the candidates that are not speciﬁed in the vote itself in arbitrary order. Here, β is the number of points, candidate p receives. The current winners of the election should be each uj with β + 2q + 1 points, followed by each xj, ci, and si with β + 2q points. Each dj should receive at most β points. We can construct the scores through the following votes in Vd, increasing the relative score of the selected candidate by 1 point compared to each other candidate except dr with 2 points. For p we use p > X > > D r > dr, for c {uj, ci, si} we use c > X > > D r > p > dr, and for xj we use xj > x1 > > x12r > > D r > p > dr, where x1 > > x12r does not contain xj. The distance limit is set to be K = q(2m 1). Note that decreasing the score of each xj by one point alone would increase the overall distance by at least 12r 3r > K for q < r. Therefore, the briber has to increase the score of p by at least 2q points. Since p is either already ranked at the top position or on position m 1, increasing the score of p by 2q makes 2q(m 2) additional swaps, and therefore an increase in the overall distance by at least 2q(m 2), necessary. Note that as 2q(m 2) < K < (2q + 1)(m 2), β + 2q is the maximum score that p can reach. Thus, the briber has to increase the score of p by exactly 2q while lowering the score of each uj by at least 1. We will show that p can only be made the winner while staying inside the distance limit if and only if there exists a solution to the X3C instance with the corresponding votes arranged such that

v i,1 : p > ui1 > X > > D r > dr > si;

v i,2 : p > ui2 > X > > D r > dr > si > ci;

v i,3 : ci > ui3 > X > > D r > p > dr.

This increases the distance by 2m 1. We will show that swapping p forward to the ﬁrst position in votes beside vi,1 and vi,2 makes it impossible to make p the winner while staying inside the distance limit. Note that beside swapping p upwards for an additional distance of 2q(m 2) while

possibly already reducing the score of 2q items, there is a leftover distance of 3q for reducing the score of the other uj by 1 with the cheapest way of reducing the score of an uj being 3. Reducing the score of uj by 1 by swapping it away from the last position without swapping it with p is not possible since it increases the distance by at least 15 3r (r 5) (for reducing the score of the x again). Reducing the score of uj (or any other relevant candidate) by swapping it down past d1, . . . , dr is also not an option since it increases the distance by at least 5 (r 5). In both cases we could not reduce the score of all the at least (q 1) leftover items. We can use the same argumentation to show that swapping down ui3 in vi,3 without swapping p forward to the ﬁrst position in vi,1 and vi,2 is not an option. In both cases we have to swap si down in vi,1 to swap ci down in vi,2 to swap ui3 with ci. But doing so without swapping p forward in one of the votes increases the distance by at least 4. Thereby we could not reduce the score of all the at least (q 1) leftover items. Therefore, the briber has to swap p forward in exactly q pairs of vi,1 and vi,2 exactly as shown above with swapping down ui3 in vi,3. Since it is necessary to reduce the score of each uj by one, making p the winner with respect to the distance limit is only possible if and only if there exists a solution to the X3C instance. K

Theorem 14 (frπ, k-approval)-DISTANCE BRIBERY is in P, even if k is part of the input.

Proof. This proof makes use of an algorithm proposed by Dorn and Schlotter (2012, Theorem 1) to compute a swapπ distance optimal bribery for k-approval. Let V = (v 1, . . . , v n) be the swapπ distance optimal bribery computed by the above mentioned algorithm. Since V is swapπ distance optimal each vote v i fulﬁlls the order proposed in the proof of Theorem 5 with the candidates on the top k and latter m k positions in their original order. Since each v i is 3-inversion free, it holds due to Diaconis and Graham (1977) that frπ(vi, v i ) = 2 swapπ(vi, v i ), which extends to the overall distance: Pn i=1 frπ(vi, v i ) = 2 Pn i=1 swapπ(vi, v i ). Assume there is a different frπ distance optimal bribery V = (v 1, . . . , v n) with Pn i=1 frπ(vi, v i) < Pn i=1 frπ(vi, v i ). Again, since V is distance optimal, by the proof of Theorem 7 we know that each v i fulﬁlls the 3-inversion free order proposed in the proof, so Pn i=1 frπ(vi, v i) = 2 Pn i=1 swapπ(vi, v i) holds. Substituting frπ with swapπ in the above inequality leads to Pn i=1 swapπ(vi, v i) < Pn i=1 swapπ(vi, v i ) which is a contradiction to the swapπ distance optimality of V . K

Theorem 15 (D, Borda)-DISTANCE BRIBERY is NPcomplete for D {swapπ, swapew π , swapw π , frπ, frew π , frw π }, even if the weight functions are identical for all voters.

Theorem 16 (D, E)-DISTANCE BRIBERY is NP-complete for D {swapew π , frew π } and for all pure scoring rules except plurality and veto, and for swapew π even if the weight functions are identical for all voters.

Since (D, E)-DISTANCE BRIBERY for D {swapew π , frew π } is solvable in polynomial-time for plurality and veto this completes a dichotomy result for pure scoring rules.

4 Conclusions

We introduced various forms of distances, namely weighted and unweighted versions of the swap and footrule distance, to the bribery problem in elections. We showed how the relation between the distances may be used in the proofs, but we also showed that there are limits. For (2, 1, . . . , 1, 0) we have a P result for the weighted swap distance, but NPcompleteness for the weighted footrule distance in the destructive case. On the one hand, we have shown for pure scoring rules that in the constructive case the complexities of the element-weighted and weighted problems coincide. On the other hand, for (2, 1, . . . , 1, 0) in the destructive case they differ. Regarding the open cases from Table 1, we conjecture NP-completeness for all of them. For many voting systems, which, like Borda, distinguish each position, the problem is already hard in the destructive (as well as constructive) case, even if only one voter is suggestible. Thus, the design of voting systems which are sensitive regarding the position of the candidates, combined with certain political integrity of the voters make the inﬂuence through bribery hard from a complexity theoretic point of view. This effects today s political agendas as distances can be considered in terms of campaigning and its limits. It is an interesting task to explore exactly which distance properties and which election properties are causing the jump from P to NP-completeness. As a next step the parameterized complexity of the presented problems and approximation algorithms for the hard problems should be considered in detail.

5 Acknowledgments

We thank the reviewers for their helpful comments. This work is supported by the DFG-grant BA6270/1-1.

Arora, S., and Barak, B. 2009. Computational Complexity: A Modern Approach. Cambridge University Press. Betzler, N., and Dorn, B. 2010. Towards a Dichotomy of Finding Possible Winners in Elections Based on Scoring Rules. Journal of Computer and System Sciences 76(8):812 836. Brelsford, E.; Faliszewski, P.; Hemaspaandra, E.; Schnoor, H.; and Schnoor, I. 2008. Approximability of Manipulating Elections. In Proceedings of the 23rd AAAI Conference on Artiﬁcial Intelligence, 44 49. AAAI Press. Conitzer, V., and Sandholm, T. 2002. Complexity of Manipulating Elections with Few Candidates. In Proceedings of the 18th National Conference on Artiﬁcial Intelligence, 314 319. AAAI Press. Diaconis, P., and Graham, R. 1977. Spearman s footrule as a measure of disarray. Journal of the Royal Statistical Society. Series B (Methodological) 39(2):262 268.

Dorn, B., and Schlotter, I. 2012. Multivariate Complexity Analysis of Swap Bribery. Algorithmica 64(1):126 151. Elkind, E.; Faliszewski, P.; and Slinko, A. 2009. Swap Bribery. In Proceedings of the 2nd International Symposium on Algorithmic Game Theory, 299 310. Springer-Verlag Lecture Notes in Computer Science #5814. Faliszewski, P., and Rothe, J. 2016. Control and Bribery in Voting. In Brandt, F.; Conitzer, V.; Endriss, U.; Lang, J.; and Procaccia, A., eds., Handbook of Computational Social Choice. Cambridge University Press. chapter 7, 146 168. Faliszewski, P.; Hemaspaandra, E.; Hemaspaandra, L.; and Rothe, J. 2009. Llull and Copeland Voting Computationally Resist Bribery and Constructive Control. Journal of Artiﬁcial Intelligence Research 35:275 341. Faliszewski, P.; Hemaspaandra, E.; and Hemaspaandra, L. 2009. How Hard Is Bribery in Elections? Journal of Artiﬁcial Intelligence Research 35:485 532. Faliszewski, P. 2008. Nonuniform bribery. In Proceedings of the 7th International Joint Conference on Autonomous Agents and Multiagent Systems, 1569 1572. IFAAMAS. Garey, M., and Johnson, D. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company. Kaczmarczyk, A., and Faliszewski, P. 2016. Algorithms for Destructive Shift Bribery. In Proceedings of the 15th International Joint Conference on Autonomous Agents and Multiagent Systems., 305 313. ACM Press. Konczak, K., and Lang, J. 2005. Voting Procedures with Incomplete Preferences. In Proceedings of the Multidisciplinary IJCAI-05 Worshop on Advances in Preference Handling, 124 129. Kumar, R., and Vassilvitskii, S. 2010. Generalized distances between rankings. In Proceedings of the 19th International Conference on World Wide Web, 571 580. ACM Press. Magrino, T.; Rivest, R.; Shen, E.; and Wagner, D. 2011. Computing the Margin of Victory in IRV Elections. In Proceedings of the Electronic Voting Technology Workshop/Workshop on Trustworthy. USENIX Association. Obraztsova, S., and Elkind, E. 2012. Optimal Manipulation of Voting Rules. In Proceedings of the 11th International Joint Conference on Autonomous Agents and Multiagent Systems, 619 626. IFAAMAS. Papadimitriou, C. 1994. Computational Complexity. Addison-Wesley. Shiryaev, D.; Yu, L.; and Elkind, E. 2013. On elections with robust winners. In Proceedings of the 13th International Joint Conference on Autonomous Agents and Multiagent Systems, 415 422. IFAAMAS. Xia, L. 2012. Computing the margin of victory for various voting rules. In Proceedings of the 13th ACM Conference on Electronic Commerce, 982 999. ACM Press. Yang, Y.; Shrestha, Y.; and Guo, J. 2016. How Hard Is Bribery with Distance Restrictions. In Proceedings of the 22nd European Conference on Artiﬁcial Intelligence, 363 371. IOS Press.