Election with Bribe-Effect Uncertainty: A Dichotomy Result

1 Introduction

Election (or voting) is a mechanism for agents in a society or multiagent system to make decisions collectively. Because of its many interesting aspects, such as algorithmic solutions and computational complexity characteristics, there is an active research field in computational social choice (see, for example, the book by [Brandt et al., 2016] and some recent results by [Kenig and Kimelfeld, 2019; Faliszewski et al., 2019; Chen et al., 2019b]). One of the most fundamental problems in computational social choice is bribery, namely that an attacker (i.e., briber) attempts to manipulate the outcome of an election by bribing some voters to deviate from their own preferences to the attacker's preference or designated candidate. Since its introduction by [Faliszewski et al., 2009], this problem has received a considerable amount of attention; see, e.g., [Brelsford et al., 2008; Xia, 2012; Faliszewski et al., 2015; 2011; Parkes and Xia, 2012; Faliszewski et al., 2019; Chen et al., 2018a; 2018b; 2019b].

∗Contact Author

Existing studies essentially make the following binary assumption: a voter either (i) takes a bribe that exceeds a threshold value determined by the voter and votes according to the attacker's preference, or (ii) declines a bribe that does not exceed the threshold value and votes according to the voter's own preference. This binary assumption oversimplifies the problem because in the real world a voter's decision may depend on the amount of the bribe. For example, a voter, who takes a bribe worth $101 because its threshold value is $100, may also take a bribe worth $99 with some probability.

The aforementioned inadequacy of the binary assumption has actually been discussed by researchers in the fields of psychology (see, e.g., [Gerlach et al., 2019]) and economic behavior (see, e.g., [Frank and Schulze, 2000]). However, the computational social choice community does not appear to be aware of these studies until now.

In this paper, we cope with the inadequacy of the binary assumption made in the literature of computational social choice, by investigating the following notion of bribe-effect uncertainty: Each voter is associated with a willingness function, rather than a threshold value; the willingness function determines the probability that a bribed voter will indeed vote according to the attacker's preference, where the probability varies with the amount of the bribe. With this new perspective, the classic bribery problem becomes what we call the Election with Bribe-Effect Uncertainty (EBEU) problem. The decision version of the EBEU problem is: Can an attacker with a fixed bribery budget succeed in manipulating the outcome of an election with a probability exceeding a given threshold of interest? Correspondingly, the optimization version of the EBEU problem asks for a solution that maximizes such a probability.

Obtaining the willingness functions as an input data can be achieved via experiments. Indeed, researchers in the psychology and economic behavior community have conducted experiments to study the relationship between dishonest behavior and reward magnitude; see Section 1.2. In particular, [Gerlach et al., 2019] provides a comprehensive survey over hundreds of such experiments.

It is worth stressing that a bribed voter may not always have to vote according to the attacker's preference, especially in elections using secret ballots. On the other hand, the EBEU model actually can be equally applied to describe the following lobbying problem: An attacker (i.e., briber) may donate an amount of money to (for example) a politician, in hoping that the politician will vote according to the attacker's preference (e.g., in deciding some public policy). In this case, the politician would certainly accept the donation but may not vote according to this particular donner's preference; instead, the politician may vote according to the preference of another donner who donates possibly a bigger amount of money. That is, the decision of the politician would be a function of the amount of the donation.

1.1 Our Contributions

The conceptual contribution of the paper is the introduction of a new type of uncertainty, namely bribe-effect uncertainty, into election models. This uncertainty is described by a willingness function, which eliminates the aforementioned oversimplifying binary assumption that has been widely made in the literature.

The technical contribution of the paper is the following dichotomy result. On one hand, we show that the EBEU problem under the Plurality voting rule, which will be explained later, does not admit any O(1)-approximation FPT-algorithm for arbitrary willingness functions, assuming FPT̸=W[1]. This means that the computational complexity of the EBEU problem could serve as an effective deterrence to bribery attackers. On the other hand, we show that if the logarithm of every voter's willingness function is Lipschitz continuous (which will be defined later), then there exists an FPT algorithm that produces (1+e)-approximate solution, meaning that the computational complexity may not be able to deter bribery attackers when their willingness functions are "smooth". This result is interesting because it's the mathematical property, rather than any specific form, of the willingness function that dictates whether or not the computational hardness can serve as a deterrence.

