# frugal_bribery_in_voting__67014cd5.pdf

Frugal Bribery in Voting

Palash Dey Indian Institute of Science Bangalore, India palash@csa.iisc.ernet.in

Neeldhara Misra Indian Institute of Technology Gandhinagar, India mail@neeldhara.com

Y. Narahari Indian Institute of Science Bangalore, India hari@csa.iisc.ernet.in

Bribery in elections is an important problem in computational social choice theory. We introduce and study two important special cases of the bribery problem, namely, FRUGALBRIBERY and FRUGAL-$BRIBERY where the briber is frugal in nature. By this, we mean that the briber is only able to influence voters who benefit from the suggestion of the briber. More formally, a voter is vulnerable if the outcome of the election improves according to her own preference when she accepts the suggestion of the briber. In the FRUGAL-BRIBERY problem, the goal is to make a certain candidate win the election by changing only the vulnerable votes. In the FRUGAL- $BRIBERY problem, the vulnerable votes have prices and the goal is to make a certain candidate win the election by changing only the vulnerable votes, subject to a budget constraint. We show that both the FRUGAL-BRIBERY and the FRUGAL- $BRIBERY problems are intractable for many commonly used voting rules for weighted as well as unweighted elections. These intractability results demonstrate that bribery is a hard computational problem, in the sense that several special cases of this problem continue to be computationally intractable. This strengthens the view that bribery, although a possible attack on an election in principle, may be infeasible in practice.

Introduction In a typical voting scenario, we have a set of candidates and a set of voters reporting their votes which are complete rankings over the candidates. A voting rule is a procedure that, given a collection of votes, chooses one candidate as the winner. A set of votes over a set of candidates along with a voting rule is called an election. Activities that try to influence voter opinions, in favor of specific candidates, are very common during the time that an election is in progress. For example, in a political election, candidates often conduct elaborate campaigns to promote themselves among a general or targeted audience. An extreme illustration of this phenomenon is bribery here, the candidates may create financial incentives to sway the voters. Of course, the process of influencing voters may involve costs even without the bribery aspect; for instance, a typical political campaign entails considerable expenditure. All situations involving any attempt to influence voters usually have the following aspects: an external agent, a

Copyright c 2016, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.

candidate that the agent would like to be the winner, a budget constraint, a cost model for a change of vote, and knowledge of the existing election. The formal computational problem that arises from these inputs is the following: is it possible to make a distinguished candidate win the election in question by incurring a cost that is within the budget? This question, with origins in (Faliszewski, Hemaspaandra, and Hemaspaandra 2006; 2009; Faliszewski et al. 2009), has been subsequently studied intensely in computational social choice literature (Faliszewski 2008; Elkind, Faliszewski, and Slinko 2009; Baumeister et al. 2012; Pini, Rossi, and Venable 2013; Dorn and Kr uger 2015; Mattei et al. 2012; 2013; Binkele-Raible et al. 2014; Erdelyi, Hemaspaandra, and Hemaspaandra 2014; Faliszewski et al. 2015; Xia 2012; Dorn and Schlotter 2012; Bredereck et al. 2014; Faliszewski, Hemaspaandra, and Hemaspaandra 2011; Schlotter, Faliszewski, and Elkind 2011).

In this work, we propose an effective cost model for the bribery problem. Even the most general cost models that have been studied in the literature fix absolute costs per voter-candidate combination, with no specific consideration to the voters opinions about the current winner and the distinguished candidate whom the briber wants to be the winner. In our proposed model, a change of vote is relatively easier to effect if the change causes an outcome that the voter would find desirable. Indeed, if the currently winning candidate is, say, a, and a voter is (truthfully) promised that by changing her vote from c d b a to d b c a, the winner of the election would change from a to d, then this is a change that the voter is likely to be happy to make. While the change does not make her most favorite candidate win the election, it does improve the result from her point of view. Thus, given the circumstances (namely that of her least favorite candidate winning the election), the altered vote serves the voter better than the original one. We believe this perspective of voter influence is an important one to study. The cost of a change of vote is dependent on the nature of the outcome that the change promises the cost is low or nil if the change results in a better outcome with respect to the voter s original ranking, and high or infinity otherwise. A frugal agent only approaches voters of the former category, thus being able to effectively bribe with

Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence (AAAI-16)

