# approximation_and_hardness_of_shiftbribery__28774e08.pdf

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

Approximation and Hardness of Shift-Bribery

Piotr Faliszewski AGH University Krakow, Poland faliszew@agh.edu.pl

Pasin Manurangsi UC Berkeley, USA pasin@berkeley.edu

Krzysztof Sornat University of Wrocław, Poland and IDSIA, USI-SUPSI, Switzerland krzysztof.sornat@cs.uni.wroc.pl

In the SHIFT-BRIBERY problem we are given an election, a preferred candidate, and the costs of shifting this preferred candidate up the voters preference orders. The goal is to ﬁnd such a set of shifts that ensures that the preferred candidate wins the election. We give the ﬁrst polynomial-time approximation scheme for the case of positional scoring rules, and for the Copeland rule we show strong inapproximability results.

1 Introduction We provide approximation algorithms and inapproximability results for the SHIFT-BRIBERY problem, introduced by Elkind et al. (2009) to capture the idea of campaigning in elections. Brieﬂy put, we are given an election where each voter ranks the candidates from the most to the least appealing one, and our goal is to ensure that a given preferred candidate becomes the winner. To this end, we can shift this candidate up within the voters preference orders, but each such shift comes with a price (which, for example, measures the difﬁculty of convincing the voter that our candidate is more appealing than the voter originally thought). Naturally, we are interested in ﬁnding as cheap a solution as possible. In fact, bribery problems also have a number of applications beyond campaign management and voting (see, e.g., the works on the margin of victory problem (Magrino, Rivest, and Shen 2011; Cary 2011; Xia 2012) and on measuring candidate success (Faliszewski, Skowron, and Talmon 2017); see also the survey of Faliszewski and Rothe (2016)). For example, a Formula 1 season consists of about 20 races, where each race can be seen as a voter ranking the candidates (the drivers) in the order in which they ﬁnished the race. For each ﬁnishing position, there is an associated number of points and the driver who collects most points becomes the world champion (i.e., this election uses a positional scoring rule as a voting rule). We can use the SHIFT-BRIBERY problem to measure how close each driver was to winning the world championship. For example, we can set the price for shifting a driver up by some t positions in a given race to be the difference between the ﬁnishing times of the driver and whoever ranked t positions higher. Then, the cheapest shift bribery corresponds

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

to the smallest speed-up that the driver needed to become the world champion. As argued by Faliszewski et al. (2017), such values can be far more informative than the score differences between the drivers. Bribery problems also appear in the contexts of lobbying (Binkele-Raible et al. 2007; 2014), rating systems (Grandi, Stewart, and Turrini 2018), or in combinatorial domains (Baumeister et al. 2015). With the exception of a few simple voting rules, such as the k-Approval family of rules and the Bucklin rule, SHIFTBRIBERY tends to be NP-hard (see the works of Elkind et al. (2009) and Schlotter et al. (2017)). Indeed, this is the case, e.g., for Borda, Copeland, Maximin (Elkind, Faliszewski, and Slinko 2009) and various elimination-based rules (Maushagen et al. 2018). Yet, in many cases it can be solved quite effectively. For example, for the case of Borda there is a polynomial-time 2-approximation algorithm of Elkind et al. (2009; 2010) and several FPT algorithms of Bredereck et al. (2016a). On the other hand, for the case of Copeland, SHIFT-BRIBERY is W[1]-hard for many natural parameters (Bredereck et al. 2016a)1 and the best known polynomial-time approximation algorithm has linear approximation ratio (Elkind and Faliszewski 2010). In fact, the difference between the Borda rule (and, in general, the positional scoring rules) and the Copeland rule is even more striking. We show that the former can be solved nearly perfectly in polynomial time, whereas for the latter we give strong inapproximability results:

1. Our main contribution is the ﬁrst polynomial-time approximation scheme (PTAS) for SHIFT-BRIBERY for positional scoring rules (in fact, our algorithm works even for the case where the scoring vectors are different for different voters). Our algorithm uses linear programming and, in particular, basic solutions of linear programs. For the case of unit prices (i.e., for the case where each unit shift has the same cost) we even obtain an EPTAS, i.e., a PTAS for which the non-polynomial factors in the running time depend on the approximation ratio only. We also show a simple combinatorial PTAS for this case. 2. For the case of the Copeland rule, we give a reduction that preserves approximation ratios up to some polynomial from the DENSEST k-SUBGRAPH (Dk S) problem to

1One notable exception is the parametrization by the number of candidates (Knop, Kouteck y, and Mnich 2017).

SHIFT-BRIBERY. Since it is generally believed that Densest k-Subgraph is hard to approximate up to a polynomial factor (Bhaskara et al. 2012; Manurangsi 2017), the same beliefs transfer to the case of Copeland-SHIFT-BRIBERY. In particular, this gives an almost-polynomial ratio hardness of approximating Copeland-SHIFT-BRIBERY under the ETH and Gap-ETH assumptions. We also show that under Gap-ETH, Copeland-SHIFT-BRIBERY does not admit an FPT approximation scheme for the parametrization by the number of unit shifts, even for the case of unit prices, whereas for parameterizations by the number of voters and by the number of candidates such approximation schemes are known to exist (Bredereck et al. 2016a).

Together with the results of Elkind et al. (2009; 2010) and Bredereck et al. (2016a), our work gives a nearly complete view of the complexity and approximability of SHIFTBRIBERY for positional scoring rules and the Copeland rule. We omit some of the proofs due to space restrictions, but all of them are available upon request.