1.2 RelatedWork

Uncertainty is inherent to many real-world complex problems and coping with it has become a fundamental research problem. Putting into the context of election, uncertainty is inherent to the bribery problem because it is inadequate to model voters as machines that return "yes" or "no" based on whether or not a monetary award exceeds a threshold (see, e.g., [Frank and Schulze, 2000]). Nevertheless, the bribeeffect uncertainty we study in the present paper has not been investigated in the literature. The most closely-related prior works are [Chen et al., 2019b] and [Wojtas and Faliszewski, 2012], which still make the binary assumption despite that some bribed voters have some "no-show" probabilities (i.e., they may not vote at all). In our model, we eliminate the binary assumption and replace it with willingness functions, which characterize the relationship between the amount of bribe and the probability that a bribed voter indeed votes according to the attacker's preference. This distinction between the different kinds of uncertainty is also confirmed by the fact that the problem studied by [Chen et al., 2019b] always denies an O(1)-approximation FPT algorithm, while the approximability of our problem is crucially dependent upon a certain mathematical property of the willingness functions, as indicated by the dichotomy result mentioned above.

It is worth mentioning that other kinds of uncertainty (e.g., margin of victory), which are loosely related to the bribeeffect uncertainty, have been studied by [Dey and Narahari, 2015; Erdelyi et al., 2014; Mattei et al., 2015]. It is also worth mentioning that we focus on investigating the impact of the mathematical property of the willingness function, rather than its specific form, which is actually an open problem. Indeed, some researchers argue that a larger "reward" (or bribe) would increase the chance of dishonest behavior (see [Conrads et al., 2014; Gneezy, 2005]); others actually argue for the opposite - a larger bribe may lead to a smaller chance of dishonest behavior - because the psychological cost of cheating may increase (see [Mazar et al., 2008]); yet others argue that they are relatively independent (see [Abeler et al., 2016]). Our dichotomy result applies regardless of the correctness of these arguments because we show that it is not the monotonicity of the willingness function that matters most in determing whether or not the computational complexity can serve as a deterrence.

Despite the classical bribery model that assumes a threshold bribery cost for each voter [Faliszewski et al., 2009], other kinds of bribery model like swap bribery are also considered, see, e.g. [Elkind et al., 2009; Bredereck et al., 2016a; 2016b; Elkind and Faliszewski, 2010].

2 Problem Statement and Preliminaries

Election Problem. There are m candidates, denoted by a set C = {c1, c2, . . . , cm}, and n voters, denoted by a set V = {v1,v2, . . . ,vn}. Each voter votes according to its preference over the candidates c1,c2, . . . ,cm. There is a voting rule, according to which a winner is determined. There are many voting rules, but we focus on the plurality rule, which says that each voter votes for its most preferred candidate and the candidate receiving the most votes will be the winner.

Bribery Problem. In this problem, an attacker (i.e., briber) attempts to manipulate the outcome of an election by bribing some voters that would deviate from voting for their own preferred candidate to voting for the attacker's designated candidate. Specifically, let voter vi has a bribery price qi, meaning that receiving a bribe worth qi will make vi vote for the attacker's designated candidate, regardless of vi's own preference. The attacker has a total budget Q that can be spent on bribing voters.

EBEUProblem. This problemextends the bibery problem, which uses a binary willingness function f j : R≥0 →{0,1}, with a more general willingness function f j : R≥0 → [0,1] for voter vj such that f j(x) returns the probability that vj will vote for the attacker's designated candidate, where x is the amount of bribe received from the attacker and 1 ≤ j ≤ n. Without loss of generality, let c1 be the winner when there are no bribery attacks and cm be the attacker's designated candidate. Suppose the attacker has a fixed budget Q for waging the bribery attack and each voter vj has a willingness functon f j. The EBEU problem asks for identifying a subset of k voters in V ′ ⊆V, each of which receives a bribe of amount xj where vj ∈V ′ , such that the probability that the attacker's designated candidate cm wins the election (i.e., the attacker succeeds in manipulating the election) is maximized.