minimal or no cost. Indeed the behavior of agents in real life is often frugal. For example, consider campaigners in favor of a relatively smaller party in a political election. They may actually target only vulnerable voters due to lack of human and other resources they have at their disposal. More formally, let c be the winner of an election and p (other than c) the candidate whom the briber wishes to make the winner of the election. Now the voters who prefer c to p will be reluctant to change their votes, and we call these votes non-vulnerable with respect to p we do not allow these votes to be changed by the briber, which justifies the frugal nature of the briber. On the other hand, if a voter prefers p to c, then it maybe very easy to convince her to change her vote if doing so makes p win the election. We name these votes vulnerable with respect to p. When p is clear from the context, we simply call these votes non-vulnerable and vulnerable, respectively. The computational problem is to determine whether there is a way to make the candidate p win the election by changing only those votes that are vulnerable with respect to p. We call this problem FRUGAL-BRIBERY. Note that there is no cost involved in the FRUGAL-BRIBERY problem. We also extend this basic model to a more general setting where each vulnerable vote has a certain nonnegative integer price which may correspond to the effort involved in approaching these voters and convincing them to change their votes. We also allow for the specification of a budget constraint, which can be used to enforce auxiliary constraints. This leads us to define the FRUGAL-$BRIBERY problem, where we are required to find vulnerable votes with a total cost that is within a given budget, such that these votes can be changed in some way to make p win the election. Note that the FRUGAL- $BRIBERY problem can be either uniform or nonuniform depending on whether the prices of the vulnerable votes are all identical or different. If not mentioned otherwise, the prices of the vulnerable votes will be assumed to be nonuniform.

Contributions

Our primary contribution in this paper is to formulate and study two important and natural models of bribery which turn out to be special cases of the well studied $BRIBERY problem in elections. Our results show that both the FRUGALBRIBERY and the FRUGAL-$BRIBERY problems are intractable for many commonly used voting rules for weighted as well as unweighted elections, barring a few exceptions. These intractability results can be interpreted as an evidence that bribery in elections is a hard computational problem in the sense that even many of its important and natural special cases continue to be intractable. Thus bribery, although a possible attack on elections in principle, maybe practically not viable.

Our Results for Unweighted Elections The FRUGAL-BRIBERY problem is in P for the k-approval, Bucklin, and plurality with runoff voting rules. Also, the FRUGAL-$BRIBERY problem is in P for the plurality and veto voting rules. In contrast, the FRUGAL-

$BRIBERY problem is NP-complete for the Borda, maximin, Copeland, and STV voting rules [Observation 1]. The FRUGAL-BRIBERY problem is NP-complete for the Borda voting rule [Theorem 1]. The FRUGAL-$BRIBERY is NP-complete for the k-approval for any constant k 5 [Theorem 2], k-veto for any constant k 3 [Theorem 3], and a wide class of scoring rules [Theorem 5] even if the price of every vulnerable vote is either 1 or . Moreover, the UNIFORM-FRUGAL-$BRIBERY is NP-complete for the Borda voting rule even if all the vulnerable votes have a uniform price of 1 and the budget is 2 [Theorem 6]. The FRUGAL-$BRIBERY problem is in P for the kapproval, Bucklin, and plurality with runoff voting rules when the budget is a constant [Theorem 4].

Our Results for Weighted Elections

The FRUGAL-BRIBERY problem is in P for the maximin and Copeland voting rules when we have only three candidates [Observation 2], and for the plurality voting rule for any number of candidates [Theorem 7]. The FRUGAL-BRIBERY problem is NP-complete for the STV [Theorem 10], plurality with runoff [Corollary 1], and every scoring rule except the plurality voting rule [Observation 2] for three candidates. The FRUGAL-$BRIBERY problem is NP-complete for the plurality voting rule for three candidates [Theorem 8]. When we have only four candidates, the FRUGALBRIBERY problem is NP-complete for the maximin [Theorem 9], Bucklin, and Copeland [Theorem 11] rules.

Related Work The pioneering work of (Faliszewski, Hemaspaandra, and Hemaspaandra 2006) defined and studied the $BRIBERY problem wherein the input is a set of votes with prices for each vote and the goal is to make some distinguished candidate win the election, subject to a budget constraint of the briber. The FRUGAL-$BRIBERY problem is the $BRIBERY problem with the restriction that the price of every nonvulnerable vote is infinite. Also the FRUGAL-BRIBERY problem is a special case of the FRUGAL-$BRIBERY problem. Hence, whenever the $BRIBERY problem is computationally easy in a setting, both the FRUGAL-BRIBERY and the FRUGAL-$BRIBERY problems are also computationally easy (see Proposition 1). However, the $BRIBERY problem is computationally intractable in most of the settings. This makes the study of important special cases such as FRUGALBRIBERY and FRUGAL-$BRIBERY, interesting. We note that a notion similar to vulnerable votes has been studied in the context of dominating manipulation by (Conitzer, Walsh, and Xia 2011). Hazon et al. (Hazon, Lin, and Kraus 2013) introduced and studied PERSUASION and k-PERSUASION problems where an external agent suggests votes to vulnerable voters which are beneficial for the vulnerable voters as well as the external agent. It turns out that the PERSUASION and the k-PERSUASION problems Turing reduce to the FRUGAL-BRIBERY and the FRUGAL-$BRIBERY problems respectively (see Proposition 3). Therefore, the polynomial time algorithms we propose in this work imply polynomial time algorithms for the persuasion analog. On the other hand,

