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