2 Preliminaries For each positive integer r N, we write [r] to denote the set {1, . . . , r}, and by [0] we mean the empty set. For an event X, we write 1[X] to denote the indicator function such that 1[X] = 1 if X occurs and 1[X] = 0 otherwise.

Elections. An election E = (C, V, { v}v V ) consists of a set C of m candidates, a set V of n voters, and the collection { v}v V of the voters preference orders. For each voter v, preference order v gives v s ranking of the candidates from the most to the least desirable one. For a preference order v, we write πv : [m] C to denote a function such that πv(1) v πv(2) v v πv(m) (in other words, πv(i) is the candidate that v ranks on the i-th position). Depending on the context, we either specify voters preference orders directly or via the π functions. Given two candidates c, c C, we write Vc c to denote the set of all voters v V that prefer c over c .

Voting Rules. A voting rule R is a function that for each election E = (C, V, { v}v V ) outputs the set R(E) C of this election s tied winners. We focus on the class of positional scoring rules and on the Copeland rule. Consider a setting with m candidates. Under a positional scoring rule Rw, we have a vector w = (w1, . . . , wm) Rm of point values associated with the candidate positions in the preference orders. Each voter gives each candidate the number of points associated with this candidate s position, and the candidates with the highest total score are the winners. For example, the Plurality rule uses vectors of the form (1, 0, . . . , 0), the k-Approval rule uses vectors with k ones followed by m k zeros, and the Borda rule uses vectors of the form (m 1, . . . , 1, 0). Given an election E = (C, V, { v}v V ), we sometimes speak of a positional scoring rule R(wv)v V , where each voter has a separate scoring vector wv = (wv 1, . . . , wv m). This is particularly useful, for example, to model weighted elections, where each voter v has a positive integer weight ωv and is treated as ωv copies of a unit-weight voter; then,

instead of using some rule Rw and incorporating weights directly into our algorithms, we can use rule R(ωv w)v V . As an added beneﬁt, our algorithms become more general. We will sometimes use wv ℓas a shorthand for wv ℓ wv ℓ+1. The Copeland rule is based on the idea of pairwise elections among the candidates. Let E be an election and let c, c be two candidates. By NE(c, c ) we mean the number of voters who prefer c over c . We say that a candidate c wins pairwise election against c if NE(c, c ) > NE(c , c). Similarly, we say that c ties (resp. loses) pairwise election against c if NE(c, c ) = NE(c , c) (resp. NE(c, c ) < NE(c , c)). For α [0, 1], the Copelandα rule assigns to each candidate c one point for each candidate with whom c wins a pairwise election, and α points for each candidate with whom c ties. Formally, each candidate c receives |{c C \ {c} : NE(c, c ) > NE(c , c)}| + α|{c C \ {c} : NE(c, c ) = NE(c , c)}| points. The winners are all the candidates with the maximum score. For a voting rule R, we write sc E,R(c) to denote the score that candidate c receives in election E. We sometimes drop the subscript R when it is clear from the context.

Shift-Bribery. A SHIFT-BRIBERY instance I = (E, p, ψ) consists of an election E = (C, V, { v}v V ), a preferred candidate p C, and a collection ψ = {ψv}v V of the voters price functions. Each voter v has the price function ψv : {0} [π 1 v (p) 1] R+ 0 { } and ψv(t) speciﬁes the cost of shifting the preferred candidate forward by t positions in v s preference order. We require that ψv(0) = 0 and that the function is nondecreasing (ψv(0) ψv(1) ψv(π 1 v (p) 1)). If ψv(t) = for some voter v and value t, then it is impossible to shift the preferred candidate by t or more positions in the preference order of v. For an instance I, by ψmax(I) we denote the highest non-inﬁnity price that occurs within I. We write ψv(ℓ) and |I| as shorthands for ψv(ℓ) ψv(ℓ 1) and mn, respectively. A shift action s = (sv)v V for an instance I = (E, p, ψ) of R-SHIFT-BRIBERY is a vector of non-negative integers such that for each voter v we have sv < π 1 v (p). Intuitively, this vector speciﬁes for each voter by how many positions we should shift the preferred candidate. We say that shift action s consists of P

v V sv unit shifts and we deﬁne its cost to be cost I(s) = P v V ψv(sv). We denote the election that results from applying s to E by shift(E, s). Let R be a voting rule and let I be a SHIFT-BRIBERY instance with election E and preferred candidate p. Shift action s is successful for I under R if p is an R-winner in shift(E, s), i.e., if p R(shift(E, s)). R-SHIFT-BRIBERY is an optimization problem where, given a SHIFT-BRIBERY instance I, we ask for a successful shift action with the lowest cost. We write OPT(I) to denote this lowest cost.

Special Price Functions. There are two particularly interesting families of price functions. A unit price function deﬁnes the cost of each unit shift to be one, i.e., if ψv is a unit price function then ψv(ℓ) = ℓfor each legal shift value ℓ. An all-or-nothing price function is such that the cost of shifting the preferred candidate is the same, irrespective by how many positions we shift him or her. Formally, if ψv is an all-or-nothing price function then there is a value cv

such that ψv(ℓ) = cv for all positive integers ℓthat represent legal shifts (and, of course, ψv(0) = 0). An instance I = (E, p, ψ) has (1, )-all-or-nothing prices if it has allor-nothing price functions and for each voter v the value cv is in {1, }. Given such an instance I, we deﬁne its width to be the maximum of π 1 v (p) 1 over all v V such that cv = 1. In other words, it is the maximum number of unit shifts possible to perform within a single vote by paying a unit of price.

