NP-hardness results simply may fail to
hold. And the reason that can happen
is the assumption of single-peaked
preferences is so restrictive that it can
rule out some of the collections of
votes used in the outputs of reductions
in general-case NP-hardness proofs.
Yet another path toward circumventing hardness-of-manipulation
results leads to relaxing the notion
of solving a manipulation problem.
Procaccia and Rosenschein42
initiated this approach by showing that
the heuristic from the seminal work
of Bartholdi, Tovey, and Trick, 3 when
extended to a coalitional manipulation setting, works correctly on an
interesting class of scoring-system
manipulation instances. By an even
more careful analysis, together with
Zuckerman, they later extended this
result to a number of other election
systems, 49 and they obtained approximation results and results that for manipulable instances are guaranteed to
return a manipulation that will work if
one is allowed to add a certain number
and weight of additional manipulators. Brelsford et al. 8 provide their own
framework for studying approximability of manipulation problems (as well
as approximability of bribery and control problems) and for a large class of
scoring systems gives approximation
algorithms for manipulation.
Returning to playing defense, what
can we do if a system has a polynomial-time manipulation algorithm? Can we
somehow feed the system a can of spinach and turn it fearsome? To a surprising extent the answer is yes, as studied
in work of Conitzer and Sandholm13
and Elkind and Lipmaa. 19 They variously do this by adding an elimination
“pre-round” (that may or may not be
based on a hypothetical one-way function) or by changing the election into
a long series of rounds of candidate
elimination. The good news is that this
approach often boosts the complexity,
and the bad news is that these multi-round election systems are simply not
the same intuitively attractive animals
that they are built from.
using complexity to Block
Bribery in elections
The complexity-theoretic study of
bribery in elections was proposed by
Faliszewski, Hemaspaandra, and He-
maspaandra, 24 and started far more
recently than did the complexity-the-
oretic study of control and manipu-
lation of elections. Bribery comes in
many variants, but the basic pattern
is just what the term brings to mind.
The briber has a certain budget, the
voters (who depending on the model
may or may not have weights) each
have a price for which their vote can be
bought, and depending on the model
voters may or may not be required to
each have unit cost (the former case
is referred to as the “without prices”
case). And the question is whether
the briber can achieve his or her
goal—typically, to make a preferred
candidate p be a winner—within the
budget. Note that bribery has aspects
of both control and manipulation.
Like some types of control one has to
choose which collection of voters to
act on, but like manipulation one is
altering votes.
hand, if one changes one’s model and
associates a cost not to each voter, but
rather to each pairwise preference of
each voter (so the more one changes a
given voter’s vote, the more one has to
pay—so-called “microbribery”), Llull
bribery (without weights) can be done,
in a slightly different model that allows irrational preferences, in polynomial time. 25
summary
In this article, we discussed some of
the main streams—control, manipulation, and bribery—in the study of
how complexity can be used as a shield
to protect elections (see Faliszewski
et al. 26 for a more technical survey).
This line was started by the striking
insight of Bartholdi, Orlin, Tovey, and
Trick (see also Simon45 for even earlier
roots) that although economics proves
we cannot make manipulation impossible, we can seek to make it computationally infeasible. As we have seen,
many hardness results have been obtained, as have many polynomial-time
attacks. Election systems and settings
vary greatly in the behaviors one can
establish. It is natural to consider
an election system’s computational
weaknesses and strengths, as one factor among many, when choosing an
election system for a given task, and
in particular to choose a system carefully in light of the types of attacks one
most needs it to thwart. Yet the work
on computational protection of elections has also energized the search for
end runs around that protection, such
as approximation algorithms and heuristics having provably frequent good
performance, and one must also worry
about such potential end runs when
making one’s election-system choice.
This work all falls within the
emerging area known as computational social choice (see Chevaleyre et
al. 10 for a superb survey), an area that
links AI, systems, and theory within
computer science, as well as economics, political science, mathematics,
and operations research. Elections
have been important for thousands
of years, and with the current and
anticipated increase of electronic
agency, elections become more important—and more open to attacks—
with each passing year. The current
push-pull between using complexity