a certain number of candidates, the
manipulation problem becomes easy.
Conitzer, Sandholm, and Lang15
provide a detailed study of this behavior,
showing for each of many election systems the exact number of candidates
necessary to make its (constructive,
weighted, coalitional) manipulation
problem computationally infeasible.
For example, in this setting manipulation is easy for Borda with up to two candidates, but becomes infeasible when
restricted even to three candidates.
In contrast, it is well known that
manipulation is simple for plurality
elections regardless of the number of
candidates. That is unfortunate, since
plurality elections are the most common and most important elections in
the real world.
What holds for scoring-rule election systems other than plurality? One
could try analyzing scoring systems
one at a time to see which are subject to manipulation, but it might be
a long slog since there are an infinite
number of scoring systems. This motivates us to look toward an excellent
general goal: finding a dichotomy theorem that in one fell swoop pinpoints
what it is about an election system
that makes it vulnerable to manipulation or that makes manipulation
computationally prohibitive. For
scoring systems, this was achieved in
Hemaspaandra and Hemaspaandra29
(see also the closely related work15, 42),
figure 4. an example of a weighted
plurality election.
each bar represents a weighted vote for a
particular candidate. We can make p a winner by bribing the weight- 5 voter to vote for
p, but bribing only the heaviest voter to vote
for p would not be sufficient.
8
6
5
4
2
0
6
c1
4
c2
2
p
which showed that scoring systems
are NP-complete to manipulate (in the
weighted setting) precisely if they allow “diversity of dislike” (that is, the
point values for the second favorite
and least favorite candidates differ),
and that all other scoring systems are
easy to manipulate. From this it follows that the only easily manipulable
scoring systems are an infinite collection of trivial systems, plurality, and
an infinite collection of systems that
are disguised, transformed versions
of plurality; all other scoring systems
are NP-hard to manipulate.
There has been an intense effort
to circumvent such hardness results.
Indeed, the seminal paper on manipulation3 provided a greedy single-voter
manipulation algorithm that was later
proved to also work in an interesting range of coalitional-manipulation
settings. 42, 49 An influential paper of
Conitzer and Sandholm14 shows that
voting systems and distributions that
on a large probability weight of the inputs satisfy certain conditions have a
manipulability-detection algorithm
that is correct on at least that same set
of inputs. A different line of research focuses on analyzing the probability with
which a randomly selected election is
susceptible to a given form of manipulation. 16, 28, 47, 48 In the standard probabi-listic model used in this line of work,d
for many natural election systems the
probability that a voter can affect the
result of an election by simply casting a
random vote is small but nonnegligible.
This work is motivated by perhaps
the greatest single worry related to using NP-hardness to protect elections—
a worry that applies to NP-hardness results not just about manipulation, but
also about control and bribery. That
worry is that NP-hardness is a worst-case theory, and it is in concept possible that NP-hard sets may be easily
solved on many of their input instances even if P and NP differ.e Levin has
d This model is called impartial culture. In impartial culture each vote is chosen uniformly
at random from the set of all permutations of
the candidates.
famously developed the theory of average-case NP-hardness, 37 and although
that theory is difficult to apply and is
tied to what distributions one uses, it
would be extremely interesting to establish that the manipulation, control,
and bribery problems for important
election systems are average-case NP-
hard with respect to some appropriate
and compellingly natural distribution.
A very exciting new path toward
circumventing hardness-of-manipulation results (and, potentially, toward
more generally circumventing hardness results about election-related issues) is to look at restricted domains
for the collections of votes the electorate may cast. In particular, there
is a very important political science
notion called “single-peaked preferences,” in which the candidates are
modeled along an axis, such as liberal
to conservative, and as one goes away
from each voter’s most preferred candidate in either of the axis’s directions
the voter prefers the candidates less
and less. Walsh46 raised the fascinating question of whether hard election-manipulation problems remain hard
even for electorates that follow the
single-peaked model, and he provided
natural examples in which manipulation problems remain hard even when
restricted to single-peaked electorates.
In contrast, and inspired by a different part of Walsh’s paper that showed
some profile completion problems
are easy for single-peaked electorates,
a recent paper by Faliszewski et al. 27
shows that for single-peaked electorates many NP-hard manipulation and
control problems have polynomial-time algorithms. The point of—and
threat of—this research line is that
for electorates that are single-peaked,
can be many-one polynomial-time reduced
to) a set that is easy on overwhelmingly many
of its instances. 21 Unfortunately, this does not
necessarily imply that the original set is easy
on overwhelmingly many of its instances. In
fact, it is known that relative to a random “
oracle” (black box), there are NP sets on which no
polynomial-time heuristic algorithm can do
well. 34 Also, it is well known that if any NP-hard
set has a polynomial-time heuristic algorithm
that is correct on all but a “sparse” amount of
its input, then P = NP. 44 However, “sparse” in
that research line is so small as to not reassure
us here. And, finally, there has been much interest in distributions, problems, and settings
that remove the gap between worst-case and
average-case complexities. 1, 38