of the World Cup soccer tournament, except there (after rescaling) wins get one point and ties get one third of a point. Figure 3 shows how the election from Figure 1 comes out under the Llull and Copeland systems. In Table 1, I (immunity) means one can never change the outcome with that type of control attack—a dream case; R ( resistance) means it is NP-hard to determine whether a given instance can be successfully attacked—still a quite good case; and V (vulnerability) means there is a polynomial-time algorithm to detect whether there is a successful attack of the given type (and indeed to produce the exact attack)—the case we wish to avoid.

Remarkably, given that Llull created his system in the 1200s, among all natural systems based on preference orders, Llull and Copeland are the systems that currently have the greatest numbers of proven resistances to control. As one can see from Table 1, Copeland is perfectly resistant to the constructive control types and to all voter-related control types (but is vulnerable to the destructive, can-didate-related control types). And Llull’s 13th-century system is almost as good. Ramon Llull, the mystic, truly was ahead of his time.

If one wants an even greater number of resistances than Copeland/Llull provides, one currently can do that in two different ways. Recently, Erdélyi, Nowak, and Rothe22 showed that a voting system whose votes are in a different, richer model—each voter provides both an approval vector and a strict ordering—has a greater number of control resistances, although in achieving that it loses some of the particular resistances of Copeland/Llull. And Hemaspaandra, Hemaspaandra, and Rothe32 constructed a hybridization scheme that allows one to build an election system whose winner problem—like the winner problem of all four systems from Table 1—is computationally easy, yet the system is resistant to all 22 control attacks. Unfortunately, that election system is in a somewhat tricky manner “built on top of” other systems each of which will in some cases determine the winner, and so the system lacks the attractiveness and transparency that real-world voters reasonably expect.

the current push-
pull between using
complexity as a
shield and seeking
holes in and paths
around that shield is
a natural part of the
drama of science.

To conclude our discussion of control, we mention one other setting, that of choosing a whole assembly or committee through an election. Such assem-bly-election settings introduce a range of new challenges. For example, the voters will have preferences over assem-blies rather than over individual candidates. We point the reader to the work of Meir et al. 40 for results on the complexity of controlling elections of this type.

using complexity to Block
election manipulation

Manipulation is often used informally as a broad term for attempts to affect election outcomes. But in the literature, manipulation is also used to refer just to the particular attack in which a voter or a coalition of voters seeks to cast their votes in such a way as to obtain a desired outcome, for example, making some candidate win. In formulating such problems, one often studies the case in which each voter has a weight, as is the case in the electoral college and in stockholder votes. The input to such problems consists of the weights of all voters, the votes of the nonmanipulators, and the candidate the manipulators are trying to make a winner.

Manipulation problems have been studied more extensively than either control or bribery problems, and so the literature is too broad to survey in any detail. But we now briefly mention a few of the key themes in this study, including using complexity to protect, using algorithms to attack, studying approximations to bypass protections, and analyzing manipulation properties of random elections.

The seminal papers on complexity of manipulation are those of Bartholdi, Orlin, Tovey, and Trick. 2, 3 Bartholdi, Tovey, and Trick3 gave polynomial-time algorithms for manipulation and proved a hardness-of-manipulation result (regarding so-called second-order Copeland voting). Bartholdi and Orlin2 showed that for “single transferable vote,” a system that is used for some countries’ elections, whether a given voter can manipulate the election is NP-complete, even in the unweighted case.

Even if election systems are proven intractable to manipulate in general, it remains possible that if one allows only