
## 14 Results And Discussion

These results show the variance of complexity of misuse among different problems in election systems of the form k-approval, k-veto, and f(m**)-approval, and give a result of complexity for infinitely many scoring**
protocols of an unbounded number of candidates. There are a few **interesting cases: These manipulations**
can either be easy by a simple greedy algorithm, equivalent to a corresponding variation of b**-Edge Cover,**
which is easy for the unweighted and unpriced cases but unknown for the weighted or priced variations, or hard by reduction from Set Cover. Manipulations involving the candidate sets are always difficult as a result of reductions from Hitting Set. These results show a connection between election manipulation and seemingly unrelated graph theory problems.

Our results demonstrate the strengths and weaknesses of approval-based election systems, and we hope they can lead to further generalizations and possible developments **of systems that better resist such attacks.** There are, however, three open problems: that of control by adding voters in 3-approval elections, control by deleting voters in 3-veto elections, and $bribery of 3-veto elections. These cases cannot be evaluated using the Edge Cover variants, because, for instance, to bribe voters in 3-veto elections, we must choose between those that distinguish three of the candidates other than p**. This cannot be accomplished with** Simple Weighted b**-Edge Cover of Multigraphs. The problem of X3C also does not appear to reduce to this** or the other cases. We leave these as open problems. The complexity of Simple Weighted b**-Edge Cover of** Multigraphs and Simple b**-Edge Weighted Cover of Multigraphs is also left as an open problem. We believe it** both problems are likely to be polynomial-time computable, due to the results for other variations of b**-Edge**
Cover and the connections between this problem and linear programming.

It is important to realize that NP-completeness only addresses the **worst-case complexity of a given**
problem, and does not take into consideration the distribution of problems that might be given. Some simple distributions were considered in [46, 45], and it may be of interest to characterize the complexity of more interesting and realistic distributions, depending upon the application.

This model also makes the assumption that in a k-approval election, each voter may vote for any combination of the k candidates independently. We know that in practice, most elections **do not follow this**
principle, and voters in most realistic elections have highly correlated **preferences (e.g., nearly single-peaked** preferences (see [43])). In [44], several otherwise hard problems **in election manipulation are shown to be** easy when restricted to the case of single-peaked preferences. **It is shown that constructive or destructive**
control by adding or deleting candidates is easy for plurality elections, as well as weighted manipulation in some scoring protocols other than plurality, become easy when the voters (including the manipulators) are restricted to having single-peaked preferences. It may thus **be of interest to characterize the complexity**
properties of manipulation in a more realistic distribution of voter preferences.

## 15 Acknowledgements

We wish to offer our special thanks to Dr. E. Hemaspaandra and anonymous referees for their helpful comments. We especially thank Dr. E. Hemaspaandra for pointing out the link to b**-Edge Cover.**