--- abstract: | An important problem in computational social choice theory is the complexity of undesirable behavior among agents, such as control, manipulation, and bribery in election systems. These kinds of voting strategies are often tempting at the individual level but disastrous for the agents as a whole. Creating election systems where the determination of such strategies is difficult is thus an important goal. An interesting set of elections is that of scoring protocols. Previous work in this area has demonstrated the complexity of misuse in cases involving a fixed number of candidates, and of specific election systems on unbounded number of candidates such as Borda. In contrast, we take the first step in generalizing the results of computational complexity of election misuse to cases of infinitely many scoring protocols on an unbounded number of candidates. Interesting families of systems include $k$-approval and $k$-veto elections, in which voters distinguish $k$ candidates from the candidate set. Our main result is to partition the problems of these families based on their complexity. We do so by showing they are polynomial-time computable, NP-hard, or polynomial-time equivalent to another problem of interest. We also demonstrate a surprising connection between manipulation in election systems and some graph theory problems. author: - | Andrew Lin\ Department of Computer Science\ Rochester Institute of Technology\ Rochester, NY 14623, USA\ `michaelwilson@example.net`\ title: '**The Complexity of Manipulating $k$-Approval Elections [^1]** ' --- Elections are a means for choosing one or more candidates given the preferences of individuals to arrive at a decision that attempts to maximize the collective welfare of the individuals (see also @Brams). A voting system contains both rules for valid voting, and how one yields a final outcome given the preferences of individual voters. The choice of which rule one uses to choose the winner(s) may affect both the outcome of the election and the behavior of each voter. Voters may be unweighted or weighted, and need not count equally toward the final result. The computational theory behind voting, as well as systems beyond that of the obvious majority and plurality, were first studied during the French Revolution. Two notable early theorists in this field were Jean-Charles de Borda @Borda and Marquis de Condorcet @Condorcet. Borda introduced the system used for electing members to the French Academy of Sciences in 1770. The Borda system favors candidates that are somewhat liked by a lot of voters. Condorcet believed the winner should be one who fares well in pairwise comparisons of the candidates, a concept that is poorly captured by the Borda election, as it does not view pairs of candidates. Condorcet discovered that, among voters with transitive preferences (meaning that if a voter prefers $x$ to $y$ and $y$ to $z$, he or she will prefer $x$ to $z$), majority preferences between pairs of candidates may be intransitive. This means that among candidates $x$, $y$, and $z$, it is possible for a majority of voters to prefer $x$ to $y$, $y$ to $z$, and $z$ to $x$, and thus a Condorcet winner, who outperforms each alternative in a pairwise election, may not exist. The result that the pairwise preferences of the aggregate of rational voters may be irrational is known as the Condorcet paradox. Beyond the applications in social sciences, in more recent times voting has also been used in many interesting problems in computation theory, including rank aggregation in search engines @DKN [@WH] and collaborative filtering @GNO. Rank aggregation can also occur when one wishes to select documents or other results based on multiple criteria @LKH. Some of these applications will be addressed in the next section. Unfortunately, it is now known that no voting system is perfect, and three major results show the weaknesses inherent in voting. Arrow's impossibility theorem @Arr shows that in any election with as few as three candidates, no voting system can convert the ranked preferences of a group of voters into a community-wide ranking meeting a reasonable set of criteria: unrestricted domain, meaning the aggregation is deterministic and complete for all possible profiles of the voters, nondictatorship, meaning that no single voter should be able to single-handedly determine the outcome, Pareto efficiency, meaning that if every voter prefers a candidate to another, this order must also hold in the aggregation, and independence of irrelevant alternatives, meaning that changes to the voters' rankings of irrelevant candidates should not change the outcome for the candidate in question. Beyond the problems of fairness, election systems are often subject to misuses, where the outcome of the election is unfairly affected by some of the voters, the chair of the election, or outside agents whom attempt to influence the voters. One form of misuse is when a voter reports preferences that are insincere to his or her true preferences for his or her own benefit, or when a group of voters conspire to collectively affect the outcome of the election. This is called manipulation, and is often disastrous for the system as a whole. In particular, a common problem in many election systems is the design that encourages voters to bury their $2^{nd}$ desired candidate, who may also be popular, among their preference list, giving their favorite candidate a more significant advantage. Done as a whole in the election, this distorts the true preferences of the participants. Two important results showing this weakness are the Gibbard-Satterthwaite theorem @Sat [@Gib] and Duggan-Schwartz theorem @DS, which show that eliminating the possibility of manipulation is impossible for any reasonable election system. The Gibbard-Satterthwaite theorem @Sat [@Gib] shows that every election of three or more candidates that chooses a single winner must either be dictatorial (i.e., where a single individual can choose the winner), nonsurjective (i.e., where some candidate cannot win under any circumstances), or is theoretically vulnerable to tactical voting in some cases. Tactical voting occurs when a voter or coalition of voters with full knowledge of the other voters' preferences has an incentive to vote contrary to their true preferences. Since neither of the first two properties are acceptable in any reasonable election system, this can be interpreted as all elections are subject to manipulation. The Duggan-Schwartz theorem @DS shows the same result with elections that elect a nonempty set of winners. We illustrate the problem of manipulation with the following example. In the election system Veto, the lowest candidate in each preference profile is given one veto, and the candidate with the fewest vetoes wins. Consider a system of three candidates, $x$, $y$, and $z$, and, initially, $100$ voters. $40$ initial voters have preferences expressed by $y \succ z \succ x$, $35$ have preferences $x \succ z \succ y$, and $25$ have preferences $y \succ x \succ z$. A total of $22$ manipulators have sincere preferences expressed by $x \succ y \succ z$. In an honest election, $x$ would receive $40$ vetoes, $y$ $35$ vetoes, and $z$ $47$ vetoes, making $y$ the winner. In this case, the $22$ manipulators can collectively make $x$ the winner if $6$ of the manipulators submit the preference $x \succ z \succ y$. Because $x$ would not be the winner of an honest Veto election, such manipulations may produce a sub-optimal outcome. In this example, the manipulators need to know the preference orderings of the honest voters, which may or may not be true depending on the problem of interest. Unfortunately, all reasonable election systems have cases in which such voting behavior is encouraged. In a related problem, an outside agent can also convince, or bribe, some of the agents to change their votes @FHH06. In the computational problem of bribery, the goal of the briber is to modify the outcome of the election with the least amount of effort. There are many interesting problem models. Most notably, voters may be unpriced or priced. In the unpriced case, we are attempting to find a bribery which changes the preferences of the fewest number of voters, and in the priced case, each voter is given a price tag. In this case, we want to find the cheapest bribery. In other cases, the cost of bribing a voter may depend on how significantly his or her preferences are to be changed @FHH06 (see also @FHHR07). In the above example, we have a total of $122$ unweighted voters, $40$ of which choose $x$ as their least favorite candidate, $35$ choose $y$, and $47$ choose $z$, making $y$ a unique winner. We may make $x$ a winner by convincing three voters whom dislike $x$ to submit preference profile $z \succ x \succ y$ instead. This gives $x$ a total of $37$ vetoes, $y$ $38$ vetoes, and $z$ $47$ vetoes. This is an optimum solution if each voter is equally costly to bribe, as it bribes the fewest voters. In other cases that we will evaluate, some voters are more costly to bribe than others. For example, in a campaign, it may be noted that a subgroup of voters will take more effort for one to convince. In the example above, depending on the price to bribe each voter, it may be the case that it is less costly to bribe five (six if a unique winner is desired) voters whom dislike $z$, to veto $y$ instead. This gives $x$ a total of $40$ vetoes, $y$ $40$ vetoes, and $z$ $42$ vetoes. It is further possible for the chair of an election to control the outcome of an election by manipulating the set of voters or candidates that will be involved @BTT92. One such way to control is by encouraging or discouraging potential voters from participating. One prominent example in politics occurred in 1971 when President Nixon signed the $26^{th}$ amendment into the Constitution of the United States, lowering the legal voting age from 21 to 18, and thus adding a set of voters to the election. The chair can also partition the set of voters to modify the outcome of the election, similar to what is seen with electoral colleges in the United States. As often observed in the presidential elections, the winner of the popular (i.e., plurality) vote need not be the winner of the electoral vote. A related problem, in which some candidates are cloned (i.e., a new candidate with similar properties is introduced to split the voters of this candidate), has also been evaluated @EFS for several systems, including $k$-Approval. It is also possible to partition the set of candidates, as is done with the candidates of the Republican and Democratic parties, as well as to add or remove candidates. In practice, an agent wishing to accomplish its goals will likely resort to a combination of more than one of the above strategies. Such problems are known computationally as multimode attacks @FHH [@FHH11], and will not be covered in this paper. Bartholdi, Tovey, and Trick @BTT89 challenged the impossibility of avoiding election misuse by making the observation that manipulation only constitutes a threat when it is computationally feasible to determine how one may manipulate the election for a given instance in the system of interest. They considered an election to be computationally resistant to manipulation if determining such an exploit is NP-hard, and computationally vulnerable if it is polynomial-time computable, and proved a number of P and NP-hard results for manipulating some election systems with one strategic voter. Since then, many results have characterized this complexity result. For example, Conitzer, Lang, and Sandholm @CLSjour evaluate the model of manipulation by a coalition of voters. In this model, which we also use in this chapter, the coalition of voters are working together to affect the outcome of the election. The line of reasoning of Conitzer, Lang, and Sandholm, of making coalitional manipulation at least NP-hard, was applied to bribery in @FHH06. Hemaspaandra and Hemaspaandra @HH07 characterize these hardness results for the case of scoring protocols, by showing exactly which scoring protocols are computationally resistant or vulnerable to manipulation. There also exist other models of interest for the problem of election manipulation, which we will not review in this chapter. In some models, each manipulator is not aware of the existence or actions of other potential manipulators. Models of manipulation under limited communications in these cases include that of safe manipulation @SW08 (see also @IYEW). In this case, the manipulator wishes to vote in a way such that the election never produces an undesirable outcome. Other possible models involve probabilistic measures of susceptibility to manipulation @RPW. We examine an infinite set of election systems, approval-based families of scoring protocols, where each candidate approves of some function $0 \leq f(m) \leq m$ of the $m$ candidates in the election, evaluating the worst-case complexities of various forms of attack. Essentially, we make the first attempt at extending the work of @HH07 [@BTT92] to scoring protocols of an unbounded number of candidates, by looking at an infinite set of election systems. A characterization of an infinite set of election systems is also evaluated in @FHS08. We find that there are generally only a few cases for the complexity of manipulation in such election systems: Nearly all problems of misuses of election systems involving controlling the voter set are hard by reductions from Set-Cover-type problems, while some problems involving controlling the candidate set are hard by a reduction from Hitting Set. Other cases are easy by greedy algorithms or variations of the Edge Cover problem. We hope that from our work one can gain a better understanding of what properties of elections make them computationally resistant or vulnerable to manipulation, so that our work can be extended to more general forms of elections. Table of Results ================ We summarize the worst-case complexity results of this chapter in the tables below, with new results in bold.[^2] ### Unweighted Cases <span> l || c | c | c | c | </span> & 1-app & 2-app & 3-app & $k$-app, $k \geq 4$\ Constructive Manipulation & P & P & P & P\ Constructive Bribery & P & **P** & **NPC** & **NPC**\ Constructive Control by Adding Voters & P & **P** & **P** & **NPC**\ Constructive Control by Deleting Voters & P & **P** & **NPC** & **NPC**\ Constructive Control by Adding Candidates & NPC & **NPC** & **NPC** & **NPC**\ Constructive Control by Deleting Candidates & NPC & **NPC** & **NPC** & **NPC**\ <span> l || c | c | c | c | </span> & 1-veto & 2-veto & 3-veto & $k$-veto, $k \geq 4$\ Constructive Manipulation & P & P & P & P\ Constructive Bribery & P & **P** & **P** & **NPC**\ Constructive Control by Adding Voters & P & **P** & **NPC** & **NPC**\ Constructive Control by Deleting Voters & P & **P** & **P** & **NPC**\ Constructive Control by Adding Candidates & NPC & **NPC** & **NPC** & **NPC**\ Constructive Control by Deleting Candidates & NPC & **NPC** & **NPC** & **NPC**\ ### Weighted Voter Cases <span> l || c | c | c | c |</span> & 1-app & 2-app & 3-app & $k$-app, $k \geq 4$\ Constructive Manipulation & P & NPC & NPC & NPC\ Constructive Bribery & P & NPC & NPC & NPC\ Constructive Control by Adding Voters & P & ? & ? & **NPC**\ Constructive Control by Deleting Voters & P & **sbw** & **NPC** & **NPC**\ Constructive Control by Adding Candidates & NPC & **NPC** & **NPC** & **NPC**\ Constructive Control by Deleting Candidates & NPC & **NPC** & **NPC** & **NPC**\ <span> l || c | c | c | c |</span> & 1-veto & 2-veto & 3-veto & $k$-veto, $k \geq 4$\ Constructive Manipulation & NPC & NPC & NPC & NPC\ Constructive Bribery & NPC & NPC & NPC & NPC\ Constructive Control by Adding Voters & P & **sbw** & **NPC** & **NPC**\ Constructive Control by Deleting Voters & P & ? & ? & **NPC**\ Constructive Control by Adding Candidates & NPC & **NPC** & **NPC** & **NPC**\ Constructive Control by Deleting Candidates & NPC & **NPC** & **NPC** & **NPC**\ ### Unweighted \$Bribery Cases <span> c || c | c | c | c | c | c | c | c | </span> & 1-app & 2-app & 3-app & $k$-app, $k \geq 4$\ Constructive \$Bribery & P & ? & **NPC** & **NPC**\ <span> c || c | c | c | c | c | c | c | c | </span> & 1-veto & 2-veto & 3-veto & $k$-veto, $k \geq 4$\ Constructive \$Bribery & P & $\geq_{p}$ **swb** & ? & **NPC**\ In this chapter, we define what an election system is, and formally define the problems that may occur in the system: manipulation, control, and bribery. We then define other computational problems, such as Edge Cover and Set Cover, which will be utilized in evaluating the complexity of these election problems. Finally, we will review previous complexity results of these related computational problems. Definition of Elections {#sect:defelect} ======================= An election $E = (C,V)$ is defined as a pair of a set of voters $V = \{v_1,\ldots,v_n\}$ and a set of candidates $C = \{c_1,\ldots,c_m\}$. Each voter $v_i$ has a preference over the candidates. A common model for understanding voter preferences is that of the transitive voter model. In the transitive voter model, which we will use exclusively in this chapter, each preference is a strict linear ordering over the candidates $c_{i_1} \succ \cdots \succ c_{i_m}$. But voter preferences need not be transitive (see, e.g., @FHHR07, in which the voter submits a reflexive and antisymmetric binary ordering over the candidates $C$). Furthermore, voters in some election systems cannot submit their vote simply as a preference ordering. A prominent example is approval, which we will define below. Elections may be weighted or unweighted. In a weighted election, each voter $v_i$ has a weight, $w(v_i)$, and their vote is counted as $w(v_i)$ individual votes in an unweighted election with the same preference ordering. Election Systems of Interest ---------------------------- \[sect:electsys\] An election system $\mathcal{E}$ specifies how one arrives at the outcome given the collection of voter preferences. Depending on the context, the outcome we may be interested in may be a winner, a nonempty subset of winners, or an aggregate preference ordering. Most typically, an election for us will be what in the literature is called a social choice correspondence, namely, a mapping from the candidates and the voter preferences to a subset (known as the winner set) of the set of candidates. There are many systems of interest, some of which involve multiple rounds. Perhaps the most common election system in everyday use is that of plurality, in which the candidate(s) most frequently ranked first among the voters is elected. Plurality is an election system in a more general family of election systems called scoring protocols. A *scoring protocol* (see the handbook article @BF02) is defined over a vector $(\alpha_1,\ldots,\alpha_m) \in {\textrm{Z}}^m$. Each candidate $c$ is given $\alpha_i$ points for each voter that ranks $c$ in the $i^{th}$ position of his or her ranking. The candidate(s) with the highest score wins. In addition to plurality, common scoring protocols include veto, Borda count, and approval-based systems with a fixed number of candidates. A *family of scoring protocols* is an infinite series of scoring protocols $(\alpha^1,\ldots,\alpha^m,\ldots)$, where $\alpha^m=(\alpha^m_1,\ldots,\alpha^m_m)$ is a scoring protocol of $m$ candidates. In *plurality*, a common form of elections in political science, each voter gives one point to his or her favorite candidate, whereas in *veto*, each voter approves, or gives one point, to all but one candidate: This has the effect of vetoing one candidate. Plurality and veto can thus be considered a family of scoring protocols of the form $\alpha^m = (1,0,\ldots,0)$ and $\alpha^m = (1,\ldots,1,0)$ respectively. In *$k$-approval*, each voter gives his or her $k$ favorite candidates $1$ point. Similarly, in *$k$-veto*, each voter vetoes his or her least $k$ favorite candidates. Although not a scoring protocol, another common election system is *approval* @BFapp. In approval voting, each voter can approve as many or as few candidates as he/she chooses. In some models, voters may still have a preference order, along with the number of candidates approved. The winner(s) is thus the candidate(s) with the most number of approvals (or weights thereof). In @FHH06 [@HHR07], it is shown that approval is computationally resistant to many forms of misuse involving the voter set, even with unweighted voters, for constructive and destructive cases. We will in fact examine the properties of this election system that give rise to the resistance. A generalization of $k$-approval and $k$-veto, *$f(m)$-approval*, where $f$ is a function of the number of candidates $m$, is an election where each voter gives $1$ point to each of his or her $f(m)$ favorite candidates. In this case, we will assume that $f(m)$ may be computed in time polynomial with respect to the quantity $m$. This ensures we may compute the outcome of an instance of this election in polynomial time. Another interesting scoring protocol is the *Borda count* @Borda. For $m$ candidates, this election is the scoring protocol defined by the vector $(m-1,m-2,\ldots,1,0)$. In this case, the first preference of each voter is given $m-1$ points, the second $m-2$ points, and so forth. Problems of Interest in Elections ================================= A common problem in all election systems of interest is the incentive for dishonesty. In all election systems of interest, there exist instances in which it is advantageous for some of the voters to vote dishonestly, affecting the outcome of the election to their advantage @Gib [@Sat; @DS]. Because manipulation is to be carried out by agents with supposedly limited computational power, Bartholdi, Tovey, and Trick @BTT89 make the observation that manipulation is only a threat to the integrity of the election when the determination of the manipulation is tractable. It is thus of interest to evaluate the complexity, worst-case or otherwise, of computing how these agents may capitalize on these weaknesses. Two other interesting problems include bribery and control: Elections may be bribed @FHH06, in which an outside agent influences the election by affecting the voters, or controlled @BTT92, in which the chair of the election affects the election by modifying the set of participating voters and candidates. Each of these problems come in two flavors: constructive, in which our goal is to ensure that a specified distinguished candidate is a winner, and destructive, where our goal is to ensure that such is not a winner. In manipulation, we attempt to reach this goal by giving preferences to a set of unestablished voters, whereas in bribery we do so by changing a given number of votes. There are two subclasses of control problems, those that alter the voter set (i.e., add or delete voters from the election) and those that alter the candidate set. We define these problems as follows. Name: : *$\mathcal{E}$-Manipulation* @BTT89 [@BO91; @CLSjour] Instance: : A set $C$ of candidates, a set $V$ of established voters, and $V'$ of unestablished voters such that $V \cap V' = \emptyset$, and distinguished candidate $p$. Question (constructive manipulation): : Does there exist an assignment of preferences for $V'$ such that $p$ is a winner of the $\mathcal{E}$ election with candidate set $C$ and voter set $V \cup V'$? Question (destructive manipulation): : Does there exist an assignment of preferences for $V'$ such that $p$ is not a winner of the $\mathcal{E}$ election with candidate set $C$ and voter set $V \cup V'$? Another problem of interest is the cases where voters have weights. In such case, we denote the problem by $\mathcal{E}$-weighted-constructive-manipulation and $\mathcal{E}$-weighted-destructive-manipulation. Name: : *$\mathcal{E}$-Bribery* @FHH06 Instance: : A set $C$ of candidates, a set $V$ of voters, distinguished candidate $p$, and nonnegative integer quota $q$. Question (constructive bribery): : Is it possible to make $p$ a winner of the $\mathcal{E}$ election by changing the preference profiles of at most $q$ voters in $V$. Question (destructive bribery): : Is it possible to make $p$ not a winner of the $\mathcal{E}$ election by changing the preference profiles of at most $q$ voters in $V$. As in the cases of manipulation, bribery is also defined for cases of weighted voters. As above, we denote this problem $\mathcal{E}$-weighted-bribery. In addition, each voter $v$ can be assigned a price tag $\pi(v)$ of a nonnegative integer. In this case, $q$ is our budget, and we want to achieve our goal (constructive or destructive bribery) by spending at most $q$ in our bribery. We denote this problem by $\mathcal{E}$-\$bribery and $\mathcal{E}$-weighted-\$bribery if voters have both weights and prices. There are six problems of interest in the case of control, as we may add, delete, or partition, either voters or candidates. Also in all of these cases, voters may be weighted. The cases of constructive control, except the versions used here of adding candidates, are from @BTT92, while those of destructive control, as well as the versions of constructive control by adding candidates used here, are from @HHR07. Name: : *$\mathcal{E}$-Control by Adding Voters* Instance: : A set $C$ of candidates, a set $V$ of established voters, and $V'$ of unestablished voters such that $V \cap V' = \emptyset$, distinguished candidate $p$, and nonnegative integer quota $q$. Question (constructive control): : Does there exist a subset $V'' \subseteq V'$ with $||V''|| \leq q$ such that $p$ is a winner of the $\mathcal{E}$ election with candidate set $C$ and voter set $V \cup V''$? Question (destructive control): : Does there exist a subset $V'' \subseteq V'$ with $||V''|| \leq q$ such that $p$ is not a winner of the $\mathcal{E}$ election with candidate set $C$ and voter set $V \cup V''$? <!-- --> Name: : *$\mathcal{E}$-Control by Deleting Voters* Instance: : A set $C$ of candidates, a set $V$ of established voters, distinguished candidate $p$, and nonnegative integer quota $q$. Question (constructive control): : Does there exist a subset $V' \subseteq V$ with $||V'|| \leq q$ such that $p$ is a winner of the $\mathcal{E}$ election with candidate set $C$ and voter set $V - V'$? Question (destructive control): : Does there exist a subset $V' \subseteq V$ with $||V'|| \leq q$ such that $p$ is not a winner of the $\mathcal{E}$ election with candidate set $C$ and voter set $V - V'$? <!-- --> Name: : *$\mathcal{E}$-Control by Partitioning Voters* Instance: : A set $C$ of candidates, a set $V$ of established voters, and distinguished candidate $p$. Question (constructive control): : Does there exist a partition of candidates $V = V_1 \cup V_2$ such that $p$ is a winner of the election with the candidates given by the union of the winners of $E_1 = (C,V_1)$ and $E_2 = (C,V_2)$? Question (destructive control): : Does there exist a partition of candidates $V = V_1 \cup V_2$ such that $p$ is not a winner of the election with the candidates given by the union of the winners of $E_1 = (C,V_1)$ and $E_2 = (C,V_2)$? <!-- --> Name: : *$\mathcal{E}$-Control by Adding Candidates* Instance: : A set $C$ of candidates, a set $V$ of established voters, and $C'$ of unestablished voters such that $C \cap C' = \emptyset$, distinguished candidate $p$, and nonnegative integer quota $q$. Question (constructive control): : Does there exist a subset $C'' \subseteq C'$ with $||C''|| \leq q$ such that $p$ is a winner of the $\mathcal{E}$ election with candidate set $C \cup C''$ and voter set $V$? Question (destructive control): : Does there exist a subset $C'' \subseteq C'$ with $||C''|| \leq q$ such that $p$ is not a winner of the $\mathcal{E}$ election with candidate set $C \cup C''$ and voter set $V$? <!-- --> Name: : *$\mathcal{E}$-Control by Deleting Candidates* Instance: : A set $C$ of candidates, a set $V$ of established voters, distinguished candidate $p$, and nonnegative integer quota $q$. Question (constructive control): : Does there exist a subset $C' \subseteq C$ with $||C'|| \leq q$ such that $p$ is a winner of the $\mathcal{E}$ election with candidate set $C - C'$ and voter set $V$? Question (destructive control): : Does there exist a subset $C' \subseteq C \backslash \{p\}$ with $||C'|| \leq q$ such that $p$ is not a winner of the $\mathcal{E}$ election with candidate set $C - C'$ and voter set $V$? In this case, note that we may not deleted the candidate $p$ in which we are manipulating against. <!-- --> Name: : *$\mathcal{E}$-Control by Partitioning Candidates* Instance: : A set $C$ of candidates, a set $V$ of established voters, and distinguished candidate $p$. Question (constructive control): : Does there exist a partition of candidates $C = C_1 \cup C_2$ such that $p$ is a winner of the election with the candidates given by the union of the winners of $E_1 = (C_1,V)$ and $E_2 = (C_2,V)$? Question (destructive control): : Does there exist a partition of candidates $C = C_1 \cup C_2$ such that $p$ is not a winner of the election with the candidates given by the union of the winners of $E_1 = (C_1,V)$ and $E_2 = (C_2,V)$? In all of these cases, we say that an election is *computationally vulnerable* to a particular form of misuse, such as manipulation, bribery, or control if the corresponding problem is polynomial-time computable. The election is *computationally resistant* to the misuse if the corresponding problem is NP-hard. Some Important NP-Complete Problems ----------------------------------- Common NP-complete problems of choice for showing NP-hardness of election systems include versions of Set Cover, Knapsack, and Hitting Set. Exact 3-Set Cover (X3C) is a common restricted version of Set Cover. Name: : *Exact Cover by 3-Sets (X3C)* @Karp (See also @GJ79 [problem SP2]) Instance: : A set $S = \{s_1,\ldots,s_{3m}\}$ and subsets $T_1,\ldots,T_n \subseteq S$ such that $||T_i||=3$. Question: : Does there exist a set $A \subseteq \{1,\ldots,n\}$ such that $||A||=m$ and $\bigcup_{i \in A}{T_i} = S$? Other variations of restricted set cover type problems also exist, such as Exact $\frac{3}{4}$-Set Cover @FHS08, which was used to show the NP-completeness of bribery in the Borda count election @BFHSS. An important problem used in showing complexities of problems involving control by adding or deleting candidates is Hitting Set. Name: : *Hitting Set* @Karp (See also @GJ79 [problem SP8]) Instance: : A set $S = \{s_1,\ldots,s_m\}$, $n$ subsets of $S$, $T_1,\ldots,T_n$, and positive integer $1 \leq q \leq m$. Question: : Does there exist a subset of $q$ elements of $S$, $S'=\{s_{i_1}, \ldots, s_{i_q}\}$, such that $S' \cap T_i \neq \emptyset$ for each $1 \leq i \leq n$? Thus, each subset $T_i$ contains at least one element of $S'$. Hitting Set can also be viewed as a generalization of Vertex Cover to hypergraphs, where edges connect an arbitrary number of vertices. This problem was used to prove that unweighted plurality elections are computationally resistant to control by adding and deleting candidates in @BTT92. We will generalize this result. Edge Covering and Edge Matching Problems ======================================== We will show in this paper that some problems in some election systems are closely related to problems involving edge coverings. This is especially true for elections that distinguish two candidates from the remaining candidates. Due to this connection, these problems generally have similar complexities to that of some forms of edge covering problems. An edge cover, as well as the well-known decision problem of Edge Cover, is defined as follows. An *edge cover* of a graph is a set of edges such that every vertex of the graph is incident to at least one edge of the set. Name: : *Edge Cover* @Karp (See also @GJ79 [pages 79, 190]) Instance: : An undirected graph $G=(V,E)$ and positive integer $q$. Question: : Does there exist an edge cover $C \subseteq E$ for $G$ of size at most $q$? It is possible to find a smallest edge cover in polynomial time, by finding a maximum matching and extending it greedily so that all vertices are covered. We will use several interesting variations of Edge Cover in this paper, which are defined as follows. In the variation $b$-Edge Cover, each vertex $v$ is to be covered by a minimum of some number, $b(v)$, of edges. There are several interesting variations of this problem: Each edge can be chosen only once (Simple $b$-Edge Cover), an arbitrary number of times ($b$-Edge Cover), or have a capacity and be chosen up to that many times (Capacitated $b$-Edge Cover) (see @Sch sections 34.1, 34.7, and 34.8), all of which are polynomial-time computable @Pul73 [@CM78; @Gab83; @Ans87]. In each case, polynomial-time computability is due to the relationship between edge coverings and edge matchings. More specifically, the size of the minimum edge covering and the size of the maximum edge matching always sum to the total of the $b$-values. The maximum edge matching can then be computed using linear programming. We further extend this problem to that of multigraphs, defining Simple $b$-Edge Cover of Multigraphs as follows. Name: : *Simple $b$-Edge Cover of Multigraphs* Instance: : An undirected multigraph $G=(V,E)$, a function $b:V \rightarrow {\textbf{\textrm{Z}}^{+}}$ and positive integer $q$. Question: : Does there exist a subset of at most $q$ edges $C \subseteq E$ such that each vertex $v \in V$ is incident to at least $b(v)$ edges in $C$? This variation is also polynomial-time computable, as follows. Simple $b$-Edge Cover for Multigraphs is polynomial-time computable. We demonstrate how to compute Simple $b$-Edge Cover of Multigraphs using Capacitated $b$-Edge Cover, which we define as follows. Name: : *Capacitated $b$-Edge Cover* (See also @Sch [chapter 34]) Instance: : An undirected graph $G=(V,E)$, a function $b:V \rightarrow {\textbf{\textrm{Z}}^{+}}$, a capacity function $c:E \rightarrow {\textbf{\textrm{Z}}}^{+}$, and positive integer $q$. Question: : Does there exist a multisubset of edges $C \subseteq E$ such that each vertex $v \in V$ is incident to at least $b(v)$ edges in $C$ and such that each $e \in E$ is chosen by $C$ with frequency at most $c(e)$? Let $G=(V,E)$, $b:V \rightarrow {\textbf{\textrm{Z}}}^{+}$, and $q>0$ be an instance of Simple $b$-Edge Cover of Multigraphs. We construct an instance of Capacitated $b$-Edge Cover as follows. Let $G'$ be a complete graph of $V$. For each pair $v_1, v_2 \in V$, we set the capacity $c(v_1,v_2)$ to the number of edges between $v_1$ and $v_2$ in $G$. Simple $b$-Edge Cover of Multigraphs, and several variations thereof, is of interest in solving some election manipulation problems in which the voters always distinguish exactly two candidates from the remaining candidates. More specifically, in such a construction, the vertices correspond to candidates and the edges to the voters, who distinguish two candidates from the remaining. We introduce two additional versions of Simple $b$-Edge Cover of Multigraphs, which will be of interest to problems involving weights and prices for voters. Name: : *Simple Weighted $b$-Edge Cover of Multigraphs* Instance: : An undirected multigraph $G=(V,E)$, a function $b:V \rightarrow {\textbf{\textrm{Z}}^{+}}$, weight function $w:E \rightarrow {\textbf{\textrm{Z}}^{+}}$ and positive integer $q$. Question: : Does there exist a subset of edges $C \subseteq E$ of total weight at most $q$ such that each vertex $v \in V$ is incident to at least $b(v)$ edges in $C$? <!-- --> Name: : *Simple $b$-Edge Weighted Cover of Multigraphs* Instance: : An undirected multigraph $G=(V,E)$, a function $b:V \rightarrow {\textbf{\textrm{Z}}^{+}}$, weight function $w:E \rightarrow {\textbf{\textrm{Z}}^{+}}$ and positive integer $q$. Question: : Does there exist a subset of at most $q$ edges $C \subseteq E$ such that each vertex $v \in V$ is incident to edges in $C$ of at least total weight $b(v)$? In these two versions, as we will see later, the weighted edges correspond to cases of bribery in which each voter has an associated price. The weighted coverings correspond to manipulations involving weighted voters. It is currently unknown whether either of these variations are polynomial-time computable, NP-intermediate, or NP-complete. We will show in this paper that some problems of interest are polynomial-time equivalent to one of these problems. A related problem involves edge matchings. See @Sch for the connection between matchings and coverings, and the extension of Edge Matching to $b$-Edge Matching, and the polynomial-time computability result. We will define an analogous problem for multigraphs as follows. Name: : *Simple $b$-Edge Matching of Multigraphs* Instance: : An undirected multigraph $G=(V,E)$, a function $b:V \rightarrow {\textbf{\textrm{Z}}^{+}}$ and positive integer $q$. Question: : Does there exist a subset of at least $q$ edges $C \subseteq E$ such that each vertex $v \in V$ is incident to at most $b(v)$ edges in $C$? This is an extension of Edge Matching. In a traditional Edge Matching problem, each vertex has a $b$-value of $b(v)=1$, as a matching cannot cover a vertex more than once. Misuses in Elections with a Fixed Number of Candidates ====================================================== In @FHH06, it is shown that bribery of unweighted scoring protocol elections can be solved in polynomial time with brute force when the number of candidates is fixed, since the number of possible preference orderings is also fixed, and that voters with equal preferences are not distinguishable (see the definition of succinct preference representation in Section \[sect:succinct\]). The same principle also applies to control by adding or deleting voters, as well as manipulation. Bribery of fixed scoring protocols is also polynomial-time computable even when voters have prices, since it suffices to bribe only the cheapest voters among those with equal preferences. We review the result for \$bribery from @FHH06 below. @FHH06 $\alpha$-\$bribery is polynomial-time computable for all scoring protocols $\alpha = (\alpha_1,\ldots,\alpha_m)$ with a fixed number of candidates $m$. Because $m$ is a constant, there are only a constant, $m!$, number of distinct preference profiles. The algorithm given in @FHH06 partitions the set of voters into $m!$ subsets, $V = V_1 \cup \cdots \cup V_{m!}$, with voters in each subset having equal preferences. A bribery can then be described by two sequences of integers, $b_1,\ldots,b_{m!}$, and $d_1,\ldots,d_{m!}$, where each $b_i$ indicates how many voters from $V_i$ we are bribing and $d_i$ indicates how many voters will be given the preferences of $V_i$. Without loss of generality, we can assume we are bribing the cheapest $b_i$ voters of the set $V_i$. Since each bribery can be described with $2m!$ variables, and each variable is bounded $0 \leq b_i,d_i \leq ||V||$, this algorithm tries at most $(||V||+1)^{2m!}$ possible briberies. This quantity is polynomial with respect to the size of the problem instance. Thus, $\alpha$-\$bribery is polynomial-time computable. Also owing to the constant number of possible preference orderings, unweighted scoring protocols of a fixed number of candidates are also computationally vulnerable to manipulation as well as control by adding or deleting voters. All scoring protocols $\alpha = (\alpha_1,\ldots,\alpha_m)$ are computationally vulnerable to constructive control by either adding or deleting voters, as well as to manipulation for a fixed number of candidates $m$. It is important to note that despite the theoretical polynomial-time computability in this case, in practice, this problem is significantly difficult for moderate-sized $m$, due to the exponential nature of $m!$. It is often the case that the brute-force algorithm, despite being faster in the worst case, is not the best approach to this problem empirically. In @HH07 [@FHH06] it is shown that most nontrivial manipulation and bribery problems in weighted scoring protocol elections are NP-hard even for a fixed number of candidates. We will discuss these cases in Section \[sect:weightprice\]. It should be noted that control by adding or deleting candidates in elections of a constant number of candidates (participating and additional candidates) is easy, as there are a constant number of different sets of candidates to add or delete, and whether or not a distinguished candidate will win or lose the election can be checked in polynomial time. Destructive Misuses =================== To demonstrate the vast differences between the problems of constructive misuse and that of destructive misuse, we prove that unweighted approval-based elections are computationally vulnerable to most forms of destructive misuse. This is true even for families of scoring protocols, in which the size of the candidate set is unbounded. Consider the problem of bribery below. Unweighted $f(m)$-approval elections are computationally vulnerable to destructive bribery. As a reminder, we assume that $f(m)$ is computable in time polynomial with respect to $m$. In a destructive bribery, we want some candidate $p' \neq p$ to beat $p$. Thus, we want to have $p'$ gain as many points as possible relative to $p$. For each $p' \neq p$, we separate the voters into 3 categories: 1\. Those approving of $p$ but not of $p'$. 2\. Those approving either both of $p$ and $p'$ or neither of $p$ nor $p'$. 3\. Those approving of $p'$ but not of $p$. Clearly, briberies of votes of the first type take priority over those of the second type, as $p'$ can gain two points relative to $p$. Voters of the third type should not be michaelwilson@example.net. We check whether $p'$ can potentially beat $p$ by first bribing voters of type one, and then those of type two, up to a total of our quota $q$. We always bribe voters to approve of $p'$ but not $p$. We find such a bribery for each other candidate $p' \neq p$ by bribing $q$ voters using the procedure above. If there exists no candidate $p' \neq p$ that can be made to beat $p$, we reject. Intuitively, the reason such briberies are easy is that we only need to ensure that $p'$ beats $p$. It does not matter if other candidates will beat both $p'$ and $p$ as a result of the bribery, as $p$ will lose. This principle is also demonstrated in @Rus for the case of Borda elections and @FHH06 for the case of scoring protocols in general. Unweighted $f(m)$-approval elections are computationally vulnerable to destructive manipulation and destructive control adding or deleting voters. The concept of attempting to make each candidate $p' \neq p$ beat $p$ can be applied to manipulation, as well as control by adding and deleting voters. In manipulation, each manipulator approves of $p'$ but not of $p$. Similarly, in control by adding voters, we only add voters that approve of $p'$ but not of $p$. In control by deleting voters, we only delete voters that approve of $p$ but not of $p'$. We conclude that all unweighted approval-based scoring protocols, as well as families of scoring protocols, $f(m)$-approval, are computationally vulnerable to destructive bribery, manipulation, and control by adding or deleting voters. The case of destructive control by adding or deleting candidates will be considered in Section \[sect:contbycand\]. The remainder of this section will thus focus on constructive problems. Manipulation of Approval-Based Scoring Protocols ================================================ It is shown in @Z that manipulation in the $f(m)$-approval families of scoring protocols (recall that $f(m)$ is computable in polynomial time with respect to the quantity of $m$ in this case) is polynomial-time computable, by a greedy algorithm. The greedy algorithm operates by iteratively assigning the manipulators' preferences as follows: each manipulator approves $p$, the distinguished candidate and the current $f(m)-1$ candidates with the lowest scores. It can be shown that this algorithm is correct by induction on the number of manipulators. Such elections are thus computationally vulnerable to insincere voting from a coalition of agents for their collective benefit, whether their goal is to elect a preferred candidate (constructive manipulation) or to prevent the election of a despised candidate (destructive manipulation). Bribery in Approval-Based Scoring Protocols =========================================== In unweighted and unpriced families of scoring protocols, the goal of the bribery problem is to determine the minimum number of voters one needs to change the preferences for (i.e., bribe) to achieve a desirable outcome. As we have seen earlier, if our goal is to exclude a candidate from winning, as in destructive bribery, this problem is easy and can be computed in polynomial time for all approval-based elections. We thus now focus on constructive bribery cases, where we aim to elect a distinguished candidate. \[@FHH06\] Unweighted $1$-approval elections are computationally vulnerable to bribery by unpriced voters. In this case, one simply bribes the voters that vote for the current winner to vote for our distinguished candidate, $p$, until either $p$ wins, in which case we accept, or until we run out of voters to bribe, in which case we reject. \[@FHH06\] Unweighted $1$-veto elections are computationally vulnerable to bribery by unpriced voters. In this case, we simply bribe voters whom veto $p$ to veto for the current winner instead. We now demonstrate how the seemingly unrelated problem of Set Cover relates to bribery of election systems, and prove the resistance to bribery of some approval-based election systems. In @HHR07 a reduction is given from X3C to control in approval elections by adding or deleting voters. The reduction operates by encoding the elements as candidates and voters as subsets of elements, by approving these elements. A number of buffer candidates and voters are added to enforce the constraints of the problem of X3C. We demonstrate how to modify this result to the cases of $k$-approval and $k$-veto, where either the number of candidates approved or vetoed is fixed, for appropriately valued $k$. The reduction requires the usage of additional buffer candidates and voters, as in the reduction given in @HHR07, each voter approves a different number of candidates. Unweighted $k$-approval elections are computationally resistant to bribery by unpriced voters for $k \geq 3$. We first show resistance for the case of $3$-approval elections. Cases for $k > 3$ can be shown by a simple change. We make our reduction from Exact $3$-Set Cover (X3C). Let $$S = \{s_1,\ldots,s_{3m}\}$$ and $$T_1 = \{t_{1,1},t_{1,2},t_{1,3}\},\ldots,T_n = \{t_{n,1},t_{n,2},t_{n,3}\}$$ be an instance of X3C. Without loss of generality, we assume $n \geq m$. We construct our $k$-approval election as follows. Our candidate set will be $$C = \{p, p', p''\} \cup \{s_1, \ldots, s_{3m}\} \cup \{b_1, \ldots, b_{\frac{3(nm+m-n)}{2}}\}.$$ For each $3$-set $T_i = \{t_{i,1},t_{i,2},t_{i,3}\}$ we construct a voter who approves of $\{t_{i,1},t_{i,2},t_{i,3}\}$. For $1 \leq i \leq \frac{3(nm+m-n)}{2}$ we add voters that approve of $b_i$ and two members of $s_1,\ldots,s_{3m}$. We choose these votes in a way such that each $s$ candidate receives exactly $n+1$ approvals in total. Finally, we add $n-m$ votes that approve of $\{p, p', p''\}$. We set our bribery quota $q$ to $m$. In this election, we note that each of $p, p', p''$ receives $n-m$ approvals. Each of $s_1$, $\ldots$, $s_{3m}$ receives $n+1$ approvals, and each candidate $b_i$ for $1 \leq i \leq \frac{3(nm+m-n)}{2}$ receives one approval. If there is an exact covering by $3$-sets, we note that bribing the agents corresponding to the $3$-sets to approve of $\{p, p', p''\}$ instead will allow $p$ to win. On the other hand, a valid bribery must remove one approval of each of $s_1$, $\ldots$, $s_{3m}$, since the most number of approvals that can be given to $p$ is $m$. Note that bribing any of the votes corresponding to $T_i$ removes three approvals, collectively, from $s_1, \ldots, s_{3m}$. In contrast, all other bribes will remove at most two approvals, collectively, from $s_1, \ldots, s_{3m}$. Thus, a successful bribery of $\leq m$ votes can only involve votes corresponding to $T_i$, and each candidate of $s_1, \ldots, s_{3m}$ must lose one approval. This corresponds to an exact covering. A simple extension to show that $k$-approval elections for $k > 3$ are also computationally resistant to bribery can be constructed by adding additional buffer candidates, such that each voter approves of distinct buffer candidates in addition to the three edges elements in the subset. Each buffer candidate would thus receive only one approval, and cannot influence the election. A similar reduction, in the next theorem shows this hardness result for $k$-veto elections. Unweighted $k$-veto elections are computationally resistant to bribery by unpriced voters for $k \geq 4$. Again, we start with $4$-veto elections and demonstrate how our reduction can be extended. Let $$S = \{s_1,\ldots,s_{3m}\}$$ and $$T_1 = \{t_{1,1},t_{1,2},t_{1,3}\},\ldots,T_n = \{t_{n,1},t_{n,2},t_{n,3}\}$$ be an instance of X3C. In this reduction, we will restrict the X3C instance to cases in which $n \geq 2m$, for reasons which will be clear later. We construct a $4$-veto election of $3m+5$ candidates, $$C = \{p\} \cup \{b_1, b_2, b_3, b_4\} \cup \{s_1,\ldots,s_{3m}\}.$$ For each set $T_i = \{t_{i,1},t_{i,2},t_{i,3}\}$, we have one voter who veto $\{p, t_{i,1}, t_{i,2}, t_{i,3}\}$. We add $\frac{mn-m^2+m-3n}{4}$ voters whom veto four candidates of $\{s_1,\ldots,s_{3m}\}$ such that each $s_i$ receives exactly $n-m+1$ vetoes. Initially, $n-2m$ voters veto the four buffer candidates, $\{b_1,b_2,b_3,b_4\}$. Under this construction, $p$ initially has $n$ vetoes, each $s_i$ has $n-m+1$ vetoes, and each buffer candidate has $n-2m$ vetoes. We set our quota for bribing voters to $m$. Consider an exact covering of $S$. Bribing the votes corresponding to the sets to vote for the $4$ buffer candidates instead will leave $p$ with $n-m$ vetoes, each $s_i$ with $n-m$ vetos, and each buffer candidate with $n-m$ vetoes. $p$ is clearly made a winner. Conversely, consider any bribery of at most $m$ voters such that $p$ is made a winner. In any bribery of at most $m$ voters, $p$ must retain at least $n-m$ vetoes. If $p$ is made a winner, each $s_i$ must retain at least $n-m$ vetoes, and can lose at most one veto. Since there are only $3m$ such candidates and only votes corresponding to the 3-sets veto 3 such candidates, these are the only votes we can bribe in such a bribery. Thus, this corresponds to an exact covering. This reduction can also be extended to $k$-veto elections for all $k>4$, by
{'source': 'arXiv_out/1005'}