Communications - November 2010

in a 2-to- 2 tie, fails to beat fails to beat .

Although this example shows that Condorcet elections sometimes have no winner, some election systems—the so-called Condorcet-consistent systems— so value the naturalness of the notion of being a Condorcet winner that they ensure that when a Condorcet winner exists, he or she is the winner in their system. One particularly interesting system is the election system proposed by the famous author and mathematician Lewis Carroll in 1876. Carroll took an approach that should warm the hearts of computer scientists. He said, in effect, that whoever had the smallest edit distance from being a Condorcet winner was the winner in his election system. His edit distance was with respect to the number of sequential exchanges of adjacent candidates in voter orderings. So in the Figure 1 example, and tie and tie tie as Carroll winners, since either of them with one adjacent exchange can become a Condorcet winner (for example, if we by one exchange turn voter 1’s preference list into > > > > > > > > > , then becomes becomes a Condorcet winner), but for example for example would take seven adjacent exchanges to become a Condorcet winner.

Lewis Carroll’s system is quite lovely
in that it focuses on the closeness to
Condorcet winnerhood. Carroll’s paper
has been included in books collecting
the most important social choice pa-
pers of all time. However, Carroll’s sys-
tem has one glaring flaw: It is compu-
tationally intractable to tell who won!
This was first shown in a paper by Bar-
tholdi, Tovey, and Trick, 4 who showed
that this problem was NP-hard. Later,
Hemaspaandra, Hemaspaandra, and
Rothe30 precisely classified the prob-
lem’s complexity as “complete” (that
is, in a certain formal sense the hardest
problem) for the class of problems that
can be solved by parallel access to NP (a
class that forms the Θp 2 level of the poly-
nomial hierarchy).a
On its face, this result is a disaster
for Lewis Carroll’s election system. Al-
though we want manipulation of elec-
tions to be difficult, we do not want to
achieve this by migrating to election
systems so opaque that we cannot ef-
ficiently compute who won.

polynomial-time greedy algorithms correctly find the Lewis Carroll winner all but an asymptotically exponentially vanishing portion of the time when the number of voters is more than quadratically larger than the number of candidates and the inputs are drawn from the uniform probability distribution. 35, 39 In fact, that algorithm can even be made “self-knowingly correct”—it almost always declares that its answer is correct, and when it does so it is never wrong. 35 Another way of arguably bypassing the hardness results for the Lewis Carroll winner problem is through approximation algorithms. For example, Caragiannis et al. 9 have recently developed two approximation algorithms for computing candidates’ scores in Carroll’s system. And a third way to sidestep the hardness results is to change the framework, namely, to assume that the number of candidates or the number of voters is bounded by a fixed constant, and to seek polynomial-time algorithms in that setting.b The seminal paper of Bartholdi, Tovey, and Trick4 successfully pursued this line, as b Many real-life settings have relatively few candidates. And a particularly interesting setting with few voters but many candidates comes from Dwork et al., 18 who suggested building a search engine for the Web that would simply query other search engines and then conduct an election given the search engines’ answers as votes.

table 1. the computational complexity of control in condorcet, copeland, Llull, and plurality elections.

the results regarding constructive control in Condorcet and plurality elections are due to bartholdi et al., 5 the results on destructive control for Condorcet and plurality are due to hemaspaandra et al., 31 and the results regarding llull and Copeland are due to Faliszewski et al. 25 Adding (unlimited number of) Candidates has not been explicitly studied in bartholdi et al. 5 and hemaspaandra et al., 31 but the results on this for Condorcet and plurality elections are corollaries to these papers’ proofs.

election system control type Adding (unlimited number of) Candidates Adding Candidates deleting Candidates run-off Partition of Candidates (ties Promote) run-off Partition of Candidates (ties eliminate) Partition of Candidates (ties Promote) Partition of Candidates (ties eliminate) Partition of voters (ties eliminate) Partition of voters (ties Promote) Adding voters deleting voters