Linear Programming. problem we are given an m n matrix A, an m-dimensional column vector b, an ndimensional column vector c, and we ask for an n dimensional column vector x that minimizes the value c T x subject to the condition that Ax b. A basic solution to such a problem is a solution x Rn such that there are n linearly independent rows ai of A with aix = bi. It is known that when {x Rn : Ax b} is bounded, there always is a basic solution that achieves the optimum, and it can be computed up to an arbitrary error in polynomial time (see, e.g., (Lau, Ravi, and Singh 2011) for the use of basic solutions in approximation algorithms).

3 Borda Rule We now move on to our results. We ﬁrst show approximation schemes for the case of the Borda rule, mostly focusing on the case of unit prices. We start with Borda because it is one of the simplest rules, for which we can present our ideas most clearly, and because it is a very practical rule (in particular, relevant to various competitions).

Initial Observations. We ﬁrst deﬁne two values that will guide our algorithms, and we explain their usefulness. Deﬁnition 1. For an instance I = (E, p, ψ) of Borda SHIFT-BRIBERY and a non-negative integer k, we deﬁne:

max-diﬀ(I) = max c C (sc E(c) sc E(p)), and

sum-diﬀ(I, k) = X

c C max{0, sc E(c) sc E(p) k}.

The former value gives the score difference between the preferred candidate and his or her strongest opponent, whereas the latter measures the total number of points that the non-preferred candidates need to lose, provided that the preferred one gains k points. Elkind et al. (2009) note that given an instance I of Borda-SHIFT-BRIBERY, if K is the smallest number of unit shifts in an optimal solution, then max-diﬀ(I)/2 K max-diﬀ(I). Indeed, if the preferred candidate gains max-diﬀ(I) points then he or she certainly matches his or her strongest opponent. On the other hand, the preferred candidate needs at least max-diﬀ(I)/2 unit shifts because each of them decreases the score difference between him or her and the strongest opponent by at most two. However, it turns out that sum-diﬀ(I, k) provides an even more useful bound. Lemma 2. Let I = (E, p, ψ) be an instance of Borda SHIFT-BRIBERY, let s be a successful shift action for I, and let ks be the number of unit shifts within s. Then, sum-diﬀ(I, ks) ks.

Proof. After applying s, the score of p is exactly sc E(p) + ks. Thus each candidate c C must have lost at least max{0, sc E(c) sc E(p) ks} points. This indeed means that ks P

c C max{0, sc E(c) sc E(p) ks} = sum-diﬀ(I, ks), as desired.

We will also make use of the following subroutine, which is based on a simple dynamic program.

Lemma 3. There exists an algorithm that given an instance I = (E, p, ψ) of Borda-SHIFT-BRIBERY, a subset C = {c1, . . . , ct} of t candidates from E, and a vector (s1, . . . , st) of non-negative integers, computes a minimum cost shift action that ensures that each candidate ci loses at least si points. The algorithm runs in polynomial time with respect to |I| + Qt i=1(si + 1).

A Combinatorial PTAS for Unit Prices. We now give a simple combinatorial PTAS for Borda-SHIFT-BRIBERY with unit prices. The main idea of our algorithm is as follows. If the optimal number of unit shifts needed is OPT, then, in total, the scores of other candidates decrease by at most OPT. This means that, once we guess OPT correctly, for each ε > 0 there can be at most 1/ε bad candidates, whose scores exceed that of the preferred candidate by more than (1+ε) OPT. Since there are only 1/ε such candidates, we can use the algorithm from Lemma 3 to compute the cheapest set of (at most) OPT unit shifts that ensure that the preferred candidate defeats these candidates. Then, we shift the preferred candidate up further ε OPT times, which ensures that p also defeats all the other candidates. In total, we use only (1 + ε) OPT shifts and hence we arrive at our PTAS for the unit prices case. This idea is formalized below.

Theorem 4. For each ε > 0, there exists an algorithm that given an instance I of Borda-SHIFT-BRIBERY with unit prices runs in time OPT(I)O(1/ε)poly(|I|) and outputs a successful shift action of cost at most (1 + ε) OPT(I).

Proof. Let I = (E, p, ψ) be an instance of Borda-SHIFTBRIBERY and let ε > 0 be the desired approximation ratio. For every k between max-diﬀ(I)/2 and max-diﬀ(I), such that sum-diﬀ(I, k) k, we execute the following steps:

1. Let Ck BAD = {c1, . . . , ct(k)} be the set of candidates whose scores are greater than sc E(p) + (1 + ε)k. We use the algorithm from Lemma 3 to ﬁnd the least-cost shift action that decreases the score of each ci Ck BAD by at least sc E(ci) sc E(p) k points. 2. If the cost of this shift action is at most k, then we perform additional arbitrary unit shifts so that the total number of unit shifts is (1 + ε)k or, if not enough unit shifts are possible, we shift p to the top of every vote. We output all the performed unit shifts and terminate.

We ﬁrst note that the algorithm indeed outputs a successful shift action. If p ends up being on top of all the votes then he or she clearly wins. On the other hand, if the total number of unit shifts performed is (1 + ε)k , then the score of p is at least sc E(p) + (1 + ε)k ; this means that, for all the candidates c / Ck BAD, the new score of p is at least sc E(c), which is at least as large as the score of c after the shifts.