Formally, the EBEU problem is described as follows while normalizing the attacker's budget Q to 1 for a technical convenience.

The (Plurality-)EBEU Problem

Input: A set of m candidates C = {c1,c2, . . . ,cm}, where c1 is the winner in the absence of bribery attacks and cm is the attacker's designated candidate; a set of n voters V = {v1,v2, · · · ,vn}; a positive integer k; an attack budget (normalized to) 1; each voter vj ∈ V is associated with a willingness function f j such that if vj receives a bribe of amount x from the attacker, then v j will vote, with probability f j(x), according to the attacker's preference rather than v j's own preference (in the case of the plurality voting rule, v j will vote for the attacker's designated candidate cm). Output: Find a set of indices I ∗ ⊆ {1,2, · · · ,n}, |I ∗ | = k,

together with xj ∈R≥0 for each j ∈ I ∗ such that

• �j∈I ∗ xj ≤1, and
• the probability that cm wins the election (under the plurality voting rule) is maximized by bribing voters belonging to V ∗ = {vi ∈V \Vm|i ∈ I ∗ }.

Lipschitz Continuity. Since we will show that the Lipschitz continuity of the willingness function f j(·) will play the critical role in determing whether the election problem under bribe-taking uncertainty is vulnerable to the bribery attack or not, we need to review this property.

Definition 1 (Lipschitz continuity). Given two metric space (X,dX) and (Y,dY ), where dX and dY respectively denote the metrics in X and Y. A function f : X →Y is said Lipschitz continuous if there exists a universal real constant a0 ≥ 0 such that for all x1,x2 ∈X, it holds that

When the function f is defined on real numbers, which is true in the setting of the present paper, the condition specified by Eq. (1) can be rewritten as

3 Hardness of EBEUWith Non-"Lipschitz Continuous" Willingness

In this section, we show via Theorem 1 that if some of the log f j(·)'s are not Lipschitz continuous, then the EBEU problem does not admit any constant ratio approximation algorithms. The inapproximability holds even if the willingness functions are continuous. The implication of this hardness result is that election under bribe-effect uncertainty is not vulnerable to optimal bribery attacks, namely that the complexity in finding an optimal attack may hinder the attacker from waging such attacks.

Theorem 1 (Main hardness result). Assuming W[1] ̸= FPT, there exist (continuous) willingness functions, f j(·)'s, such that the EBEU problem does not admit any g(k)- approximation algorithm that runs in FPT time parameterized by k for any computable function g, even if m = 2.

In order to prove Theorem 1, we leverage the 2dimensional knapsack problem, which is reviewed below, and its W[1]-hardness result owing to [Kulik and Shachnai, 2010].

The 2-dimensional Knapsack

Input: A set of n′ items, where each item j has a 2dimensional size (aj,bj) ∈ Z2≥0 ; a 2-dimensional knapsack

of size (A,B) ∈ Z2>0 .

Output: Decide whether or not there exists a subset S of items such that |S| = r and �j∈S(a j , b j) ≤ (A,B).

Theorem 2 (Theorem 7, [Kulik and Shachnai, 2010]). AssumingW[1] ̸=FPT, there does not exist any algorithm that runs in time fKP(r)|IKP|O(1) for solving the 2-dimensional knapsack problem for any computable function fKP, where |IKP| is the length of the input.

The strategy for proving Theorem 1 is the following: Suppose on the contrary that there exists some aapproximation FPT algorithm that solves the EBEU problem in fEBEU(k)|IEBEU|O(1) time for some computable function fEBEU, where a = g(k) for some function g, we can show that this algorithm can be utilized to solve the 2-dimensional knapsack problem in fKP(r)|I|O(1) time for some computable function fKP. This contradicts with Theorem 2.