since the reduction in Proposition 3 from PERSUASION to FRUGAL-BRIBERY is a Turing reduction, the existing NPcompleteness results for the persuasion problems do not imply NP-completeness results for the corresponding frugal bribery variants. We refer to (Rogers and Rogers 1967) for Turing reductions. Also, (Zuckerman et al. 2011) provided a game theoretic view on coalition formation in the context of manipulation.

Preliminaries Let V = {v1, . . . , vn} be the set of all voters and C = {c1, . . . , cm} the set of all candidates. Each voter vi s vote is a preference i over the candidates which is a linear order over C. In the paper, whenever we do not specify the order among a set of candidates while describing a vote, the statement/proof is correct in whichever way we fix the order among them. We denote the set {0, 1, 2, . . .} by N, N \ {0} by N+, and {1, . . . , k} by [k], for any positive integer k. We denote the set of all linear orders over C by L(C). Hence, L(C)n denote the set of all n-voters preference profiles [n]= ( 1, . . . , n). Let denote the disjoint union of sets. A map rc : n,|C| N+L(C)n 2C \ { } is called a voting correspondence. A map t : 2C \ { } C is called a tie breaking rule. A commonly used tie breaking rule is the lexicographic tie breaking rule where ties are broken according to a predetermined preference t L(C). A voting rule is r = t rc, where denote the composition of maps.

Remark. We note that works in the literature often do not include a tie breaking rule in the definition of voting rules and study unique and co-winner versions of the same problem. However, our definition of vulnerable votes needs elections to have a unique winner. For this reason, we include a tie breaking rule as part of the definition of voting rules and mention a tie breaking rule in all the proofs. In many settings, the voters may have positive integer weights. Such an election is called a weighted election. The winner of a weighted election is defined to be the winner of the unweighted election where each vote is replaced by as many copies of the vote as its weight. We assume the elections to be unweighted, if not stated otherwise. Given an election E, we can construct a directed weighted graph GE, called the weighted majority graph, from E. The set of vertices in GE is the set of candidates in E. For any two candidates x and y, the weight of the edge (x, y) is DE(x, y) = NE(x, y) NE(y, x), where NE(a, b) is the number of voters who prefer candidate a to b. Some examples of common voting correspondences are as follows. Positional scoring rules: A collection of m-dimensional vectors sm = (α1, α2, . . . , αm) Rm with α1 α2 αm and α1 > αm for every m N naturally defines a voting rule a candidate gets score αi from a vote if it is placed at the ith position, and the score of a candidate is the sum of the scores it receives from all the votes. The winners are the candidates with maximum score. Scoring rules remain unchanged if we multiply every αi by any constant λ > 0 and/or add any constant μ. Hence, we assume without loss of generality that for any score vector sm, there exists a j such that αj αj+1 = 1 and αk = 0 for all k > j. We call such

an sm a normalized score vector. If αi is 1 for i [k] and 0 otherwise, then, we get the k-approval voting rule. For the k-veto voting rule, αi is 0 for i [m k] and 1 otherwise. 1-approval is called the plurality voting rule and 1-veto is called the veto voting rule. Maximin: The maximin score of a candidate x is miny =x DE(x, y). The winners are the candidates with maximum maximin score. Copelandα: Given α [0, 1], the Copelandα score of a candidate x is |{y = x : DE(x, y) > 0}| + α|{y = x : DE(x, y) = 0}|. The winners are the candidates with maximum Copelandα score. If not mentioned otherwise, we will assume α to be zero. Bucklin: A candidate x s Bucklin score is the minimum number ℓsuch that more than half of the voters rank x in their top ℓpositions. The winners are the candidates with lowest Bucklin score. Note that, the above voting rule is also called simplified Bucklin. However, for simplicity, we use the term Bucklin only in this draft. Plurality with runoff: The top two candidates according to the plurality scores are selected first. The pairwise winner of these two candidates is selected as the winner. Single Transferable Vote: In Single Transferable Vote (STV), a candidate with the least plurality score is dropped from the election and its votes are transferred to the next preferred candidate. If two or more candidates receive the least plurality score, then a tie breaking rule is used. The candidate that remains till the last round is the winner. We use the notation A P B to denote that the problem A polynomial time many-to-one reduces to the problem B.

