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 [21]. 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 [21] (see also **[84]).**
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 ≻ x ≻ 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 [16]. 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 26th 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
[105] 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 [34, ?**], and will** not be covered in this paper.

Bartholdi, Tovey, and Trick [12] 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 [97] 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-