Proof of Theorem 1. Under the proof strategy mentioned above, we first construct an instance of the EBEU problem from an instance of the 2-dimensional knapsack problem according to the following two steps. First, we construct two candidates c1 and c2, where c1 is the winner when there are no bribery attacks and c2 is the attacker's designated candidate. Recall that the bribe budget is defined to be 1. Second, we construct n = 2n′ +2k-1 voters, including n′ key voters, each of which corresponds to an item, and n′ +2k-1 dummy voters, each of which does not correspond to any item, where k = r. The difference between these two types of voters is in their willingness functions: the willingness functions of key voters are not Lipschitz continuous, but the willingness functions of dummy voters are Lipschitz continuous.

• Constructing key voters: For each item j of 2dimensional size (aj,bj), a key voter vj is constructed with the following willingness function f j:

where M>a is an integer (e.g., M=a+1) and d is a sufficiently small rational number (e.g., d = 1/(100n)).

Note that the function f j is continuous, but it has a sharp increase around the point A+aj (k+1)A , where the value explodes with rate O(1/d) = O(n). Hence, f j and log f j are not Lipschitz continuous.

• Constructing dummy voters: Each dummy voter has the following willingness function fdummy:

All the n′ key voters vote for c1 because they are not bribed by the attacker. Among the n′ +2k-1 dummy voters, 2k-1 of them vote for c1 and n′ of them vote for c2. This completes the construction of a EBEU instance.

Now, suppose there exists a a-approximation FPT algorithm for the EBEU problem that runs in fEBEU(k)|IEBEU |O(1) time. Then, we can use this algorithm to solve the given 2dimensional knapsack instance, yielding a contradiction. Recall that k = r and that there is a one-to-one correspondence between the key voters in the constructed EBEU instance and the items in the given 2-dimensional knapsack instance. The proof is based on the following 5 claims (see [Chen et al., 2019a] for the omitted proofs).

Claim 1. If c2 wins with probability 0 in the approximation solution to the constructed EBEU instance, the given 2dimensional knapsack instance does not admit any feasible solution.

From now on we assume c2 wins with a positive probability in the approximation solution to the EBEU instance. Note that if the attacker chooses to bribe some voter, the attacker should spend an amount such that the voter will vote for the attacker's designated candidate with a positive probability. This means that if the attacker chooses to bribe a dummy voter, the attacker should spend an amount that is strictly larger than 1, which is impossible. Hence, the attacker bribes exactly k key voters in any feasible solution. Let V ′ be an arbitrary feasible solution to the EBEU instance, and let S′ be the corresponding subset of items in the 2-dimensional knapsack instance. It is clear that j ∈S′ and vj ∈V ′ are equivalent.

Claim 3. Without loss of generality, we can assume that the attacker bribes vj ∈V ′ with an amount A+aj (k+1)A .

Claim 4. If the given 2-dimensional knapsack instance admits a feasible solution, then the objective value of an aapproximation solution to the EBEU instance is at least M-B .

Claim 5. If the given 2-dimensional knapsack instance does not admit any feasible solution, then the objective value of the approximation solution to the EBEU instance is at most M-B-1 .

By Claim 1, Claim 4 and Claim 5, we can decide whether the given 2-dimensional knapsack instance admits a feasible solution by checking whether or not the a-approximation solution to the EBEU instance has an objective value larger than M-B-1 . Since the approximation algorithm runs in fEBEU(k)|IEBEU|O(1) time for some computable function fEBEU and that r = k, we derive an FPT algorithm for the 2-dimensional knapsack problem, contradicting Theorem 2. Hence, Theorem 1 holds.

4 FPT-Approximation Schemes for EBEU With Lipschitz Continuous Willingness