Problem Definition In all the definitions below, r is a fixed voting rule. We define the notion of vulnerable votes as follows. Definition 1 (Vulnerable votes) Given a voting rule r, a set of candidates C, a profile of votes = ( 1, . . . , n), and a distinguished candidate p, we say a vote i is p-vulnerable if p i r( ). With the above definition of vulnerable votes, we formally define the FRUGAL-BRIBERY problem as follows. Definition 2 (r-FRUGAL-BRIBERY) Given a preference profile over a candidate set C, and a candidate p, determine if there is a way to make p win the election by changing only the vulnerable votes. Next we generalize the FRUGAL-BRIBERY problem to the FRUGAL-$BRIBERY problem which involves prices for the vulnerable votes and a budget for the briber. Definition 3 (r-FRUGAL-$BRIBERY) Given a preference profile = ( 1, . . . , n) over a candidate set C, a candidate p, a finite budget b, and a price function c : [n] N such that c(i) = if i is not a p-vulnerable vote, determine if there exist votes i1, . . . , iℓ and votes i1, . . . , iℓ L(C) such that ℓ j=1 c(ij) b and r( [n]\{i1,...,iℓ}, i1, . . . , iℓ) = p. If the prices of all the vulnerable votes are the same, then we call the problem UNIFORM-FRUGAL-$BRIBERY. Otherwise, we call it NONUNIFORM-FRUGAL-$BRIBERY.

The above problems are important special cases of the well studied $BRIBERY problem. Also, the COALITIONALMANIPULATION problem (Bartholdi, Tovey, and Trick 1989; Conitzer, Sandholm, and Lang 2007), one of the classic problems in computational social choice theory, turns out to be a special case of the FRUGAL-$BRIBERY problem. Due to space constraints, proofs of some results (marked with a ( )) are omitted. Proposition 1 to 3 below hold for both weighted and unweighted elections. Proposition 1 ( ) For every voting rule, FRUGAL-BRIBERY P UNIFORM-FRUGAL-$BRIBERY P NONUNIFORMFRUGAL-$BRIBERY P $BRIBERY. Also, COALITIONALMANIPULATION P NONUNIFORM-FRUGAL-$BRIBERY. Also, the FRUGAL-BRIBERY problem reduces to the COALITIONAL-MANIPULATION problem by simply making all vulnerable votes to be manipulators. Proposition 2 For every voting rule, FRUGAL-BRIBERY P COALITIONAL-MANIPULATION. We can also establish the following relationship between the PERSUASION (respectively k-PERSUASION) problem and the FRUGAL-BRIBERY (respectively FRUGAL-$BRIBERY) problem. The persuasions differ from the corresponding frugal bribery variants in that the briber has her own preference order, and desires to improve the outcome of the election with respect to her preference order. The following proposition is immediate from the definitions of the problems. Proposition 3 ( ) For every voting rule, there is a Turing reduction from PERSUASION (respectively k-PERSUASION) to FRUGAL-BRIBERY (respectively FRUGAL-$BRIBERY).

Results for Unweighted Elections Now we present the results for unweighted elections. The following result follows immediately from the literature on the COALITIONAL-MANIPULATION (Xia et al. 2009), the $BRIBERY problems (Faliszewski, Hemaspaandra, and Hemaspaandra 2006; Faliszewski 2008) and Proposition 1 and 2. Observation 1 ( ) The FRUGAL-BRIBERY problem is in P for the k-approval for any k, Bucklin, and plurality with runoff voting rules. The FRUGAL-$BRIBERY problem is in P for the plurality and veto voting rules. The FRUGAL-$BRIBERY problem is NP-complete for the Borda, maximin, Copeland, and STV voting rules. We now present our main results. We begin with showing that the FRUGAL-BRIBERY problem for the Borda voting rule and the FRUGAL-$BRIBERY problem for various scoring rules are NP-complete. To this end, we reduce from the EXACT-COVER-BY-3-SETS (X3C) problem, which is known to be NP-complete (Garey and Johnson 1979). The X3C problem is defined as follows. Definition 4 (The X3C Problem) Given a universe U and t subsets S1, . . . , St U with |Si| = 3, i [t], does there exist an index set I [t] with |I| = |U|/3 such that i ISi = U? We denote an arbitrary instance of X3C by (U, {S1, . . . , St}).

We now prove that the FRUGAL-BRIBERY problem is NPcomplete for the Borda rule, by a reduction from X3C. Theorem 1 The FRUGAL-BRIBERY problem is NPcomplete for the Borda voting rule. Proof: The problem is clearly in NP. To show NP-hardness, we reduce an arbitrary instance of X3C to FRUGAL-BRIBERY. Let (U, {S1, . . . , St}) be an instance of X3C. We define a FRUGAL-BRIBERY instance as follows. Let m be the universe size |U|. The candidate set is C = U D {p, c, z}, where |D| = 5m. Let us fix any arbitrary order f among the candidates in U D. For any subset A U D, let A be the ordering among the candidates in A as defined in f and A the reverse order of A. For each Si, 1 i t, we add two votes v1 i and v2 i as follows.

v1 i : p D U \ Si c z Si