Moreover, the algorithm from Lemma 3 ensures that after the shifts the score of p is at least as high as the scores of all the candidates from Ck BAD. Thus, p is a winner. Next, let us argue that the algorithm computes a (1 + ε)- approximate solution. Recall that due to the results of Elkind et al. (2009), the number of unit shifts in the optimal solution is between max-diﬀ(I)/2 and max-diﬀ(I). Therefore the algorithm must terminate at latest when considering k = OPT(I). Given this many shifts, it is by deﬁnition possible for p to obtain score higher than all the candidates from Ck BAD and, so, the algorithm from Lemma 3 returns a shift action with at most OPT(I) unit shifts. Thus the algorithm terminates with at most (1 + ε) OPT(I) unit shifts. The running time of the algorithm follows from Lemma 3 and is bounded by a polynomial in |I| and Πci Ck BAD(sc E(ci) sc E(p) k + 1) (max-diﬀ(I) + 1)t(k). However, we only invoke Lemma 3 when k sum-diﬀ(I, k). This means that:

k sum-diﬀ(I, k) = X

c C max{0, sc E(c) sc E(p) k}

(sc E(ci) sc E(p) k) > t(k)εk,

and we conclude that t(k) < 1/ε. Thus the running time is polynomial with respect to |I| + (1 + max-diﬀ(I))1/ε.

EPTAS for Unit Prices. The main result of this subsection is an EPTAS (efﬁcient polynomial-time approximation scheme) for Borda-SHIFT-BRIBERY with unit prices, that is, a PTAS for which the non-polynomial factors in the running time depend only on the required approximation ratio. Note that in the algorithm from Theorem 4 this factor was OPT(I)O(1/ε) and, thus, did not depend on ε alone. On the technical level, we ﬁrst develop an algorithm that for an instance I of Borda-SHIFT-BRIBERY with unit prices outputs a solution with cost at most OPT(I) + p

OPT(I). Lemma 5. There is a polynomial-time algorithm that, given an instance I of Borda-SHIFT-BRIBERY with unit prices, outputs a successful shift action with cost at most OPT(I)+ p

OPT(I). Using this algorithm and the combinatorial PTAS from Theorem 4, we obtain our EPTAS (in short, if max-diﬀ(I) < 2/ε2 then we run the algorithm from Theorem 4 and we run the algorithm from Lemma 5 otherwise). Theorem 6. There is an algorithm that, given an instance I of Borda-SHIFT-BRIBERY with unit prices and a positive number ε > 0, runs in time 2O(log(1/ε)/ε)poly(|I|) and outputs a successful shift action of cost at most (1+ε) OPT(I). Theorem 6 gives formal evidence that approximating Borda-SHIFT-BRIBERY is computationally easier for the case of unit prices than for the general case or, even, for the all-or-nothing prices case. The latter cases are W[1]- hard when parameterized by the budget (Bredereck et al. 2016a) and this means that no EPTAS exists for them unless W[1] = FPT. If there were an EPTAS for Borda-SHIFTBRIBERY for the case of general prices, or for the all-ornothing prices, which ran in time f(ε)n O(1), then we could

j [π 1 v (p) 1] x(v,j) s.t.:

0 x(v,1) x(v,π 1 v (p) 1) 1 , v V, (1) X

v Vc p x(v,π 1 v (c)) sc E(c) sc E(p) k, c Ck BAD. (2)

Figure 1: Program LP-U(I, k) from the proof of Lemma 5. For each voter v, we have variables x(v,1), . . . , x(v,π 1 v (p) 1). Constraints (1) ensure that an integral solution describes a valid shift action and Constraints (2) ensure that after applying such an action, each candidate in Ck BAD has score no higher than p; recall that Vc p means the set of voters that prefer c to p. The optimization goal is to minimize the number of unit shifts in the shift action.

plug in ε = 1/(2B), where B would be the budget limit, and solve the problem exactly in time f( 1

2B )n O(1), implying that W[1] = FPT. Such connections between FPT algorithms and EPTASes are well-known in theoretical computer science (Cesati and Trevisan 1997), but, so far, have not found many applications in computational social choice. Let us now move on to the proof of Lemma 5. The general structure of our algorithm is similar to that of the algorithm from Theorem 4, but instead of invoking Lemma 3, we solve a linear program. We form this program in such a way that its basic solution has to consist almost entirely of integral values. Then, rounding and complementing the obtained shift action with arbitrary unit shifts gives the desired solution. To state our linear program, we will model shift actions as boolean matrices (x(v,j))v V,j [m] such that x(v,j) is 1 if after applying the shift action the preferred candidate is ranked on position j or better in vote v, and it is 0 otherwise (so we will always have 0 x(v,1) x(v,2) x(v,m) 1). Formally, a shift action s = (sv)v V corresponds to the boolean matrix x(v,j) = 1[π 1 v (p) sv j].

Proof of Lemma 5. Let I = (E, p, ψ) be an instance of Borda-SHIFT-BRIBERY with unit prices, where E = (C, V, { v}v V (E)). We try all integers k between max-diﬀ(I)/2 and max-diﬀ(I), such that sum-diﬀ(I, k) k, and for each of them we perform the following steps:

1. We form the set Ck BAD C of those candidates c whose scores exceed value sc E(p) + k +

k. 2. We form the linear program LP-U(I, k) from Figure 1 and solve it for a basic solution (note that the objective function gives the number of unit shifts used). If LP-U(I, k) is infeasible or the cost of the solution exceeds k, then we skip this value of k. Let (x OPT (v,j))v V,j [π 1 v (p) 1] be the basic optimal solution found. 3. Let s LP be the shift action corresponding to ( x OPT (v,j) )v V,j [π 1 v (p) 1]. (Note that the rounded

solution indeed correctly describes a shift action and that its cost, i.e., the number of unit shifts it contains, is at most k.) Form a shift action s by extending s LP so that it contains k +