Now we present an algorithmic result in Theorem 3, while assuming the willingness functions are Lipschitz continuous. Theorem 3 (Main algorithmic result). Let F + j ={x : f j(x) > 0} where 1 ≤ j ≤ n. If log f j(x) is Lipschitz continous for all x ∈ F + j as well as 1 ≤ j ≤ n and the number of candidates m is a constant, then there exists an algorithm for solving the EBEU problem such that the algorithm runs in fEBEU(k)|IEBEU|O(1) time for some computable function fEBEU and returns a solution with an objective value that is no smaller than (1-e)OPT, where OPT ∈ [0,1] is the optimal objective value and e > 0 is an arbitrary small constant.

In order to prove Theorem 3, we proceed as follows. In Section 4.1, we show the existence of a well-structured near optimal solution. In Section 4.2, we show how to guess important structural information for identifying the well-structured near optimal solution. In Section 4.3, we present an approximation algorithm that returns a k O(k) - approximation solution. This approximation algorithm provides an upper bound of the optimal objective value, through which we develop a dynamic programming-based FPT approximation scheme in Section 4.4.

4.1 Existence of a Near Optimal Solution

Recall that the total budget is 1 and we only consider f j(x) where x ≤ 1. The following property of f j(·)'s plays a crucial role in deriving a k O(k) -approximation algorithms, which leads to an FPT approximation scheme. Intuitive, ln f j being Lipschitz continuity means that the value of f j(x) does not increase arbitrary as x increases, as is shown by Corollary 1. This fact is particularly useful in two aspects. First, we can round down the cost spent on bribing each voter by some sufficiently small amount without causing the value of the willingness function to change much. This allows us to show the existence of a well-structured near optimal solution. Second, we can derive a k O(k) -approximation solution through the following heuristic: If we have a budget of amount k instead of 1, then we can simply bribe the k voters whose f j(1)'s are the largest; given that we only have a budget of 1, we can choose to spend 1/k to bribe each of these voters, and this greedy solution would not be too far from the optimal one because f j(1) and f j(1/k) do not differ too much, owing to the property of Lipschitz continuity.

The following Lemma 1, Lemma 2 and Corollary 1 are all deduced from Lipschitz continuity (see [Chen et al., 2019a] for their proofs).

Lemma 1. If ln f j(x) is Lipschitz continuous for x ∈ F + j ∩ [0,1], then

holds for any sufficiently small e > 0.

Note that we do not necessarily restrict f j's to be nondecreasing, but if f j(x) < f j(y) for some x > y and the attacker allocates a budget of amount x to bribe v j, then the attacker may simply choose to spend a smaller amount to bribe vj. For example, the attacker can spend an amount x′ to bribe vj, where f j(x′ ) = supt≤x f j(t). Consequently, we define ¯ f j as:

Similar to Lemma 1, the following lemma holds for function f j .

Lemma 2. If ln f j(x) is Lipschitz continuous for x ∈ F + j ∩ [0,1], then

holds for any sufficiently small e > 0.

From now on we only need to focus on fj(x) instead of f j(x) because the monotonicity of fj(x) makes our presentation easier to follow. According to Lemma 2, we have the following corollary.

Corollary 1. If ln f j(x) is Lipschitz continuous for x ∈ F + j ∩ [0,1], then

holds for any x, y ∈ F + j ∩[0,1],x < y.

Consider an arbitrary solution where the attacker bribes some subset V ′ of voters such that any vj ∈V ′ will vote for the attacker's designated candidate with some probability p j . Let p1 be the probability that cm wins. Let vj0 ∈ V ′ be an arbitrary fixed voter. Suppose we change the probability associated to vj0 ∈V ′ from pj0 to p′j0 ≥ pj0 , and let p2 be the probability that cm wins as a consequence of the change in probability. Since vj0 votes for the attacker's designated candidate with a higher probability now, it is straightforward to see that p2 ≥ p1. Lemma 3 below says that p2 cannot be too large.

Proof. Let W be the event that when vj0 votes for the attacker's designated candidate cm and cm wins. Let W′ be the event that when v j0 does not vote for the attacker's designated candidate cm and cm wins. Then, we have

and

Since p j0 ≤ p′j0 , we have Pr(W′ )(1- p j0 ) ≥ Pr(W′ )(1- p′j0 ). Hence, we have p2 ≤ p1 · p′j0 p j0 .

