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 [?]. For m **candidates, this election is the scoring**
protocol defined by the vector (m − 1, m − 2, . . ., 1, **0). In this case, the first preference of each voter is given**
m − 1 points, the second m − **2 points, and so forth.**

## 5 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 [7, 6, 22]. Because manipulation is to be carried out by agents with supposedly limited computational power, Bartholdi, Tovey, and **Trick [12] 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 [21], in which an outside agent influences the election by affecting the voters, or controlled [16], 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: E-Manipulation **[12, 82, 97]**
Instance: A set C of candidates, a set V **of established voters, and** V
′ **of unestablished voters such that**
V ∩ V
′ = ∅**, and distinguished candidate** p.

Question (constructive manipulation): **Does there exist an assignment of preferences for** V
′**such that**
p is a winner of the E election with candidate set C **and voter set** V ∪ V
′?

Question (destructive manipulation): **Does there exist an assignment of preferences for** V
′**such that** p is not a winner of the E election with candidate set C **and voter set** V ∪ V
′?

Another problem of interest is the cases where voters have weights. In such case, we denote the problem by E-weighted-constructive-manipulation and E**-weighted-destructive-manipulation.**