figure 2. Ramon Llull, 13th-century mystic
and philosopher.
have more recent papers. 7, 11, 24, 25
However, their polynomial-time algorithms
sometimes involve truly astronomical
multiplicative constants.
Finally, we mention that in the
years since the work showing Lewis
Carroll’s election system to have a winner problem that is complete for parallel access to NP, a number of other systems, most notably those of Kemeny
and Young, have also been shown to be
complete for parallel access to NP. 33, 43
Naturally, researchers have sought to
bypass these hardness results as well
(for examples, see6, 9, 12, 36).
using complexity to Block
election control
Can our choice of election systems—and
not merely nasty ones with hard winner
problems but rather natural ones with
polynomial-time winner problems—be
used to make influencing election outcomes costly? We start the discussion
of this issue by considering problems
of election control, introduced by Bartholdi, Tovey, and Trick5 in 1992. In
election control, some actor who has
complete knowledge of all the votes
seeks to achieve a desired outcome—
either making a favored candidate be the
sole winner (“constructive control”) or
precluding a despised candidate from
being a unique winner (“destructive
control”)—via changing the structure
of the election. The types of structural
changes that Bartholdi, Tovey, and
Trick proposed are adding or deleting
candidates, adding or deleting voters,
or partitioning candidates or voters
into a two-round election structure.
Between these types and the different
tie-breaking rules that can be used to
decide which candidates move forward
from the preliminary rounds of two-round elections in the case of ties (that
is, whether all the tied people move forward or none of them do), there now
are eleven types of control that are typically studied—each having both a constructive and a destructive version.
For reasons of space we will not de-
fine all 11 types here. We will define
one type explicitly and will mention
the motivations behind most of the
others. Let us consider Control by De-
leting Voters. In this control scenario,
the input to the problem is the elec-
tion (C, V ), a candidate p ∈ C, and an
integer k. The question is whether by
removing at most k votes from V one
can make p be the sole winner (for the
constructive case) or can preclude p
from being a unique winner (for the
destructive case). Control by Delet-
ing Voters is loosely inspired by vote
suppression: It is asking whether by
the targeted suppression of at most k
votes the given goal can be reached.
(By discussing vote suppression we are
in no way endorsing it, and indeed we
are discussing paths toward making it
computationally infeasible.) So, for a
given election system E, we are inter-
ested in the complexity of the set com-
posed of all inputs (C, V, p, k) for which
the goal can be reached.c
c As to who is seeking to do the control, that is ex-
ternal to the model. For example, it can be some
central authority or a candidate’s campaign
committee. In fact, in the real world there often
are competing control actors. But results we
will soon cover show that even a single control
actor faces a computationally infeasible prob-
lem. Also, the reader may naturally feel uncom-
fortable with the model’s assumption that the
The other control types similarly
are motivated as abstractions of real-
world actions—many far more savory
than vote suppression. For example,
Control by Adding Voters abstracts
such actions as get-out-the-vote drives,
positive advertising campaigns, pro-
viding vans to drive elderly people to
the polls, registration drives, and so
on. Control by Adding Candidates and
Control by Deleting Candidates reflect
the effect of recruiting candidates
into—and pressuring them to with-
draw from—the race. The memory of
the 2000 U.S. presidential race sug-
gests that whether a given small-party
candidate—say Ralph Nader—enters
a race can change the outcome. The
partition models loosely capture other
behaviors, such as gerrymandering.
figure 3. the points assigned by the Llull/copeland systems in the head-to-head contests
of the election of figure 1.
1. Llull
2. copeland
: 0
: 1
: 1
: 1
: 0
: 1
:0:0
:0
:1: 1
:
: 1
: 0
: 0
: 1
: 0.5
: 0.5
: 0.5
: 0.5
: 0
: 1
: 0
: 1
: 1
: 0
: 0
: 1