From Lemma 3, we obtain the following corollary.

Corollary 2. Let p ′ be the probability that cm wins when we change the probability that vj votes for the attacker's designated candidate from pj to p′j . Then, we have

Note that we can interpret Lemma 3 as if we decrease the probability of vj0 from p′j0 to pj0 , in which case the probability that vj votes for the attacker's designated candidate decreases from p2 to p1, but we can still obtain the lower bound p1 such that p1 ≥ p2 · pj0 p′j0 . This leads to the following corollary:

Corollary 3. Let p ′ be the probability that cm wins when we change the probability that vj votes for the attacker's designated candidate from pj to p′j , then we have

Now we are ready to construct a solution. From now on we denote by V ∗ the subset of voters selected by the optimal solution. Let xj be the amount of budget the attacker spends on bribing voter vj ∈V ∗ , fj(xj) = pj, and p ∗ be the probability that cm wins. We modify the optimal solution in the following three steps.

Step 1. We reduce the amount of budget that is spent on each voter by a factor of 1-e/k, meaning that the attacker spends (1-e/k)xj to bribe voter vj ∈V ∗ .

Lemma 4. After Step 1, cm wins with a probability at least p ∗ (1 - O(e )).

Proof. According to Lemma 2, we have fj((1-e/k)xj) ≥ (1-O(e/k))pj. According to Corollary 3, the probability that cm wins after the modification specified in Step 1 is at least p ∗ (1-O(e/k))k ≥ p ∗ (1-O(e)).

Step 2. Note that after Step 1, the total amount of budget spent by the attacker is at most 1-e/k. If the attacker spends less than e/k 2 on some voter, then we increase the amount to be e/k 2 . Since at most k voters are selected, the overall increase in the spent budget is e/k, which is still legitimate (i.e., no greater than the original total budget of 1). Note that by doing so the probability that cm wins does not decrease and is at least p ∗ (1-O(e)).

Step 3. Consider the budget spent to bribe vj ∈ V ∗ after Step 2. We round down this amount to the nearest value in the form of e/k 2 (1+e/k)i for some integer i ≥ 0. Note that this step is similar to Step 1 and using the same argument as in Step 1, we can show that after Step 3 cm wins with a probability at least p ∗ (1-O(e)).

After conducting the preceding three steps, we call the resulting solution a well-structured feasible solution, which has a near optimal objective value (i.e., well-structured near optimal solution).

4.2 Enumeration

In order to find a well-structured near optimal solution, we need to guess (through enumeration) on some component in this solution. Since the amount of budget spent on each selected voter is in the form of e/k 2 (1+e/k)h where h ≤ O(k/e · log(k/e)), there are only O(k/e · log(k/e)) possibilities. We now classify the voters into m groups, where Vi is the set of voters who vote for candidate ci when there are no bribery attacks. We first guess, via k m enumerations, the number of voters bribed in each Vi. Suppose ki voters that belong to Vi are bribed.

For each bribed voters in Vi, the attacker spends a budget of amount e/k 2 (1+e/k)h to bribe the voter. We can list the ki different amounts the attacker spent to bribe the voters inVi as a vector, leading to a ki-dimensional vector where each element (or coordinate) can take at most O(k/e · log(k/e)) different values. We call such a vector a package for Vi. Through O(k k /e k · log k (k/e)) enumerations, we can guess the package for each Vi. Hence, by O(k mk /e mk · log mk (k/e)) enumerations, we can guess all of the packages.

Suppose the package for Vi is (a,b). Then, what remains to be done is to decide to select which of the two voters in Vi. Note that even if we know the two selected voters are v j1 and v j2 , it is far from clear that the attacker should spend budget a to bribe voter v j1 and budget b to bribe voter v j2 , or the attacker should spend b to bribe v j1 and a to bribe v j2 . In order to resolve this issue, we employ a dynamic programming approach. For this purpose, we need a g(k)-approximation algorithms that can provide us with a reasonable lower bound on the optimal objective value. Section 4.3 presents such an approximation algorithm.

