protecting elections, rather than on why and in what settings elections are used for aggregating preferences in the first place. The latter issue could itself fill a survey—but not this survey. However, before moving on we briefly mention a few varied examples of how elections can be useful in aggregating preference. In daily life, humans use elections to aggregate preferences in tasks ranging from citizens choosing their political representatives to an academic department’s faculty members selecting which job candidate to hire to conference business meeting attend-ees selecting future locations for their conference. In electronic settings, elections often can take on quite different, yet also interesting and important, challenges. For example, one can build a metasearch engine based on combining underlying search engines, in order to seek better results and be more resistant to “Web spam.” 18 One can use voting as an approach to building recommender systems41 and to planning. 20 Voting was already very important before computers and the internet existed, and in the modern world, where multiagent settings abound, the importance of voting is greater still.

In this article, we will discuss the successes and failures to date in using complexity to defend against three important classes of attacks on election systems: (structural) control attacks, (voter) manipulation, and bribery. In these three settings, high computational complexity is the goal. But first, we briefly discuss a case so surprising that one might not even think of it, namely, the case in which an election system is so complex that even determining who won is intractable.

We must first introduce the model of elections we will use throughout this article. While doing so, we will also define some election systems, such as plurality rule. An election consists of a candidate set C and a list V of votes (ballots) over those candidates. In almost all the election systems we discuss, a vote is simply a strict ordering of all the candidates, for example, “Nader > Gore > Bush” if the voter likes Nader most, Gore next most, and Bush least. An exception is approval voting, in which each vote is a bit-vector giving a thumbs-up or thumbs-down to each candidate.

An election system is simply a map-

Voting was already
very important
before computers
and the internet
existed, and in the
modern world,
where multiagent
settings abound,
the importance of
voting is greater
still.

ping from (C, V ) to a “winner set” W, Ø Í W Í C. Perhaps the most famous and common election system is plurality, in which each candidate who most often comes at the top of voters’ orders is put into W. We will focus quite a bit on plurality in this article, since it has been extensively studied with respect to using complexity to protect elections. Plurality is itself a special case of a broad class of election systems known as scoring systems or scoring-rule systems. In these, each candidate gets from each voter a certain number of points based on where he or she falls in the voter’s ordering, and whoever gets the most points wins. For example, the scoring point system for plurality (in k-candidate elections) is that a voter’s favorite candidate gets one point from that voter and the other k− 1 candidates get zero points from that voter. In the Borda election system, proposed in the 18th century, the points from favorite to least favorite are k− 1, k− 2, . . . , 0. In veto elections, the points are 1, 1, 1, . . . , 1, 0; that is, the voter in effect votes against one candidate. Scoring systems are a flexible, important class of voting systems and, as we will see, they are a class whose manipulation complexity (for fixed numbers of candidates) is completely analyzed. There are many other important election systems, but to move the article along, we will introduce them as we need.

An election system that immediately merits note is the Condorcet rule. In Condorcet elections, a candidate is a winner exactly if he or she beats each other candidate in head-to-head major-ity-rule elections under the voters’ preferences. Consider the election shown in Figure 1. In that election there is no Condorcet winner, since is beaten by is beaten by 3-to- 1, is beaten by 4-to-0, and is beaten by 4-to-0, and 4-to-0, and

figure 1. an election.