hard, was applied to bribery in [21]. Hemaspaandra and Hemaspaandra [11] 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 [102] (see also [99]). 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 [103].

We examine an infinite set of election systems, approval-based families of scoring protocols, where each candidate approves of some function 0 ≤ f(m) ≤ 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 [11, 16] 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 [19].

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.

## 2 Table Of Results

We summarize the worst-case complexity results of this chapter in the tables below, with new results in bold.1

## 2.0.1 Unweighted Cases

| 1-app                                       | 2-app   | 3-app   | k-app, k ≥ 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 |

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

1

In the table, swb is the complexity of Simple Weighted b-Edge Cover of Multigraphs and sbw that of Simple b-Edge Weighted

Cover of Multigraphs.