v2 i : Si z c U \ Si D p Let D4m/3 2, Dm 1, Dm 2, D5m/3 1 D be any arbitrary pairwise disjoint subsets of D with |D4m/3 2| = 4m/3 2, |Dm 1| = m 1, |Dm 2| = m 2, |D5m/3 1| = 5m/3 1. We now add the following two votes μ1 and μ2.

μ1 : z c D4m/3 2 p Dm 1 U others

μ2 : U Dm 2 c p D5m/3 1 z others The distinguished candidate is p. The tie-breaking rule is p others . The winner is c and thus the votes in {v1 i : 1 i t} are the only vulnerable votes. We claim that the two instances are equivalent. Suppose there exists an index set I [t] with |I| = |U|/3 such that i ISi = U. We replace the votes v1 i with ν1 i , i I, which is defined as follows.

ν1 i : p D U \ Si z Si c

The final score of p is the same as the final scores of c, z, and every candidate in U and more than the score of every candidate in D. This makes p win the election. To prove the other direction, suppose the FRUGALBRIBERY instance is a YES instance. Notice that the only vulnerable votes are v1 i for every i [t]. We assume without loss of generality, that candidate p is placed at the first position in all the changed votes. The votes μ1 and μ2 ensure that the score of c must decrease by 4m/3 for p to win. Hence, there must be at least m/3 votes that are changed since each vote change can reduce the score of c by at most 4. Also, in each vote v1 i where the position of c has been changed, the score of z from that vote must increase, since otherwise, there will be at least one candidate x Si whose score must increase by at least two contradicting the fact that p wins the election. However, the score of z can increase by at most m/3. Hence, there will be exactly m/3 votes where c s score decreases and thus in all those votes, c must come at the last position. We claim that the Si s corresponding to the changed votes must form an exact set cover. Indeed, otherwise, there will be a candidate in U whose score does not increase and thus there will be some other candidate in U whose score increases by at least two contradicting the fact that p wins the

election. We will use Lemma 1 in subsequent proofs which has been used before (Baumeister, Roos, and Rothe 2011; Dey, Misra, and Narahari 2015).

Lemma 1 ( ) Let C = {c1, . . . , cm} D, (|D| > 0) be a set of candidates and α a normalized score vector of length |C|. Then, for any given X = (X1, . . . , Xm) Zm, there exists λ R and a voting profile such that the α -score of ci is λ + Xi for all 1 i m, and the score of candidates d D is less than λ. Moreover, the number of votes is O(poly(|C| m i=1 |Xi|)), where |Xi| is the absolute value of Xi. Note that the number of votes used in Lemma 1 is polynomial in m if |D| and |Xi| are polynomials in m for every i [m], which indeed is the case for all our proofs that use Lemma 1. Hence, the reductions in the proofs that use Lemma 1 run in polynomial amount of time. We now show the results for various classes of scoring rules.

Theorem 2 The FRUGAL-$BRIBERY problem is NPcomplete for the k-approval voting rule for any constant k 5, even if the price of every vulnerable vote is either 1 or .

Proof: The problem is clearly in NP. To show NP-hardness, we reduce an arbitrary instance of X3C to FRUGAL- $BRIBERY. Let (U, {S1, . . . , St}) be an instance of X3C. We define a FRUGAL-$BRIBERY instance as follows. The candidate set is C = U D {p, q}, where |D| = k 1. For each Si, 1 i t, we add a vote vi as follows.

vi : p q Si 5 candidates

By Lemma 1, we can add poly(|U|) many additional votes to ensure the following scores (denoted by s( )).

s(q) = s(p) + |U|/3, s(x) = s(p) + 1, x U,

s(d) < s(p) |U|/3, d D The tie-breaking rule is p others . The winner is q. The distinguished candidate is p and thus all the votes in {vi : 1 i t} are vulnerable. The price of every vi is 1 and the price of every other vulnerable vote is . The budget is |U|/3. We claim that the two instances are equivalent. Suppose there exists an index set I [t] with |I| = |U|/3 such that i ISi = U. We replace the votes vi with v i, i I, which are defined as follows.

v i : p D k candidates

This makes the score of p not less than the score of any other candidate and thus p wins. For the other direction, suppose the FRUGAL-$BRIBERY instance is a YES instance. Then notice that there will be |U|/3 votes in {vi : 1 i t} where the candidate q should not be placed within the top k positions since s(p) = s(q) |U|/3 and the budget is |U|/3. We claim that the Si s corresponding to the vi s that have been changed must form an exact set cover. Indeed, otherwise, there will be a candidate x U,