k unit shift or, if this is impossible, then so that p is on the top of every preference order. Output s and terminate.

Since ﬁnding basic solutions for linear programs can be done in polynomial time, the whole algorithm runs in polynomial time. Further, the cost of the computed shift action s is at most OPT(I) + p

OPT(I) unit shifts. To see this, consider the step when the algorithm tries k = OPT(I); if it terminates earlier then our claim certainly is satisﬁed. For this value of k, LP-U(I, k) certainly has a solution of cost at most k because an optimal successful shift action for I is one of its feasible solutions. Thus the algorithm terminates for this value of k and (in Step 3) outputs a shift action with at most OPT(I) + p

OPT(I) unit shifts. It remains to show that the computed shift action s is successful. If p ends up at the top of every preference order, then surely s is a successful shift action. Let us consider the case where s consists of exactly k +

k unit shifts, i.e., where after applying s, p has score sc E(p) + k +

k , for the value of k for which the algorithm terminates. Since prior to applying s each candidate c / Ck BAD had score at most sc E(p) + k +

k , after applying s candidate p certainly has score at least as high as theirs. Thus we only need to show that each candidate in Ck BAD also ends up with score at most sc E(p) + k +

k . Let us say that a voter v V is integral if x OPT (v,j) {0, 1} for all j [π 1 v (p) 1] and let Vint be the set of all integral voters. Since (x OPT (v,j))v V,j [π 1 v (p) 1] is a basic solution of LP-U(I, k), at least P

v V (π 1 v (p) 1) inequalities must be tight. For each integral voter v, exactly π 1 v (p) 1 inequalities of the form (1) are tight. On the other hand, for each non-integral voter v, at most π 1 v (p) 2 inequalities in (1) are tight. Further, there are |Ck BAD| inequalities of the form (2) and |Ck BAD|

k , because each candidate c Ck BAD contributes at least

k points to sum-diﬀ(I, k) and sum-diﬀ(I, k) k. Altogether, this means that there are at most

k non-integral voters, i.e., |V \Vint|

k . Intuitively, each tight inequality of the form (2) can lead to at most a single non-integral voter. For each c Ck BAD, the score of c after applying s LP is as follows (for a number x, 0 x 1, by frac(x) we mean its fractional part, so that if 0 x < 1 then frac(x) = x and if x = 1 then frac(x) = 0):

j x OPT (v,π 1 v (c))

= sc E(c) X

v Vc p x OPT (v,π 1 v (c)) + X

v Vc p frac x OPT (v,π 1 v (c))

(2) sc E(p) + k + P v Vc p frac x OPT (v,π 1 v (c))

= sc E(p) + k + P v Vc p\Vint frac x OPT (v,π 1 v (c))

sc E(p) + k + |V \ Vint| sc E(p) + k +

This means that p is indeed a winner of the election.

Uniform All-or-Nothing Prices. In addition to the above PTASes, we devise a simple greedy algorithm for the special case. The main idea is to simply shift the preferred candidate p to the top in the votes where p is ranked lowest.

Theorem 7. Borda-SHIFT-BRIBERY with uniform all-ornothing prices is NP-hard and there is a greedy algorithm that gives 1.5-approximate solution in polynomial time.

4 Positional Scoring Rules In this section we give our main result: A PTAS for the case of SHIFT-BRIBERY with an arbitrary positional scoring rule, whose scoring vectors are, possibly, different for different voters, and for arbitrary prices.

Theorem 8. There is an algorithm that given ε > 0 and an instance I of R-SHIFT-BRIBERY, where R is a given positional scoring rule with a possibly different scoring vector for each voter, outputs a successful shift action for I of cost at most (1 + ε) OPT(I) and runs in time |I|O(1/ε2).

We remark that a corollary of Theorem 8 is a PTAS for Borda-SHIFT-BRIBERY (for arbitrary prices).

An Algorithm with Additive Error. The crucial part of our algorithm is an approximation algorithm that yields a good solution in the case where ψmax(I), the highest noninﬁnite price in the instance, is small.

Lemma 9. There is an algorithm that given ε > 0 and an instance I of R-SHIFT-BRIBERY, where R is a given positional scoring rule with a possibly different scoring vector for each voter, outputs a successful shift action for I of cost at most (1 + ε) OPT(I) + (1 + 1/ε)ψmax(I) and runs in time |I|O(1).

The main complication in the general prices case, as opposed to the unit prices case, is that the cost of obtaining some k + 1 points for the preferred candidate can be far larger than the cost of obtaining k points. Thus the main trick used in the proofs from the previous section deciding up front how many more points than in an optimal solution the preferred candidate would get cannot be directly applied. We work around this problem by ﬁrst solving a linear program which, roughly speaking, for a given value ε > 0 tells us how many extra points the preferred candidate needs to ensure so that he or she has score higher than all but at most 1/ε candidates. Then, using a technique similar to the one we used for Lemma 5 in particular, solving a second linear program, for which a basic solution contains a large number of integral variables we ﬁnd our approximate solution.

Proof of Lemma 9. We ﬁrst describe the somewhat nonintuitive algorithm, then we explain its workings and argue why it produces the desired approximate solution. Let I = (E, p, ψ) be an instance of R-SHIFT-BRIBERY, where E = (C, V ) is an election, p is the preferred candidate, and ψ = {ψv}v V (E) is a collection of price functions. Further,

j [π 1 v (p) 1] ψv(π 1 v (p) j) x(v,j) s.t.:

0 x(v,1) x(v,π 1 v (p) 1) = x(v,π 1 v (p)) = = x(v,m) = 1 , v V (3)

