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.