whose score never decreases which contradicts the fact that p wins the election since s(p) = s(x) 1. We next present a similar result for the k-veto voting rule which can be proved by a reduction from the X3C problem. Theorem 3 ( ) The FRUGAL-$BRIBERY problem is NPcomplete for the k-veto voting rule for any constant k 3, even if the price of every vulnerable vote is either 1 or . However, the existence of a polynomial time algorithm for the FRUGAL-$BRIBERY problem for the k-approval, Bucklin, and plurality with runoff voting rules, when the budget is a constant follows from the existence of a polynomial time algorithm for the COALITIONAL-MANIPULATION problem for these voting rules for a constant number of manipulators (Xia et al. 2009). Theorem 4 ( ) The FRUGAL-$BRIBERY problem is in P for the k-approval, Bucklin, and plurality with runoff voting rules, if the budget is a constant. Our next result shows that, the FRUGAL-$BRIBERY problem is NP-complete for a wide class of scoring rules. Theorem 5 can be proved by a reduction from the X3C problem. Theorem 5 ( ) For any positional scoring rule r with score vectors { si : i N}, if there exists a polynomial function f : N N such that, for every m N, f(m) 2m and in the score vector (α1, . . . , αf(m)), there exists a 1 ℓ f(m) 5 satisfying the following condition: αi αi+1 = αi+1 αi+2 > 0, ℓ i ℓ+ 3 then the FRUGAL-$BRIBERY problem is NP-complete for r even if the price of every vulnerable vote is either 1 or . For the sake of concreteness, an example of a function f, stated in Theorem 5, that works for the Borda voting rule is f(m) = 2m. Theorem 6 below shows the intractability of the UNIFORM-FRUGAL-$BRIBERY problem for the Borda voting rule, even in a very restricted setting. Theorem 6 can be proved by a reduction from the COALITION MANIPULATION problem for the Borda voting rule for two manipulators which is known to be NP-complete (Betzler, Niedermeier, and Woeginger 2011; Davies et al. 2011). Theorem 6 ( ) The UNIFORM-FRUGAL-$BRIBERY problem is NP-complete for the Borda voting rule, even when every vulnerable vote has a price of 1 and the budget is 2.

Results for Weighted Elections Now we turn our attention to weighted elections. The first part of Observation 2 follows from the literature on the COALITIONAL-MANIPULATION problem and Proposition 2 whereas the second part of Observation 2 follows from the proof of Theorem 6 in (Conitzer, Sandholm, and Lang 2007). Observation 2 ( ) The FRUGAL-BRIBERY problem is in P for the maximin and Copeland voting rules for three candidates. The FRUGAL-BRIBERY problem is NP-complete for any scoring rule except plurality for three candidates.

Theorem 7 ( ) The FRUGAL-BRIBERY problem is in P for the plurality voting rule.

The PARTITION problem, which is known to be NPcomplete (Garey and Johnson 1979), is defined as follows. Definition 5 (PARTITION Problem) Given a finite multi-set W of positive integers with

w W w = 2K, does there exist a subset W W such that

w W w = K? An arbitrary instance of PARTITION is denoted by (W, 2K). We define another problem which we call 1/4-PARTITION as below. The 1/4-PARTITION problem can be proved to be NP-complete by reducing from the PARTITION problem. We will use this fact in the proof of Theorem 10. Definition 6 (The 1/4-PARTITION Problem) Given a finite multi-set W of positive integers with w W w = 4K, does there exist a subset W W such that

w W w = K? An arbitrary instance of 1/4PARTITION is denoted by (W, 4K). The following result can be proved by exhibiting a reduction from the PARTITION problem. Theorem 8 ( ) The FRUGAL-$BRIBERY problem is NPcomplete for the plurality voting rule for three candidates. Next we show the hardness result for the maximin rule. Theorem 9 The FRUGAL-BRIBERY problem is NPcomplete for the maximin voting rule for four candidates. Proof: The problem is clearly in NP. We reduce an arbitrary instance of PARTITION to an instance of FRUGALBRIBERY for the maximin voting rule. Let (W, 2K), with W = {w1, . . . , wn} and n i=1 wi = 2K, be an arbitrary instance of the PARTITION problem. The candidates are p, a, b, and c. For every i [n], there is a vote p a b c of weight wi. There is one vote c a b p, one b c a p, and one a c b p each of weight K. The tie-breaking rule is p a b c . The distinguished candidate is p. Let T denote the set of votes corresponding to the weights in W and the rest of the votes S. Notice that only the votes in T are vulnerable. We claim that the two instances are equivalent. Suppose there exists a subset W W such that

w W w = K. We change the votes corresponding to the weights in W to p a b c and the rest of the votes in T to p b c a. The maximin score of every candidate is K and thus due to the tie-breaking rule, p wins. On the other hand, suppose there is a way to change the vulnerable votes, that is the votes in T, that makes p win the election. Without loss of generality, we can assume that all the votes in T place p at top position. First notice that the only way p could win is that the vertices a, b, and c must form a cycle in the weighted majority graph. Otherwise, one of a, b, and c will be the winner of the election. Now we show that the candidate b must defeat the candidate c. If not, then c must defeat b by a margin of K since the maximin score of p is fixed at K. Also, a must defeat c by a margin of K, otherwise the maximin score of c will be more than K. This implies that all the votes in T must be p a c b which makes a defeat b. This is a contradiction since the vertices a, b, and c must form a cycle in the weighted majority graph. Hence b must defeat c by a margin of K. This forces every