v Vc p wv π 1 v (c) x(v,π 1 v (c))

sc E(p) + X

j [π 1 v (p) 1] wv j x(v,j) , c C (4)

Figure 2: LP1 for the proof of Lemma 9. For each voter v, we have variables x(v,1), . . . , x(v,m). For an integral solution, Constraints (3) ensure that the variables specify a shift action, Constraints (4) ensure that this shift action is successful, and the optimization goal speciﬁes its cost.

j [π 1 v (p) 1] ψv(π 1 v (p) j) y(v,j) s.t.:

0 y(v,1) y(v,jv 1) y(v,jv) = = y(v,m) = 1 , v V (5)

v Vc p wv π 1 v (c) y(v,π 1 v (c)) sc E(p) + P

j [π 1 v (p) 1] wv j y(v,j), c CBAD (6) P

j [π 1 v (p) 1] wv j y(v,j)

j [π 1 v (p) 1] wv j y (v,j) (7)

Figure 3: LP2 for the proof of Lemma 9. For each voter v, we have variables y(v,1), . . . , y(v,m). For an integral solution, Constraints (5) ensure that the variables specify a shift action that pushes p at least as far as shift action s does, Constraints (6) ensure that p s score at least matches the scores of candidates in CBAD, and Constraint (7) ensures that p s score is higher than the scores of candidates not in CBAD.

let R be a positional scoring rule speciﬁed via scoring vectors (wv)v V (with one vector for each voter in V ). Our algorithm proceeds as follows:

1. We solve linear program LP1 from Figure 2. Let (x OPT (v,j))v V,j [m] be the computed optimal solution found for this program. Note that the value of the optimization goal for LP1 is at most OPT(I), because this would be the cost of an optimal integral solution. 2. For every v V, j [m], we let y (v,j) = min{1, (1 + ε)x OPT (v,j)}, and we let jv [m] be the smallest index such that y (v,jv) = 1. Intuitively, the shift action s that for each voter v shifts p to position jv is our ﬁrst order approximation of the shift action that we will eventually

produce; its cost is at most (1 + ε) OPT(I) but after applying it, p s score might still be lower than that of some of the candidates. Formally, we deﬁne set CBAD to contain all the candidates c such that:

v Vc p wv π 1 v (c) 1[π 1 v (c) jv]

> sc E(p) + X

j [π 1 v (p) 1] wv j y (v,j)

On the left-hand side of the above equation, candidate c loses as many points as indicated by shift action s , but the score of p, on the right-hand side, is computed with respect to the possibly fractional values y (v,j). 3. We solve linear program LP2 from Figure 3 for an optimal, basic solution (y OPT (v,j))v V,j [m]. We output shift action s that corresponds to ( y OPT (v,j) )v V,j [m].

The algorithm certainly runs in polynomial time. Let us now explain why the shift action that it outputs indeed ensures that p is a winner. Foremost, due to Constraints (5), shift action s (weakly) dominates s (i.e., for each voter it shifts p at least as far as s does). Thus, after applying s, each opponent of p who is not in CBAD has score at most as high as in the left-hand side of Equation (8). Constraint (7) ensures that p obtains at least as high a score as on the right-hand side of Equation (8) and, thus, p does not lose against any candidate not in CBAD. On the other hand, Constraints (6) ensure that p does not lose against anyone in CBAD. It remains to argue that cost I(s) is at most as required in the lemma. To this end, we ﬁrst claim that |CBAD| < 1/ε (we omit the technical proof due to space restriction). We now proceed to bound cost I(s). First, observe that an optimal integral solution for LP1 has cost OPT(I) and, thus, for our optimal, but perhaps non-integral, solution (x(v,j))v V,j [m] we have: P

j [π 1 v (p) 1] ψv(π 1 v (p) j)x OPT (v,j) OPT(I). (9)

For each voter v V , we say that v is integral if y OPT (v,j) {0, 1} for all j [m]. Let Vint denote the set of all integral voters. Recall that (y OPT (v,j))v V,j [m] is a basic solution for LP2, meaning that at least mn linearly independent inequalities must be tight (because we have mn variables).2 For each non-integral voter v / Vint, only at most m 1 linearly independent inequalities in (5) are tight. However, there are only 1 + |CBAD| < 1 + 1/ε inequalities of the form (6) and (7). From this, we can conclude that less than 1 + 1/ε voters are not integral, i.e.:

|V \ Vint| < 1 + 1/ε. (10)

As a result, we have that cost I(s) equals: P

j [π 1 v (p) 1] ψv(π 1 v (p) j) y OPT (v,j)

2We stress here that the inequalities must be linearly independent because in Constraint (5) we have equalities, each deﬁned by two linearly dependent inequalities; satisfying such an equality counts as only one tight inequality for a basic solution.

j [π 1 v (p) 1] ψv(π 1 v (p) j) y OPT (v,j) + P

v V \Vint P

j [π 1 v (p) 1] ψv(π 1 v (p) j) y OPT (v,j) .

Now, observe that the ﬁrst summation on the right hand side is upper bounded by the optimum of LP2. Note that (y (v,j))v V,j [m] is a solution to LP2. Hence, we have:

cost I(s) P v V P

j [π 1 v (p) 1] ψv(π 1 v (p) j)y (v,j) + P

v V \Vint P

j [π 1 v (p) 1] ψv(π 1 v (p) j) y OPT (v,j)

j [π 1 v (p) 1] ψv(π 1 v (p) j) x OPT (v,j) + P v V \Vint P

j [π 1 v (p) 1] ψv(π 1 v (p) j) y OPT (v,j)

