{'fraction_non_alphanumeric': 0.04431050087619635, 'fraction_numerical': 0.00893527701284446, 'mean_word_length': 3.8687417963622726, 'pattern_counts': {'":': 0, '<': 2, '<?xml version=': 0, '>': 8, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 34, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Computational Complexity Characterization of Protecting Elections from Bribery

The bribery problem in election has received considerable attention in the literature, upon which various algorithmic and complexity results have been obtained. It is thus natural to ask whether we can protect an election from potential bribery. We assume that the protector can protect a voter with some cost (e.g., by isolating the voter from potential bribers). A protected voter cannot be bribed. Under this setting, we consider the following bi-level decision problem: Is it possible for the protector to protect a proper subset of voters such that no briber with a fixed budget on bribery can alter the election result? The goal of this paper is to give a full picture on the complexity of protection problems. We give an extensive study on the protection problem and provide algorithmic and complexity results. Comparing our results with that on the bribery problems, we observe that the protection problem is in general significantly harder. Indeed, it becomes $\sum_{p}^2$-complete even for very restricted special cases, while most bribery problems lie in NP. However, it is not necessarily the case that the protection problem is always harder. Some of the protection problems can still be solved in polynomial time, while some of them remain as hard as the bribery problem under the same setting.

Abstract. The bribery problem in election has received considerable attention in the literature, upon which various algorithmic and complexity results have been obtained. It is thus natural to ask whether we can protect an election from potential bribery. We assume that the protector can protect a voter with some cost (e.g., by isolating the voter from potential bribers). A protected voter cannot be bribed. Under this setting, we consider the following bi-level decision problem: Is it possible for the protector to protect a proper subset of voters such that no briber with a fixed budget on bribery can alter the election result? The goal of this paper is to give a full picture on the complexity of protection problems. We give an extensive study on the protection problem and provide algorithmic and complexity results. Comparing our results with that on the bribery problems, we observe that the protection problem is in general significantly harder. Indeed, it becomes Σ p 2 -complete even for very restricted special cases, while most bribery problems lie in NP. However, it is not necessarily the case that the protection problem is always harder. Some of the protection problems can still be solved in polynomial time, while some of them remain as hard as the bribery problem under the same setting.

Introduction
In an election, there are a set of candidates and a set of voters. Each voter has a preference list of candidates. Given these preference lists, a winner is determined based on some voting rule, examples of which will be elaborated later.
In the context of election, the bribery problem has received considerable attention (see, for example, [1,7,8,12,14]). In this problem, there is an attacker who attempts to manipulate the election by bribing some voters, who will then report preference lists of the attacker's choice (rather than the voters' own preference lists). Each voter has a price for being bribed, and the attacker has an attack budget for bribing voters. There are two kinds of attackers: constructive vs. destructive. A constructive attacker attempts to make its designated candidate win an election, whereas the designated candidate would not win the election should there be no attacker. In contrast, a destructive attacker attempts to make its designated candidate lose the election, whereas the designated candidate would win the election should there be no attacker. The research question is: Given an attack budget for bribing, whether or not a (constructive or destructive) attacker can achieve its goal?
In this paper, we initiate the study of a new problem, called the protection problem, which extends the bribery problem as follows. There are also a set of candidates, a set of voters, and a bribery attacker. Each voter also has a preference list of candidates. There is also a voting rule according to which a winner is determined. Going beyond the bribery problem, the protection problem further considers a defender, who aims to protect elections from bribery. More specifically, the defender is given a defense budget and can use the defense budget to award some of the voters so that they cannot be bribed by the attacker anymore. This leads to an interesting problem: Given a defense budget, is it possible to protect an election from an attacker with a given attack budget for bribing voters (i.e., assuring that the attacker cannot achieve its goal)?
Our contributions. We introduce the problem of protecting elections from bribery, namely the protection problem. Given a defense budget for rewarding some of the voters and an attack budget for bribing some of the rest voters, the protection problem asks whether or not the defender can protect the election. We investigate the protection problem against the aforementioned two kinds of bribery attackers: constructive vs. destructive.
We present a characterization on the computational complexity of the protection problem (summarized in Table 1 in Section 5). The characterization is primarily concerning the voting rule of r-approval, which will be elaborated in Section 2. At a high level, our results can be summarized as follows. (i) The protection problem is hard and might be much harder than the bribery problem. For example, the protection problem is Σ p 2 -complete in most cases, while the bribery problem is in NP under the same settings. (ii) The destructive protection problem (i.e., protecting elections against a destructive attacker) is no harder than the constructive protection problem (i.e., protecting elections against a constructive attacker) in all of the settings we considered. In particular, the destructive protection problem is Σ p 2 -hard only when the voters are weighted and have arbitrary prices, while the constructive protection problem is Σ p 2 -hard even when the voters are unweighted and have the unit price. (iii) Voter weights and prices have completely different effects on the computational complexity of the protection problem. For example, the constructive protection problem is coNP-hard in one case but is in P in another case.
Related Work. The problem of protecting elections from attacks seemingly has not received the due attention. Very recently, Yin et al. [20] considered the problem of defending elections against an attacker who can delete (groups of) voters. That is, the investigation is in the context of the control problem, where the attacker attempts to manipulate an election by adding or deleting some voters. The control problem has been extensively investigated (see, for example, [4,9,10,20]). Although the control problem is related to the bribery problem, the means used by the attacker in the control problem (i.e., attacker adding or deleting some voters) is different from the means used by the attacker in the bribery problem (i.e., attacker changing the preference lists of the bribed voters). We investigate the protection problem, which is defined in the context of the bribery problem rather than the control problem. That is, the problem we investigate is different from the problem investigated by Yin et al. [20].
The protection problem we study is inspired by the bribery problem. Faliszewski et al. [8] gave the first characterization on the complexity of the bribery problem, including some dichotomy theorems. In the bribery problem, the attacker can pay a fixed, but voter-dependent, price to arbitrarily manipulate the preference list of a bribed voter. The complexity of the bribery problem under the scoring rule of r-approval or r-veto for small values of r was addressed later by Lin [15] and Bredereck and Talmon [2]. There are also studies on measuring the bribery price in different ways (see, e.g., [1,6,12]).
Technically, the protection problem is related to the bi-level optimization problem, especially the bi-level knapsack problem ( [3,5,17,18]). In the bi-level knapsack problem, there is a leader and a follower. The leader makes a decision first (e.g., packing a subset of items into the knapsack), and then the follower solves an optimization problem given the leader's decision (e.g., finding the most profitable subset of items that have not been packed by the leader). The problem asks for the decision of the leader such that a certain objective function is optimized (e.g., minimizing the profit of the follower). The protection problem we study can be formulated as the bi-level problem by letting the defender award some voters who therefore cannot be bribed by the attacker anymore, and then the attacker bribes some of the remaining voters as an attempt to manipulate the election.
Voting rules. In this paper, we focus on the scoring rule (or scoring protocol) that maps a preference list to a m-vector α = (α 1 , α 2 , . . . , α m ), where α i ∈ N is the score assigned to the i-th candidate on the preference list of voter v j and α 1 ≥ α 2 ≥ . . . ≥ α m . Given that τ j is the preference list of v j , candidate c τj(i) receives a score of α i from v j . The total score of a candidate is the summation of the scores it received from the voters. The winner is the candidate that receives the highest total score. We focus on a single-winner election, meaning that only one winner is selected. In the case of a tie, a random candidate with the highest total score is selected. However, our results remain valid for all-natural variation of selecting a single winner.
Weights of voters. Voters can have different weights. Let w j ∈ N be the weight of voter v j . In a weighted election, the total score of a candidate is the weighted sum of the scores a candidate receives from the voters. For example, candidate c i receives a score w j · α τ −1 j (i) from voter v j . By re-indexing all of the candidates, we can set, without loss of generality, c m as the winner in the absence of bribery.
Adversarial models. We consider an attacker that does not belong to C ∪ V but attempts to manipulate the election by bribing some voters. Suppose voter v j has a bribing price p b j , meaning that v j , upon receiving a bribery of amount p b j from the attacker, will change its preference list to the list given by the attacker. The attacker has a total budget B. As in the bribery problem, we also consider two kinds of attackers: -Constructive attacker: This attacker attempts to make a designated candidate win the election, meaning that the designated candidate is the only candidate who gets the highest score. -Destructive attacker: This attacker attempts to make a designated candidate lose the election, meaning that there is another candidate that gets a strictly higher score than the designated candidate does.
Protection. In the protection problem, voter v j , upon receiving an award of amount p a j (or awarding price) from the defender, will always report its preference list faithfully and cannot be bribed. Note that p a j may have multiple interpretations, such as monetary award, economic incentives or the cost of iso-lating voters from bribery. We say a voter v j is awarded if v j receives an award of p a j . Problem statement. We formalize our problem as follows.
The constructive protection problem (i.e., protecting elections against constructive attackers): Input: A set C of m candidates. A set V of n voters, each with a weight w j ∈ Z >0 , a preference list τ j , an awarding price of p a j ∈ Z >0 and a bribing price of p b j ∈ Z >0 . A scoring rule for selecting a single winner. A defender with a defense budget F ∈ Z ≥0 . An attacker with an attack budget B ∈ Z ≥0 attempting to make candidate c m win the election. Output: Decide whether there exists a V F ⊆ V such that , c m does not get a strictly higher score than any other candidate despite the attacker bribing the voters belonging to V B (i.e., bribing V B ).
The destructive protection problem (i.e., protecting elections against destructive attackers): Input: A set C of m candidates. A set V of n voters, each with a weight w j ∈ Z >0 , a preference list τ j , an awarding price of p a j ∈ Z >0 and a bribing price of p b j ∈ Z >0 . A scoring rule for selecting a single winner. Suppose c m is the winner if no voter is bribed. A defender with a defense budget F ∈ Z ≥0 . An attacker with an attack budget B ∈ Z ≥0 attempting to make c m lose the election by making c ∈ C \ {c m } get a strictly higher score than c m does. Output: Decide if there exists a V F ⊆ V such that j:vj ∈VF p a j ≤ F ; and for any subset V B ⊆ V \ V F such that j:vj ∈VB p b j ≤ B, no candidate c ∈ C \ {c m } can get a strictly higher score than c m does despite the attacker bribing V B .
Further terminology and notations. We denote by W (c i ) the total score obtained by candidate c i in the absence of bribery (i.e., no voter is bribed). If the defender can select V F such that no constructive or destructive attacker can succeed, we say the defender succeeds. We call our problem as the (constructive or destructive) weighted-$-protection problem, where "weighted" indicates that the voters are weighted and "$" indicates that arbitrary awarding and bribing prices are involved. In addition to investigating the general weighted-$-protection problem, we also investigate the following special cases of it: the $-protection problem with w j = 1 for each j (i.e., the voters are not weighted); -the weighted-protection problem with p a j = p b j = 1 for each j (i.e., voters are associated with the unit awarding price and the unit bribing price); the unit-protection problem with w j = p a j = p b j = 1 for each j (i.e., voters are not weighted, and are associated with the unit awarding price and the unit bribing price).
the symmetric protection problem with p a j = p b j for each j (i.e., the awarding price and the bribing price are always the same), while noting that different voters may have different prices.

The Weighted-$-Protection Problem
The goal of this subsection is to prove the following theorem. Proof sketch. The proof of Lemma 2 follows from De-Negre (DNeg) variant of bi-level knapsack problem, which is proved to be Σ p 2 -hard by Caprara et al. [3]. We give a brief explanation. In this De-Negre variant, there are an adversary and a packer. The adversary has a reserving budgetF and the packer has a packing budgetB. There is a set of n items, each having a pricep a j to the adversary, a pricep b j to the packer, and a weightw j =p b j to both the adversary and the packer. The adversary first reserves a subset of items whose total price is no more thanF . Then the packer solves the knapsack problem with respect to the remaining items that are not reserved; i.e., the packer will select a subset of the remaining items whose total price is no more thanB but their total weight is maximized. The De-Negre variant asks if the adversary can reserve a proper subset of items such that the total weight of the unreserved items that are selected by the packer is no more than some parameter W . The De-Negre variant is similar to the weighted-$-protection protection problem, because we can view the defender and attacker in the protection problem respectively as the adversary and packer in the bi-level knapsack problem. In the case of a single-winner election with m = 2 candidates, the goal of the defender is to assure that the constructive attacker cannot make the loser get a strictly higher score than the winner by bribing. This is essentially the same as ensuring that the constructive attacker cannot bribe a subset of non-awarded voters whose total weight is higher than a certain threshold, which is the same as the bi-level knapsack problem.

The Weighted-Protection Problem
This is a special case of the weighted-$-protection problem when p a j = p b j = 1. The following theorem used by Faliszewski et al. [8] was originally proved for another problem. In our context, F = 0 and thus V F = ∅, it is NP-hard to decide if the constructive attacker can succeed or, equivalently, if the defender cannot succeed. Hence, it is coNP-hard to decide if the defender can succeed and Theorem 2 follows. Theorem 2. (By Faliszewski et al. [8]) If m is a constant, the constructive weighted-protection problem is coNP-hard for any scoring rule that α 2 , α 3 , . . . , α m are not all equal (i.e., it does not hold that α 2 = α 3 = . . . = α m ).
In contrast, the destructive version is easy. Using the fact that m, the number of candidates, is a constant, we can prove the following Theorem 3 through suitable enumerations.
Theorem 3. If m is a constant, then the destructive weighted-protection problem is in P for any scoring rule.

The $-Protection Problem
This is the special case of the protection problem with w j = 1 for every j. The following two theorems illustrate the significant difference (in terms of complexity) between the general problem and its special case with symmetricity (i.e., p a j = p b j ).

The Case of Constructive Attacker
The following Theorem 6 shows Σ p 2 -hardness for the most special cases of the constructive weighted-$-protection problem, namely w j = p a j = p b j = 1 (unitprotection). It thus implies readily the Σ p 2 -hardness for the more general constructive $-protection and constructive weighted-protection.
Membership in Σ p 2 follows directly from Lemma 1. To prove Theorem 6, it suffices to show the following. To prove Lemma 3, we reduce from a variant of the ∃∀ 3 dimensional matching problem (or ∃∀3DM), which is called ∃∀3DM ′ and defined below. The classical ∃∀ 3DM is Σ p 2 -hard proved by Mcloughlin [16]. By leveraging the proof by Mcloughlin [16], we can show the Σ p 2 -hardness of the ∃∀3DM ′ problem.
∃∀3DM ′ : Given a parameter t, three disjoint sets of elements W , X, Y of the same cardinality, and two disjoint subsets is not a perfect matching (where a perfect matching is a subset of triples in which every element of W ∪ X ∪ Y appears exactly once)?

Proof (Proof of Lemma 3).
Given an arbitrary instance of ∃∀ 3DM ′ , we construct an instance of the constructive unit-protection problem in r-approval election as follows. Recall that r = 4 and thus every voter votes for 4 candidates.
There are 3n + 2 key candidates, including: -3n key candidates, each corresponding to one distinct element of W ∪ X ∪ Y and we call them element candidates. The score of every element candidate is n + ξ; -one key candidate called leading candidate, whose total score is n + t + ξ − 1; -one key candidate called designated candidate, whose total score is ξ.
Besides key candidates, there are also many dummy candidates, each of score either 1 or m 1 − t + 1. The number of dummy candidates will be determined later.
There are m 1 + m 2 (m 1 − t + 1) key voters, including: -m 1 key voters, each corresponding to a distinct triple in M 1 and we call them M 1 -voters. For each (w i , x j , y k ) ∈ M 1 , the corresponding voter votes for the 3 candidates corresponding to elements w i , x j , y k together with the leading candidate; -m 2 · (m 1 − t + 1) key voters, each distinct triple in M 2 corresponds to exactly m 1 −t+1 voters and we call them M 2 -voters. For every (w i , x j , y k ) ∈ M 2 , each of its m 1 − t+ 1 corresponding voters vote for the 3 candidates corresponding to elements w i , x j , y k together with one distinct dummy candidate. Since the m 1 − t + 1 voters are identical, we can view them as m 1 − t + 1 copies, i.e., every M 2 -voter has m 1 − t + 1 copies. Besides key voters, there are also sufficiently many dummy voters. Each dummy voter votes for exactly one key candidate and 3 distinct dummy candidates. Dummy voters and dummy candidates are used to make sure that the score of key candidates are exactly as we have described. More precisely, if we only count the scores of key candidates contributed by key voters, then the element candidate corresponding to z ∈ W ∪ X ∪ Y has a score of d is the number of occurrences of z in the triple set M i for i = 1, 2, and the leading candidate has a score of m 1 . Hence, there are exactly n + ξ − d(z) dummy voters who vote for the element candidate corresponding to z, and n + t + ξ − 1 − m 1 dummy voters who vote for the leading candidate.
As the leading candidate is the current winner, the constructive unit-protection problem asks whether the election can be protected against an attacker attempting to make the designated candidate win. The defense budget is F = m 1 − t and the attack budget is B = n. In the following we show that the defender succeeds if and only if the given ∃∀ 3DM ′ instance admits a feasible solution U 1 .
"Yes" Instance of ∃∀ 3DM ′ → "Yes" Instance of Constructive Unit-Protection. Suppose the instance of ∃∀ 3DM ′ admits a feasible solution U 1 , we show that the answer for constructive unit-protection problem is "Yes".
Recall that each M 1 -voter corresponds to a distinct triple (w i , x j , y k ) in M 1 and votes for 4 candidates -the leading candidate and the three candidates corresponding to w i , x j , y k . We do not award M 1 -voters corresponding to the triples in U 1 , but award all of the remaining M 1 -voters. The resulting cost is In what follows we show that after awarding voters this way, the attacker cannot make the designated candidate win.
Suppose on the contrary, the attacker can make the designated candidate win by bribing α ≤ t voters among the M 1 -voters, β ≤ m 2 voters among the M 2 -voters, and γ dummy voters. We claim that the following inequalities hold: Inequality (1a) follows from the fact that the attack budget is n and the attacker can bribe at most n voters. Inequality (1b) holds because of the following. Given that a candidate can get at most one score from each voter and that the attacker can bribe at most n voters, bribing voters can make the designated candidate obtain a score at most n + ξ. Hence, the score of each key candidate other than the designated one should be at most n + ξ − 1. Recall that without bribery, each of the 3n element candidate has a score of n + ξ and the leading candidate has a score of n + t + ξ − 1. Hence, the attacker should decrease at least 1 score from each element candidate and t scores from the leading candidate, leading to a total score of 3n + t. Note that an M 1 -voter contributes 1 score to 4 key candidates, therefore it contributes in total a score of 4 to the key candidates.
Similarly an M 2 -voter contributes a score of 3, and a dummy voter contributes a score of 1 to the key candidates. Therefore, by bribing (for example) an M 1voter, the total score of all the element candidates and the leading candidate can decrease by at most 4. Thus, inequality (1b) holds. In the following we derive a contradiction based on Inequalities (1a) and (1b). By plugging γ ≤ n − α − β into Inequality (1b), we have 3α + 2β ≥ 2n + t. Since β ≤ n − α, we have 3α + 2β ≤ α + 2n ≤ 2n + t. Hence, 3α + 2β = α + 2n = 2n + t, and we have α = t and β = n − t. Note that the defender has awarded every M 1voter except the ones corresponding to U 1 , where |U 1 | = t. Hence, every voter corresponding to the triples in U 1 is bribed. Furthermore, as Inequality (1b) is tight, bribing voters makes the designated candidate have a score of n + ξ, while making each of the other key candidates have a score of n + ξ − 1. This means that the score of each element candidate decreases exactly by 1. Hence, the attacker has selected a subset of M 2 -voters such that together with the M 1voters corresponding to triples in U 1 , these voters contribute exactly a score of 1 to every element candidate. Let U 2 be the set of triples to which the bribed M 2 -voters correspond, then U 1 ∪ U 2 forms a 3-dimensional matching, which is a contradiction to the fact that U 1 is a feasible solution to the ∃∀ 3DM ′ instance. Thus, the attacker cannot make the designated candidate win and the answer for the constructive unit-protection problem is "Yes". "No" Instance of ∃∀ 3DM ′ → "No" Instance of Constructive Unit-Protection. Suppose for any U 1 ⊆ M 1 , |U 1 | = t there exists U 2 ∈ M 2 such that U 1 ∪ U 2 is a perfect matching, we show that the answer to the constructive unitprotection problem is "No". Consider an arbitrary set of voters awarded by the defender. Among the awarded voters, let H be the set of triples that corresponds to the awarded M 1 -voters. As |H| ≤ m 1 − t, |M 1 \ H| ≥ t. We select an arbitrary subset H 1 ⊆ M 1 \ H such that |H 1 | = t. There exists some H 2 ⊆ M 2 such that H 1 ∪ H 2 is a perfect matching, and we let the attacker bribe the set of voters corresponding to triples in H 1 ∪ H 2 . Note that this is always possible as every M 2 -voter has m 1 − t + 1 copies, so no matter which M 2 -voters are awarded the briber can always select one M 2 -voter corresponding to each triple in H 2 . It is easy to see that by bribing these voters, the score of every element candidate decreases by 1, and the score of the leading voter decreases by t. Meanwhile, let each bribed voter vote for the designated candidate and three distinct dummy candidates, then the designated candidate has a score of n + ξ and becomes a winner, i.e., the answer to the constructive unit-protection problem is "No". ⊓ ⊔ Remark. The proof of Lemma 3 can be easily modified to prove the Σ p 2 -hardness of r-approval constructive unit-protection problem for any fixed r ≥ 4. Specifically, we can make the same reduction, and add dummy candidates such that every voter additionally votes for exactly r − 4 distinct dummy candidates.

The Case of Destructive Attacker
Theorem 7. Both r-approval destructive weighted-protection and r-approval (symmetric) $-protection problems are NP-complete.
The proof of Theorem 7 is based on a crucial observation of the equivalence between the destructive weighted-$-protection problem (under an arbitrary scoring rule) and the minmax vector addition problem we introduce (see Appendix 7.1). The full proof of Theorem 7 can be found in Appendix 7.6. Table 1. Summary of results for single-winner election under the r-approval scoring rule: "Symmetric" means p a j = p b j for every j and "asymmetric" means otherwise; hardness results that are proved for the case with only two candidates (i.e., m = 2) are marked with a "⋄" (Note that when m = 2, the 1-approval rule is the same as the plurality, veto or Borda scoring rule. It can be shown that with a slight modification, the hardness results hold for any non-trivial scoring rule); algorithmic results (marked with a "P") hold for arbitrary scoring rules; the complexity of the protection problem against a destructive attacker with wj = p a j = p b j = 1 remains open; for most variants of the protection problem against a constructive attacker, we only provide hardness results and we do not know yet whether or not they belong to the class of coNP-complete or Σ p 2 -complete proble.
We remark three natural open problems for future research. One is the complexity of the destructive protection problem with w j = p a j = p b j = 1. It is not clear whether the problem is in P or is NP-complete. Another is the constructive protection problem with p a j = p b j = 1 and arbitrary voter weights. We only show its coNP-hardness, it is not clear whether or not this problem is coNP-complete. The third problem is the complexity of r-approval constructive unit-protection problem when r = {1, 2, 3} as our hardness proof only holds when r ≥ 4.

Conclusion
We introduced the protection problem and characterized its computational complexity. We showed that the problem, in general, is Σ p 2 -complete, and identified settings in which the problem becomes easier. Moreover, we showed the protection problem in some parameter settings is polynomial-time solvable, suggesting that these parameter settings can be used for real-work election applications.
In addition to the open problems mentioned in Section 5, the following are also worth investigating. First, our hardness results would motivate the study of approximation or FPT (fixed parameter tractable) algorithms for the protection problem. Note that even polynomial time approximation schemes can exist for Σ p 2 -hard problems (see, e.g., By Caparara et al. [3]). It is thus desirable that a similar result can be obtained for some variants of the protection problem. Second, how effective is this approach when applied towards the problem of defending against other types of attackers that can, e.g., add or delete votes? Third, much research remains to be done in extending the protection problem to accommodate other scoring rules such as Borda and Copeland.

Destructive Weighted-Protection -an Equivalent Formulation
We provide an equivalent formulation of the destructive weighted-protection problem under any scoring rule α = (α 1 , · · · , α m ), which will be very useful for several proofs throughout this paper.
The minmax vector addition problem: where · ∞ is the infinity norm (i.e., the maximal absolute value among the m − 1 coordinates).

Lemma 4. The answer to the destructive weighted-$-protection problem is "Yes" if and only if the answer to the corresponding minmax vector addition problem is "Yes".
Proof. A "Yes" Instance of Minmax Vector Addition → A "Yes" Instance of Destructive Weighted-$-Protection. Suppose the answer to the minmax vector addition problem is "Yes." Then, there exists some V * F ⊆ V such that for any For showing a contradiction, suppose the answer for the destructive weighted-$protection problem is "No". In this case, even if the defender awards the voters in V * F , the attacker can still make c m lose by bribing some subset V * B of voters. Note that if c m does not win, there must exist some other candidate, say, c i , who gets a strictly higher score than c m after the attacker bribes some voters. Let us compare their scores before and after bribing voters. Before bribing voters, the scores of c i and c m are Λ(c i ) and Λ(c m ), respectively. Recall that a candidate c k is at the position of τ −1 j (k) on the preference list of v j , therefore any v j ∈ V * B contributes a score of α τ −1 j (i) to Λ(c i ), and contributes a score of α τ −1 j (m) to Λ(c m ). After bribing voters, the preference list of v j is changed, but regardless of the change, v j contributes at least α m to c m and at most α 1 to c i . Let the scores of c i and c m after bribing voters be Λ ′ (c i ) and Λ ′ (c m ), respectively. Then, it follows that which contradicts Eq. (2). Thus, the answer to the destructive weighted-$protection problem is "Yes".
A "Yes" Instance of Destructive Weighted-$-Protection → A "Yes" Instance of Minmax Vector Addition. Suppose the answer to the destructive weighted-$-protection problem is "Yes" by awarding the voters in V * F . We show that the answer to the corresponding instance of minmax vector addition problem is "Yes". Suppose on the contrary the answer is "No." Then, for V * Consequently, there must exist some 1 ≤ i ≤ m−1 such that Λ(c i )+ j:vj ∈V * B ∆ ij > Λ(c m ). By plugging in ∆ ij , we have This means that if the defender awards the voters in V * F , then the attacker can bribe the voters in V * B to change their preference lists such that for any v j ∈ V * B , candidate c i is on top of the list and c m is at bottom of the list. By doing this, c i gets a strictly higher score than c m . This contradicts the fact that the answer to the destructive weighted-$-protection problem is "Yes". Hence, the answer to the minmax vector addition problem is "Yes". ⊓ ⊔

Voter Dominance and Preliminary Observations
Let S m be the set of permutations over {c 1 , c 2 , . . . , c m }. Each element of S m can be a preference list. Let V h ⊆ V be the set of voters whose preference list is the h-th element of S m . For two voters v j and v j ′ , we say v j dominates v j ′ (or v j ′ is dominated by v j ), denoted by v j ′ ≺ v j , if any of the following two conditions hold: (i) The following holds and at least one of the inequalities is strict: (ii) The following holds: Note that the domination relation is only defined between the voters who have the same preference. Intuitively, if v j ′ ≺ v j , then v j is more "important" than v j ′ because v j has a greater weight but is "cheaper" to bribe or award (i.e., more valuable to both the attacker and the defender).
We have the following lemmas.

Lemma 5. Consider the destructive weighted-$-protection problem with V F ⊆ V being the set of awarded voters. Suppose the attacker can succeed by bribing a subset
, then the attacker can succeed by bribing Towards the proof, we need Lemma 4, which states that the destructive weighted-$-protection problem is equivalent to another problem called minmax vector addition. The reader may refer to Section 4.2 for the definition of this problem. The following observation follows directly from the definition of ∆ ij which is included in the definition of minmax vector addition.
Assuming Lemma 4, we can prove Lemma 5 as follows.
Proof (Proof of Lemma 5). We prove the lemma by applying an exchange argument to the minmax vector addition problem, which is equivalent to the destructive weighted-$-protection by Lemma 4. Suppose by bribing voters in V B the destructive attacker can make c m lose. Then, it follows that j:vj ∈VB p b j ≤ B and ||Λ + j:j∈VB As That is, the briber can also win by bribing voters in ( Consider the destructive weighted-$-protection problem. Suppose the defender succeeds by awarding a subset and v j ∈ V F , then the defender can succeed by awarding Proof. We again use an exchange argument to the minmax vector addition prob- Suppose on the contrary that the defender cannot win by fixing voters in We argue that the defender cannot win either by fixing voters in V A ∪{v j ′ }, which is a contradiction. Suppose the defender fixes voters in V A ∪ {v j ′ }. There are two possibilities. If v j ′ ∈ V B , then we let the briber bribe voters in V B . It is obvious that the briber can win. Otherwise, v j ′ ∈ V B , then we let the briber bribe voters Hence, the lemma is true.

⊓ ⊔
We sayV ⊆ V is maximal (with respect to V) if for anyv ∈V, there is no v ∈ V \V that can dominatev. That is,V contains the most important voters. The following corollary follows directly from the preceding two lemmas.
Corollary 1 Consider the destructive weighted-$-protection problem. Without loss of generality, we can assume that V F is maximal with respect to V and V B is maximal with respect to V \ V F .
Unfortunately, Corollary 1 does not hold for the constructive weighted-$protection problem, which is significantly different from the destructive version of the protection problem in terms of computational complexity. Nevertheless, similar results hold for the unweighted constructive problem.

then the briber can also win by bribing voters in
Proof. Again, we prove by an exchange argument. Suppose by bribing voters in V B the constructive briber can make c i win. Now we consider the following procedure: we change the preference list of v j into the same one as that of v j ′ , and meanwhile, restore the preference list of v j ′ to the original one. As voters have the same weight, this procedure does not change the total score of every candidate, and c i is thus still the winner. Furthermore, this procedure is equivalent as we bribe (V B \ {v j ′ }) ∪ {v j }. Since v j dominates v j ′ , the total cost of bribing (V B \ {v j ′ }) ∪ {v j } is no more than that of bribing V B . Hence, the lemma is true.
⊓ ⊔ Lemma 8. In the constructive $-bribery-protection problem, suppose the defender can win by fixing a subset

then the defender can also win by fixing voters in
Proof. Suppose on the contrary that the defender cannot win by fixing voters in Then the constructive briber can win by bribing voters in some subset V B ⊆ V \ V ′ F . There are two possibilities. If v j ′ ∈ V B , then even if the defender fixes V F the briber can still bribe V B and make c i win, which is a contradiction. Otherwise v j ′ ∈ V B . If the defender fixes V F , we let the briber bribe (V B \ {v j ′ })∪{v j }. According to Lemma 7, if the briber can win by bribing V B , he/she can also win by bribing (V B \ {v j ′ }) ∪ {v j }, again contradicting the fact that the defender can succeed by awarding V F .

⊓ ⊔
The above Lemmas implies the following.
Corollary 2 Without loss of generality, we can assume that V F is maximal with respect to V, and V B is maximal with respect to V \ V F in the constructive $-bribery-protection problem.

Proofs Omitted in Section 3.1
Recall that our goal is to prove Theorem 1.
Theorem 1. For any non-trivial scoring rule, both the constructive and destructive weighted-$-protection problem, is Σ p 2 -complete. We first show Σ p 2 -membership. Lemma 1. For any non-trivial scoring rule, both the constructive and destructive weighted-$-protection problems are in Σ p 2 . For ease of proof, we use the following definition of Σ p 2 from [19] (see Theorem 3 therein).
Proof (Proof of Lemma 1). Given an instance I of the constructive or destructive weighted-$-protection problem, we want to know if there exists a subset V F such that j:vj ∈VF p a j ≤ F and for any subset V B ⊆ V \V F with j:vj ∈VB p b j ≤ B and any preference listτ j for v j ∈ V B , the following property R(I, V F , V B ∪ {τ j |v j ∈ V B }) is true: By bribing voter in V B and change the preference list of each v j ∈ V B toτ j , a constructive attacker cannot make candidate c i win, or a destructive attacker cannot make c m lose. It is easy to see that the property R(I, V F , V B ∪ {τ j |v j ∈ V B }) can be verified in polynomial time, therefore Lemma 1 is proved.
⊓ ⊔ Now we prove the Σ p 2 -hardness. Note that in case of m = 2, destructive weighted-$-bribery-protection is equivalent to constructive weighted-$-bribery-protection. We prove the Lemma 2 for the protection problem under plurality. With slight modification the proof works for any non-trivial scoring protocol for two candidates.
We reduce from the De-Negre (DNeg) variant of bi-level knapsack problem, which is proved to be Σ p 2 -hard by Caprara et al. [3]. Before we describe the bi-level knapsack problem, we first introduce the classical knapsack problem, which is closely related. In the knapsack problem, given is some fixed budget B together with a set S of items, each having a pricep a j and a weightw j . The goal is to select a subset of items whose total price is no more than the given budget and the total weight is maximized. We denote by KP (S,B) the optimal objective value of the knapsack problem.
In the De-Negre (DNeg) variant of bi-level knapsack problem, there is an adversary and a packer. The adversary has a reserving budgetF and the packer has a packing budgetB. There is a set of n items, each having a pricep a j to the adversary,p b j to the packer and a weightw j =p b j (to both the adversary and the packer). The adversary first reserves a subset of items whose total prices is no more thanF . Then the packer solves the knapsack problem with respect to the remaining items that are not reserved, i.e., the packer will select a subset of remaining items whose total price is no more thanB such that their total weight is maximized. The DNeg variant of the bi-level knapsack problem asks for a proper subset of items reserved by the adversary such that the total weight of items selected by the packer is minimized. More precisely, the problem can be formulated as a bi-level integer programming as follows.
The DNeg variant of bi-level knapsack problem: where y 1 , y 2 , · · · , y n solves the following: The decision version of the DNeg variant of bi-level knapsack problem asks whether there exists a feasible solution with the objective value at most W . The following lemma is due to Caprara et al. [3].

Lemma 9 (By Caprara et al. [3]). The decision version of the DNeg variant of bi-level knapsack problem is
Based on the above lemma, we are able to prove Lemma 2.
Proof (Proof of Lemma 2). Given an arbitrary instance of the (decision version of) DNeg variant of bi-level knapsack problem, we construct an election instance as follows. There are m = 2 candidates. The defense and attack budgets are F =F and B =B, respectively. There are n + 2 voters: n key voters v 1 , v 2 , · · · , v n who vote for c 2 , each having an awarding price p a j =p a j , a bribing price p b j =p b j , and a weight w j =p b j . -one dummy voter v n+1 who votes for c 2 whose weight is 2W , awarding price is F + 1 and bribing price is B + 1. -one dummy voter v n+2 who votes for c 1 whose weight is n j=1p b j , awarding price is F + 1 and bribing price is B + 1.
Obviously c 2 is the original winner. We show in the following that the constructed election instance is secure if and only if the DNeg variant of bi-level knapsack problem admits a feasible solution with an objective value at most W .
Suppose the DNeg variant of bi-level knapsack problem admits a feasible solution with an objective value at most W , and let x * i be such a solution. As n j=1p a j x * j = n j=1 p a j x * j ≤F = F , we let the defender award all the voters such that x * j = 1, i.e., let V F = {v j |x * j = 1}. According to the fact that the objective value of the bi-level knapsack problem is at most W , and the fact that the two dummy voters can never be bribed, it follows that the optimal objective value of the following knapsack problem is at most W : Thus, with a budget of B the the briber can never bribe key voters whose total weight is more than W . Note that originally the total weight of voters voting for c 2 is 2W + n j=1 p b j , and the total weight of voters voting for c 1 is n j=1 p b j , the briber cannot succeed and the election is thus secure.
Suppose the election is secure. Then there exists some V F such that we can say j:vj ∈VF p a j ≤ F and if voters in V F are fixed, no briber can succeed. Note that the two dummy voters can never be protected nor bribed, whereas V F ⊆ {v 1 , v 2 , · · · , v n }. Thus, among voters in {v 1 , v 2 , · · · , v n } \ V F , within a budget of B the briber cannot bribe voters whose total weight is more than W . This is equivalent as saying that by setting x j = 1 for v j ∈ V F and x j = 0 otherwise, the knapsack problem for y j does not admit a feasible solution with an objective value more than W . Hence, the objective value of the given DNeg variant of bi-level knapsack problem is at most W . ⊓ ⊔

Proofs Omitted in Section 3.2
Theorem 3. If m is a constant, then the destructive weighted-protection problem is in P for any scoring rule.
Proof. The theorem is proved by trying all different possible V F and check whether the attacker can succeed for each of them. By Corollary 1, for voters having the same preference, V F contains voters of the largest weights. Hence to determine V F , it suffices to know the number of voters having each preference in V F . There are at most m! different preferences, and consequently at most n m! different kinds of V F , which is polynomial when m is constant. For each possible choice of V F , we check whether the attacker can succeed by trying all possible V B and all possible ways of changing their preferences. Firstly, by Corollary 1, for voters in V \ V F that have the same preference list, V B contains the ones of the largest weights, hence using a similar argument we know there are at most n m! different kinds of V B . Given V F and V B , it remains to determine how the preference lists of voters in V B should be changed. Note that we do not need to specify how the preference list is changed for each v j ∈ V B . Instead, we only need to determine the number of voters in V B that are changed to each preference list, which gives rise to at most n m! possibilities. Therefore, overall there are at most n 3m! different possibilities regarding V F , V B and how to alter the preference lists of voters in V B , which can be enumerated efficiently when m is a constant.

⊓ ⊔
We remark that an argument similar to the one we used to prove Theorem 3 was used by Faliszewsk et al. [8].

Proofs omitted in Section 3.3
Theorem 4. For any non-trivial scoring rule, both the constructive and destructive $-protection problems are NP-complete.
To prove Theorem 4, we first show the problem belongs to NP in Lemma 10 and then show its NP-hardness in Lemma 11. Again, in case of two candidates, the constructive and destructive variants are identical and it suffices to prove the theorem under the scoring rule of plurality.
Towards the proof, we need the following intermediate problems. Balanced Partition: Given a set of positive integers {a 1 , a 2 , · · · , a 2n } where a 1 ≤ a 2 ≤ · · · ≤ a 2n and an integer q such that 2n j=1 a j = 2q. Determine whether there exists a subset S of n integers such that i:ai∈S a i = q.
The balanced partition problem is a variant of the partition problem (in which S is not required to contain exactly n integers). The NP-completeness of the balanced partition problem is a folklore result, which follows from a slight modification on NP-completeness proof for the partition problem given by Garey and Johnson [11].
Using the balanced partition problem, we are able to show the NP-hardness of the following problem in Lemma 12.
Proof. Membership in NP is straightforward. We show balanced partition ′ is NP-hard in the following via reduction from balanced partition.
Given an instance of the balanced partition problem where the integers are a 1 ≤ a 2 ≤ · · · ≤ a 2n and q = 1/2 · 2n j=1 a j , we construct an instance of the balanced partition ′ problem by adding 4n integers, each of value 3q.
We first show that the constructed instance is a feasible instance. Obviously every additional integer is larger than any a j where j ≤ 2n. Let the additional integers be a 2n+1 , a 2n+2 , · · · , a 6n . In the constructed instance there are 2n ′ = 6n elements, with the summation of all integers being 2q + 12nq. Let q ′ = q + 6nq. Obviously a n ′ +1 + a n ′ +2 + · · · + a 2n ′ −1 = 9nq > q ′ + 1. Thus, the constructed instance is a feasible instance of the balanced partition ′ problem.
We show that the constructed instance admits a feasible partition if and only if the given balanced partition instance admits a feasible solution.
If the given balanced partition instance admits a feasible solution, then obviously the constructed balanced partition ′ problem admits a feasible solution (by adding 2n of the additional integers to both sides).
Suppose the constructed balanced partition ′ instance admits a feasible solution. We claim that among the 4n additional integers, there are exactly 2n of them in S. Otherwise S contains either at most 2n − 1 of them or at least 2n + 1 of them. By symmetry we assume without loss of generality that S contains at most 2n − 1 of them, then all integers in S add up to at most (2n − 1) · 3q + 2q < q ′ = q + 6nq, which is a contradiction. Thus, S contains exactly 2n additional integers, implying that the remaining n integers adding up to q, i.e., the given balanced partition instance admits a feasible solution.
⊓ ⊔ Proof (Proof of Lemma 11). We will prove the NP-hardness for an election with only two candidates under 1-approval (plurality). Recall that in this case the constructive and destructive protection problem are the same. We reduce from the balanced partition ′ problem. Given an arbitrary instance of the balanced partition ′ problem, we construct an instance of the $-briberyprotection problem such that the answer to the problem is "Yes" if and only the balanced partition ′ instance admits a feasible solution.
Obviously c 2 is the original winner. We show that the answer to the constructed $-bribery-protection instance is "Yes" if and only if the balanced partition ′ problem admits a feasible solution.
Suppose the given balanced partition ′ instance admits a feasible solution S. Now we let the defender fix the n key voters whose awarding price is 4q + a j where a j ∈ S. It is easy to verify that the total awarding price is 4nq + q = F , which stays within the defense budget. We argue that, no briber can alter the election result with a budget of B. Let V F be the set of fixed voters. Suppose on the contrary there is a briber who can make c 1 win. Given that the total attack budget is B, the briber can only bribe key voters. Furthermore, the briber has to bribe at least n voters. As |V F | = n, the briber has to bribe all voters in V * \ V F . However, which is a contradiction. Thus, the answer to the constructed $-bribery-protection instance is "Yes". Suppose the answer to the constructed $-bribery-protection instance is "Yes". Note that in total there are 4n − 1 voters voting for c 2 and 2n voters voting for c 1 . Thus any briber who wants to alter the election result has to bribe at least n voters who originally vote for c 2 . Since the 2n − 1 dummy jobs voting for c 2 can never be protected nor bribed, we can fix a subset V F ⊆ V * such that no briber can bribe n or more voters from V * \ V F with a budget of B. We have the following claim.
Proof (Proof of Claim 7.5). We first show that |V F | ≤ n. Suppose on the contrary that |V F | ≥ n + 1. Note that any key voter has an awarding price of at least 4q, thus the total awarding price is at least 4(n + 1)q. However, F = 4qn + q < 4(n + 1)q, which is a contradiction.
We now show that |V F | ≥ n. Suppose on the contrary that |V F | ≤ n − 1. Then there are at least n + 1 key voters that can be bribed and we bribe the cheapest n voters. As p b 1 ≥ p b 2 ≥ · · · ≥ p b 2n , the total bribing price of the cheapest n voters among any n + 1 voters is at most p b n + p b n+1 + · · · + p b 2n−1 = 4qn − (a n + a n+1 + · · · + a 2n−1 ) ≤ 4qn − (q + 1) = B, whereas the briber can always bribe the cheapest n voters and let c 2 win, which contradicts the fact that the answer to the $-bribery-protection instance is "Yes". Hence |V F | ≥ n.
Using the fact that |V F | = n, we have j:vj ∈VF a j ≥ q.
Thus, j:vj ∈VF a j = q, i.e., the given balanced partition ′ instance admits a feasible solution.

⊓ ⊔
The symmetric $-protection problem (i.e., p a j = p b j ), however, is significantly easier, as shown by Theorem 5.
Theorem 5. For constant m, both destructive and constructive symmetric $protection problems are in P for any scoring rule.
Proof. The proof idea is the same as that of Theorem 3, namely by trying all different possible V F . For each V F , we try all possible V B 's and all possible ways of altering the preference of voters in V B . Note that every voter has the same weight and satisfies that p a j = p b j . Therefore, a voter with a smaller (awarding and bribing) price always dominates a voter with a larger price. By Corollary 1 and Corollary 2, for the voters having the same preference, V F contains the voters that have the smallest prices. Therefore, in order to determine V F , it suffices to know the number of voters that have the same preference, implying that there are at most n m! different kinds of V F 's. Similarly, given a V F , there are at most n m! different kinds of V B 's. Using the same argument as that of Theorem 3, for every V F and V B , there are at most n m! ways of altering the preferences of the voters in V B . Therefore, there are n 3m! different possibilities in total, which can be enumerated efficiently when m is a constant. ⊓ ⊔

Proofs Omitted in Section 4.2
The goal is to prove Theorem 7.
Theorem 7. Both r-approval destructive weighted-protection and r-approval (symmetric) $-protection problems are NP-complete.
Towards the proof, we first show the NP-hardness.
Lemma 13. The r-approval destructive weighted-protection problem is NP-hard for any r ≥ 3.