Communications - November 2010

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.