(9) (1 + ε) OPT(I)

+ P v V \Vint P

j [π 1 v (p) 1] ψv(π 1 v (p) j) y OPT (v,j) .

Now, observe that for each v V , if P

j [π 1 v (p) 1] ψv(π 1 v (p) j) y OPT (v,j) is , then OPT(I) must also be and the inequality we try to prove is trivially true. Hence, we may assume that P

j [π 1 v (p) 1] ψv(π 1 v (p) j) y OPT (v,j) is ﬁnite; in this case, this quantity is bounded by ψmax(I). As a result, we can further bound cost I(s) by

cost I(s) (1 + ε) OPT(I) + |V \ Vint| ψmax(I)

(10) (1 + ε) OPT(I) + (1 + 1/ε)ψmax(I),

which concludes our proof.

The Final PTAS. Now we use the approximation algorithm with additive error to derive an approximation algorithm with a purely multiplicative ratio. Since the algorithm from Lemma 9 works well when ψmax(I) is small, we will ﬁrst preprocess our instance so that ψmax(I) is much smaller than OPT(I). To do so, note that if we consider an optimal shift action s OPT, then there are only a few voters v such that ψv(s OPT v ) is large; speciﬁcally, for every δ > 0, only at most 1/δ voters have ψv(s OPT v ) δ OPT(I). This means that if we guess such voters and the numbers of unit shifts that we apply to them, then we can reduce the instance I to another instance I , where ψmax(I ) is bounded by δ OPT(I). We then run the algorithm from Lemma 9 on I . By selecting δ = O(ε2), the additive error becomes O((δ/ε) OPT(I)) = O(ε OPT(I)) as intended.

5 Copeland For the case of Copelandα family of rules, we show that the SHIFT-BRIBERY problem is hard to approximate even for the unit prices and for the all-or-nothing prices. Specifically, we show that an approximation algorithm for the Copelandα-SHIFT-BRIBERY implies an approximation algorithm for the DENSEST-k-SUBGRAPH problem, which is believed to be hard to approximate (Bhaskara et al. 2012). Deﬁnition 10. In the DENSEST-k-SUBGRAPH (Dk S) problem, we are given an undirected graph G = (VG, EG) and a positive integer k, and the goal is to output a k-vertex subgraph of G with as many edges as possible.

Theorem 11. Let τ be an arbitrary non-decreasing function. If there is a polynomial time τ(|I|)-approximation algorithm for Copelandα-SHIFT-BRIBERY for some α [0, 1], for the case of unit prices or all-or-nothing prices, then there is a polynomial time O(τ(|VG|O(1))2)- approximation algorithm for the Dk S.

Although hardness of approximation of Dk S within up to polynomial factor is not known, inapproximability up to almost polynomial factor is known assuming the exponential time hypothesis (ETH) and its gap version (Gap-ETH).3 Speciﬁcally, Manurangsi (2017) has shown that under the ETH assumption (the Gap-ETH assumption, respectively), DENSEST-k-SUBGRAPH is hard to approximate to within a factor of n1/poly(log log n) (no(1), respectively). Together with Theorem 11, this implies the following corollary.

Corollary 12. Assuming ETH, for some constant c > 0 there is no polynomial-time |I|1/(log log |I|)c-approximation algorithm for Copelandα-SHIFT-BRIBERY for any α > 0, even for unit prices or all-or-nothing prices. Moreover, assuming Gap-ETH, the inapproximability ratio can be improved to |I|f(|I|) for any function f = o(1).

For the parametrization by the number of unit shifts, assuming Gap-ETH implies that there is no FPT approximation scheme for the problem even for the case of unit prices.

Theorem 13. Assuming Gap-ETH, for every α [0, 1], every ε > 0, and every computable function T, there is no algorithm that given a Copelandα-SHIFT-BRIBERY instance I with unit prices, runs in time T(OPT(I)) poly(|I|) and outputs a successful shift action with at most (2 ε) OPT(I) unit shifts.

We are not aware of a constant factor FPT approximation algorithms for the problem and it is possible that the factor 2 above can be improved to larger constants, or even beyond a constant. This remains an interesting open question.

6 Conclusions

We have given the ﬁrst PTAS for SHIFT-BRIBERY for the case of positional scoring rules, and we have shown severe limitations regarding approximability of CopelandαSHIFT-BRIBERY. We have also shown more efﬁcient versions of our algorithms for the case of the Borda rule with unit prices. Our PTAS improves upon the 2-approximation algorithm of Elkind and Faliszewski (2010), but their algorithm is quite robust and was used, e.g., for combinatorial shift bribery (Bredereck et al. 2016b) and bribery in approval elections (Faliszewski, Skowron, and Talmon 2017). It may be possible to apply our technique in these settings as well. Another interesting direction is to see whether our ideas can be applied to the BRIBERY problem, where the goal is to minimize the number of bribed voters but we are allowed

3ETH (Impagliazzo and Paturi 2001; Impagliazzo, Paturi, and Zane 2001) states that there is no subexponential time algorithm that solves 3SAT. Gap-ETH (Dinur 2016; Manurangsi and Raghavendra 2017) states that no subexponential time algorithm can distinguish between a satisﬁable 3CNF formula and one which is only (1 δ)-satisﬁable for some absolute constant δ > 0.

to change each bribed voter s preference arbitrarily. On this front, Keller et al. (2018) give a PTAS for the problem for Borda, t-approval, and, more generally, any scoring rules that satisfy a certain technical condition. It remains open whether a PTAS exists for all scoring rules.

