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