4.3 A Simple Approximation Algorithm

Theorem 4. If ln f j(x) is Lipschitz continuous for x ∈ F ∗ j ∩ [0,1] and 1 ≤ j ≤ n, then there exists a k O(k) -approximation algorithm that runs in O(k m|IEBEU|) time for solving the EBEU problem, where |IEBEU| is the length of the input.

In order to prove Theorem 4, we first show a general result on comparing two arbitrary solutions. Let V 1 and V 2 denote the subsets of k voters selected by two feasible solutions Sol1 and Sol2, respectively. Let V h i =Vi ∩V h for h = 1,2. We say "the second solution is l-bounded by the first solution" if (i) |V 1 i | = |V 2 i | for every i and (ii) there exists a one-to-one lmapping, denoted by s, from the voters in V 1 i to the voters in V 2 i , where a mapping s : V 1 i →V 2 i is called l-mapping if for any j ∈V 1 i , we have

where xj is the amount of money the attacker spends to bribe voter v j in the first solution, and x′s( j) is the amount of money the attacker spends to bribe voter vs( j) in the second solution.

Lemma 5. Given two feasible solutions Sol1 and Sol2. Let p1 and p2 be their optimal objective values, respectively. If the second solution is l-bounded by the first solution for some l ≥ 1, then we have p2 ≤ l k p1.

Note that Theorem 4 already contrasts sharply with Theorem 1 and the running time is polynomial when m is constant.

4.4 An Approximation Scheme in FPT-Time

Theorem 5. If ln f j(x) is Lipschitz continuous for x ∈ F ∗ j ∩ [0,1] and 1 ≤ j ≤ n, and m is a constant, then there exists a (1+e)-approximation algorithm that runs in FPT-time parameterized by k for solving the EBEU problem, where e > 0 is any constant.

Proof sketch. We will use dynamic programming to keep track of all possible "partial solutions" and find out the wellstructured near optimal solution. A partial solution is a subset of voters selected among the first g voters. A state for a partial solution contains the following information: i). The number of bribed voters in eachVi. ii). The total amount of cost spent so far on the bribed voters. Notice that while the cost spent on each bribed voter can be an arbitrary real number, our rounding procedure ensures that we may assume the cost to take at most O(k/e · log(k/e)) distinct values (see Section 4.2), therefore the cost spent on each bribed voter can be stored, and consequently the overall cost. iii). The random variable that corresponds to the bribed voters in each Vi in the partial solution. Note that for each bribed voter, whether or not the voter changes preference is a binary random variable, and the eventual number of votes received by each candidate after bribery depends on the summation of these m random variables. Each of these random variables can only take values in {0,1, · · · ,k}, therefore, it suffices to store its probability on each value. The probability can be arbitrary real number, so we need to round it. Rounding is possible because the approximation algorithm derived in Section 4.3 can be used to provide us with an upper and lower bounds on the optimal probability that differ by a factor of at most k O(k) . Therefore, we can round the probabilities into an FPT number of distinct values based on the lower bound and show that the rounding will not cause the objective to increase by an O(e) factor.

5 Conclusion and Discussion

We introduced a new perspective of the electoral bribery problem in bribe-effect uncertainty, which goes beyond previous studies that assume a fixed threshold value according to which a voter decides to accept or decline a bribe. We used the notion of willingness function to accommodate the bribe-effect uncertainty. We proved a dichotomy result, which shows that the Lipschitz continuity of the logarithm of the willingness function, rather than any specific form of the willingness function, dictates whether or not the computational hardness can serve as a deterrence to bribery attackers. The new perspective of bribe-effect uncertainty indicates that there are many interesting problems for future research. For example, we only investigated the Plurality voting rule; it is interesting to know whether the dichotomy result is applicable to other voting rules or not.

Acknowledgements

We thank Dr. Paul Romanowich for useful discussions at an early stage of this research. This work is supported in part by NSF Grant #1756014 and ARO Grant #W911NF-17-1-0566.