Acknowledgments Piotr Faliszewski was supported by AGH University statutory research grant 11.11.230.337. Pasin Manurangsi was supported by NSF Awards CCF-1813188 and CCF-1815434. Krzysztof Sornat was partially supported by the National Science Centre, Poland, grant number 2015/17/N/ST6/03684 and the SNSF Grant APPROXNET 200021 159697/1. We would like to thank the anonymous reviewers for their helpful comments.

References Baumeister, D.; Erd elyi, G.; Erd elyi, O. J.; and Rothe, J. 2015. Complexity of Manipulation and Bribery in Judgment Aggregation for Uniform Premise-Based Quota Rules. Math. Soc. Sci. 76:19 30. Bhaskara, A.; Charikar, M.; Vijayaraghavan, A.; Guruswami, V.; and Zhou, Y. 2012. Polynomial Integrality Gaps for Strong SDP Relaxations of Densest k-Subgraph. In Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2012), 388 405. Binkele-Raible, D.; Erd elyi, G.; Fernau, H.; Goldsmith, J.; Mattei, N.; and Rothe, J. 2007. On Complexity of Lobbying in Multiple Referenda. Review of Economic Design 11(3):217 224. Binkele-Raible, D.; Erd elyi, G.; Fernau, H.; Goldsmith, J.; Mattei, N.; and Rothe, J. 2014. The Complexity of Probabilistic Lobbying. Discrete Optimization 11:1 21. Bredereck, R.; Chen, J.; Faliszewski, P.; Nichterlein, A.; and Niedermeier, R. 2016a. Prices Matter for the Parameterized Complexity of Shift Bribery. Inf. Comput. 251:140 164. Bredereck, R.; Faliszewski, P.; Niedermeier, R.; and Talmon, N. 2016b. Large-Scale Election Campaigns: Combinatorial Shift Bribery. J. Artif. Intell. Res. 55:603 652. Cary, D. 2011. Estimating the Margin of Victory for Instant-Runoff Voting. In Proceedings of Electronic Voting Technology Workshop/Workshop on Trustworthy Elections (EVT/WOTE 2011). Cesati, M., and Trevisan, L. 1997. On the Efﬁciency of Polynomial Time Approximation Schemes. Inf. Process. Lett. 64(4):165 171. Dinur, I. 2016. Mildly Exponential Reduction from Gap 3SAT to Polynomial-Gap Label-Cover. Electronic Colloquium on Computational Complexity (ECCC) 23:128. Elkind, E., and Faliszewski, P. 2010. Approximation Algorithms for Campaign Management. In Proceedings of the 6th International Workshop on Internet and Network Economics (WINE 2010), 473 482. Elkind, E.; Faliszewski, P.; and Slinko, A. M. 2009. Swap Bribery. In Proceedings of the 2nd International Symposium on Algorithmic Game Theory (SAGT 2009), 299 310.

Faliszewski, P., and Rothe, J. 2016. Control and Bribery in Voting. In Handbook of Computational Social Choice. Cambridge Univ. Press. 146 168. Faliszewski, P.; Skowron, P.; and Talmon, N. 2017. Bribery as a Measure of Candidate Success: Complexity Results for Approval-Based Multiwinner Rules. In Proceedings of the 16th Conference on Autonomous Agents and Multi Agent Systems (AAMAS 2017), 6 14. Grandi, U.; Stewart, J.; and Turrini, P. 2018. The Complexity of Bribery in Network-Based Rating Systems. In Proceedings of the 32nd AAAI Conference on Artiﬁcial Intelligence (AAAI 2018), 1047 1054. Impagliazzo, R., and Paturi, R. 2001. On the Complexity of k-SAT. J. Comput. Syst. Sci. 62(2):367 375. Impagliazzo, R.; Paturi, R.; and Zane, F. 2001. Which Problems Have Strongly Exponential Complexity? J. Comput. Syst. Sci. 63(4):512 530. Keller, O.; Hassidim, A.; and Hazon, N. 2018. Approximating Bribery in Scoring Rules. In Proceedings of the 32nd AAAI Conference on Artiﬁcial Intelligence (AAAI 2018), 1121 1129. Knop, D.; Kouteck y, M.; and Mnich, M. 2017. Voting and Bribing in Single-Exponential Time. In Proceedings of the 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017), 46:1 46:14. Lau, L. C.; Ravi, R.; and Singh, M. 2011. Iterative Methods in Combinatorial Optimization. Cambridge Univ. Press, 1st edition. Magrino, T. R.; Rivest, R. L.; and Shen, E. 2011. Computing the Margin of Victory in IRV Elections. In Proceedings of Electronic Voting Technology Workshop/Workshop on Trustworthy Elections (EVT/WOTE 2011). Manurangsi, P., and Raghavendra, P. 2017. A Birthday Repetition Theorem and Complexity of Approximating Dense CSPs. In Proceedings of the 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017), 78:1 78:15. Manurangsi, P. 2017. Almost-Polynomial Ratio ETHHardness of Approximating Densest k-Subgraph. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2017), 954 961. Maushagen, C.; Neveling, M.; Rothe, J.; and Selker, A. 2018. Complexity of Shift Bribery in Iterative Elections. In Proceedings of the 17th International Conference on Autonomous Agents and Multi Agent Systems (AAMAS 2018), 1567 1575. Schlotter, I.; Faliszewski, P.; and Elkind, E. 2017. Campaign Management Under Approval-Driven Voting Rules. Algorithmica 77(1):84 115. Xia, L. 2012. Computing the Margin of Victory for Various Voting Rules. In Proceedings of the 13th ACM Conference on Electronic Commerce (EC 2012), 982 999.