of the World Cup soccer tournament,
except there (after rescaling) wins get
one point and ties get one third of a
point. Figure 3 shows how the election
from Figure 1 comes out under the
Llull and Copeland systems. In Table
1, I (immunity) means one can never
change the outcome with that type of
control attack—a dream case; R (
resistance) means it is NP-hard to determine whether a given instance can
be successfully attacked—still a quite
good case; and V (vulnerability) means
there is a polynomial-time algorithm
to detect whether there is a successful
attack of the given type (and indeed to
produce the exact attack)—the case
we wish to avoid.
Remarkably, given that Llull created his system in the 1200s, among all
natural systems based on preference
orders, Llull and Copeland are the
systems that currently have the greatest numbers of proven resistances
to control. As one can see from Table
1, Copeland is perfectly resistant to
the constructive control types and to
all voter-related control types (but is
vulnerable to the destructive, can-didate-related control types). And
Llull’s 13th-century system is almost
as good. Ramon Llull, the mystic, truly
was ahead of his time.
If one wants an even greater number of resistances than Copeland/Llull
provides, one currently can do that in
two different ways. Recently, Erdélyi,
Nowak, and Rothe22 showed that a voting system whose votes are in a different, richer model—each voter provides
both an approval vector and a strict
ordering—has a greater number
of control resistances, although in
achieving that it loses some of the
particular resistances of Copeland/Llull. And Hemaspaandra,
Hemaspaandra, and Rothe32
constructed a hybridization scheme that
allows one to build an election system
whose winner problem—like the winner problem of all four systems from
Table 1—is computationally easy, yet
the system is resistant to all 22 control
attacks. Unfortunately, that election
system is in a somewhat tricky manner
“built on top of” other systems each
of which will in some cases determine
the winner, and so the system lacks the
attractiveness and transparency that
real-world voters reasonably expect.
the current push-
pull between using
complexity as a
shield and seeking
holes in and paths
around that shield is
a natural part of the
drama of science.
To conclude our discussion of control, we mention one other setting, that
of choosing a whole assembly or committee through an election. Such assem-bly-election settings introduce a range
of new challenges. For example, the
voters will have preferences over assem-blies rather than over individual candidates. We point the reader to the work of
Meir et al. 40 for results on the complexity
of controlling elections of this type.
using complexity to Block
election manipulation
Manipulation is often used informally
as a broad term for attempts to affect
election outcomes. But in the literature, manipulation is also used to refer
just to the particular attack in which a
voter or a coalition of voters seeks to
cast their votes in such a way as to obtain a desired outcome, for example,
making some candidate win. In formulating such problems, one often studies the case in which each voter has a
weight, as is the case in the electoral
college and in stockholder votes. The
input to such problems consists of the
weights of all voters, the votes of the
nonmanipulators, and the candidate
the manipulators are trying to make a
winner.
Manipulation problems have been
studied more extensively than either
control or bribery problems, and so
the literature is too broad to survey in
any detail. But we now briefly mention
a few of the key themes in this study,
including using complexity to protect,
using algorithms to attack, studying
approximations to bypass protections,
and analyzing manipulation properties
of random elections.
The seminal papers on complexity of manipulation are those of Bartholdi, Orlin, Tovey, and Trick. 2, 3
Bartholdi, Tovey, and Trick3 gave
polynomial-time algorithms for manipulation and proved a hardness-of-manipulation result (regarding so-called second-order Copeland voting).
Bartholdi and Orlin2 showed that for
“single transferable vote,” a system
that is used for some countries’ elections, whether a given voter can manipulate the election is NP-complete,
even in the unweighted case.
Even if election systems are proven
intractable to manipulate in general, it
remains possible that if one allows only