vote in T to prefer b to c. Hence, without loss of generality, we assume that all the votes in T are either p a b c or p b c a, since whenever c is right after a, we can swap a and c and this will only reduce the score of a without affecting the score of any other candidates. If the total weight of the votes p a b c in T is more than K, then DE(c, a) < K, thereby making the maximin score of a more than the maximin score of p. If the total weight of the votes p a b c in T is less than K, then DE(a, b) < K, thereby making the maximin score of b more than the maximin score of p. Thus the total weight of the votes p a b c in T should be exactly K which corresponds to a partition of W. We now prove the hardness result for the STV voting rule. Theorem 10 The FRUGAL-BRIBERY problem is NPcomplete for the STV voting rule for three candidates. Proof: The problem is clearly in NP. We reduce an arbitrary instance of 1/4-PARTITION to an instance of FRUGALBRIBERY for the STV voting rule. Let (W, 4K), with W = {w1, . . . , wn} and n i=1 wi = 4K, be an arbitrary instance of the 1/4-PARTITION problem. The candidates are p, a, and b. For every i [n], there is a vote p a b of weight wi. There is a vote a p b of weight 3K 1 and a vote b a p of weight 2K. The tie-breaking rule is a b p . The distinguished candidate is p. Let T denote the set of votes corresponding to the weights in W and the rest of the votes be S. Notice that only the votes in T are vulnerable. We claim that the two instances are equivalent. Suppose there exists a subset W W such that w W w = K. We change the votes corresponding to the weights in W to b p a. We do not change the rest of the votes in T. This makes p win the election. For the other direction, suppose there is a way to change the votes in T that makes p win the election. First Notice that p can win only if b qualifies for the second round. Hence, the total weight of the votes in T that put b at the first position must be at least K. On the other hand, if the total weight of the votes in T that put b at the first position is strictly more than K, then p does not qualify for the second round and thus cannot win the election. Hence the total weight of the votes in T that put b at the first position must be exactly equal to K which constitutes a 1/4-partition of W. For three candidates, the STV voting rule is the same as the plurality with runoff voting rule. Hence, we have the following corollary. Corollary 1 The FRUGAL-BRIBERY problem is NPcomplete for the plurality with runoff voting rule for three candidates. We also have the following results for the Copelandα and Bucklin voting rules by reducing from PARTITION. Theorem 11 ( ) The FRUGAL-BRIBERY problem is NPcomplete for the Copelandα and Bucklin voting rules for four candidates, whenever α [0, 1). From Proposition 1, Observation 2, Theorem 8 to 11, and Corollary 1, we get the following corollary. Corollary 2 The UNIFORM-FRUGAL-$BRIBERY and the NONUNIFORM-FRUGAL-$BRIBERY problems are NP-

complete for the scoring rules except plurality, STV, and the plurality with runoff voting rules for three candidates and for the maximin, Copeland, and Bucklin voting rules for four candidates.

Acknowledgement Palash Dey wishes to gratefully acknowledge support from Google India for providing him with a special fellowship for carrying out his doctoral work. Neeldhara Misra acknowledges support by the INSPIRE Faculty Scheme, DST India (project IFA12-ENG-31).

Bartholdi, J.; Tovey, C.; and Trick, M. 1989. The computational difficulty of manipulating an election. Social Choice and Welfare (SCW) 6(3):227 241. Baumeister, D.; Faliszewski, P.; Lang, J.; and Rothe, J. 2012. Campaigns for lazy voters: Truncated ballots. In Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 577 584. International Foundation for Autonomous Agents and Multiagent Systems. Baumeister, D.; Roos, M.; and Rothe, J. 2011. Computational complexity of two variants of the possible winner problem. In The 10th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 853 860. International Foundation for Autonomous Agents and Multiagent Systems. Betzler, N.; Niedermeier, R.; and Woeginger, G. J. 2011. Unweighted coalitional manipulation under the borda rule is NP-hard. In IJCAI, volume 11, 55 60. Binkele-Raible, D.; Erd elyi, G.; Fernau, H.; Goldsmith, J.; Mattei, N.; and Rothe, J. 2014. The complexity of probabilistic lobbying. volume 11, 1 21. Discrete Optimization. Bredereck, R.; Chen, J.; Faliszewski, P.; Nichterlein, A.; and Niedermeier, R. 2014. Prices matter for the parameterized complexity of shift bribery. In International Conference on Artificial Intelligence (AAAI). Conitzer, V.; Sandholm, T.; and Lang, J. 2007. When are elections with few candidates hard to manipulate? Journal of the ACM (JACM) 54(3):14. Conitzer, V.; Walsh, T.; and Xia, L. 2011. Dominating manipulations in voting with partial information. In Proceedings of the Twenty Fifth AAAI Conference on Artificial Intelligence, AAAI 2011, San Francisco, California, USA, August 7-11, 2011. Davies, J.; Katsirelos, G.; Narodytska, N.; and Walsh, T. 2011. Complexity of and algorithms for Borda manipulation. In Proceedings of the International Conference on Artificial Intelligence (AAAI), 657 662. Dey, P.; Misra, N.; and Narahari, Y. 2015. Kernelization complexity of possible winner and coalitional manipulation problems in voting. In Proceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems, AAMAS 15, 87 96. Richland, SC: International Foundation for Autonomous Agents and Multiagent Systems. Dorn, B., and Kr uger, D. 2015. On the hardness of bribery variants in voting with CP-Nets. Annals of Mathematics and Artificial Intelligence. 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 (SAGT 2009). Springer. 299 310.

Erdelyi, G.; Hemaspaandra, E.; and Hemaspaandra, L. A. 2014. Bribery and voter control under voting-rule uncertainty. In Proceedings of the 13th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 61 68. International Foundation for Autonomous Agents and Multiagent Systems. Faliszewski, P.; Hemaspaandra, E.; Hemaspaandra, L. A.; and Rothe, J. 2009. Llull and Copeland voting computationally resist bribery and constructive control. Journal of Artificial Intelligence Research (JAIR) 35(1):275. Faliszewski, P.; Reisch, Y.; Rothe, J.; and Schend, L. 2015. Complexity of manipulation, bribery, and campaign management in bucklin and fallback voting. Autonomous Agents and Multi-Agent Systems 29(6):1091 1124. Faliszewski, P.; Hemaspaandra, E.; and Hemaspaandra, L. A. 2006. The complexity of bribery in elections. In International Conference on Artificial Intelligence (AAAI), volume 6, 641 646. Faliszewski, P.; Hemaspaandra, E.; and Hemaspaandra, L. A. 2009. How hard is bribery in elections? Journal of Artificial Intelligence Research (JAIR) 35(2):485. Faliszewski, P.; Hemaspaandra, E.; and Hemaspaandra, L. A. 2011. Multimode control attacks on elections. J. Artif. Intell. Res. (JAIR) 40:305 351. Faliszewski, P. 2008. Nonuniform bribery. In Proceedings of the 7th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 1569 1572. International Foundation for Autonomous Agents and Multiagent Systems. Garey, M. R., and Johnson, D. S. 1979. Computers and Intractability, volume 174. freeman New York. Hazon, N.; Lin, R.; and Kraus, S. 2013. How to change a groups collective decision? In Proceedings of the 23rd International Joint Conference on Artificial Intelligence (IJCAI), 198 205. Mattei, N.; Pini, M. S.; Venable, K. B.; and Rossi, F. 2012. Bribery in voting over combinatorial domains is easy. In Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 1407 1408. International Foundation for Autonomous Agents and Multiagent Systems. Mattei, N.; Pini, M. S.; Rossi, F.; and Venable, K. B. 2013. Bribery in voting with cp-nets. Ann. Math. Artif. Intell. 68(1-3):135 160. Pini, M. S.; Rossi, F.; and Venable, K. B. 2013. Bribery in voting with soft constraints. In International Conference on Artificial Intelligence (AAAI). Rogers, H., and Rogers, H. 1967. Theory of recursive functions and effective computability, volume 126. Mc Graw-Hill New York. Schlotter, I.; Faliszewski, P.; and Elkind, E. 2011. Campaign management under approval-driven voting rules. In Proceedings of the Twenty-Fifth AAAI Conference on Artificial Intelligence, AAAI 2011, San Francisco, California, USA, August 7-11, 2011. Xia, L.; Zuckerman, M.; Procaccia, A. D.; Conitzer, V.; and Rosenschein, J. S. 2009. Complexity of unweighted coalitional manipulation under some common voting rules. In Proceedings of the 21st International Joint Conference on Artificial Intelligence (IJCAI), volume 9, 348 353. Xia, L. 2012. Computing the margin of victory for various voting rules. In Proceedings of the 13th ACM Conference on Electronic Commerce (EC), 982 999. ACM. Zuckerman, M.; Faliszewski, P.; Conitzer, V.; and Rosenschein, J. S. 2011. An NTU cooperative game theoretic view of manipulating elections. In Proceedings of the 7th International Conference on Internet and Network Economics, WINE 11, 363 374. Berlin, Heidelberg: Springer-Verlag.