a group of people is deciding where to go for dinner together, one of them may prefer American food to Brazilian, and Brazilian to Chinese. This person’s vote can then be expressed as A ≻ B ≻ C.

Given everyone’s vote, which cuisine should be chosen? The answer is far from obvious. We need a voting rule that takes as input a collection of votes, and as output returns the winning alternative. A simple rule known as the plurality rule chooses the alternative that is ranked first the most often. In this case, the agents do not really need to give a full ranking: it suffices to indicate one’s most-preferred alternative, so each agent is in fact just voting for a single alternative.

Another rule is the anti-plurality rule, which chooses the alternative that is ranked last the least often. Now, it suffices for agents to report their last-ranked alternative—they are voting against an alternative. Which of these two rules is better? It is difficult to say. The former tries to maximize the number of agents that are happy about the choice; the latter tries to minimize the number that are unhappy. Another rule, known as the Borda rule, tries to strike a balance: when there are three alternatives, it will give two points to an alternative whenever it is ranked first, one whenever it is ranked second, and zero whenever it is ranked last. Many other rules, most of them not relying on such a points-based scheme, have been proposed; social choice theorists analyze the desirable and undesirable properties of these rules.

Rather than just choosing a winning alternative, most of these rules can also be used to find an aggregate ranking of all the alternatives. For example, we can sort the alternatives by their Borda score, thereby deciding not only on the “best” alternative but also on the second-best, and so on. There are numerous applications of this that are relevant to computer scientists: as an illustrative example, one can pose the same query to multiple search engines, and combine the resulting rankings of pages into an aggregate ranking.

One particularly nice rule for such settings is the Kemeny rule, which finds an aggregate ranking of the alternatives that “minimally disagrees” with the input rankings. More precisely, we say that a disagreement occurs when-

While enabling
the use of
computationally
demanding voting
rules is valuable,
I believe that in
the near future,
computer scientists
will make much
larger contributions
to the theory and
practice of voting.

ever the aggregate ranking ranks one alternative above another, but one of the voters ranks the latter alternative above the former. The Kemeny rule produces a ranking that minimizes the total number of such disagreements (summed over both voters and pairs of alternatives).

The Kemeny rule has a number of desirable properties. For one, if we assume that there exists an unobserved “correct” ranking of the alternatives (reflecting their true quality), and each voter produces an estimate of this correct ranking according to a particular noisy process, then the Kemeny rule produces the maximum likelihood estimate of the correct ranking. 40

Unfortunately, finding the Kemeny rule’s output ranking is computationally intractable (formally, NP-hard). 3 Nevertheless, there are algorithms that can usually solve the problem in practice. 8 As an example, in Duke University’s computer science department, we have used the Kemeny rule to find an aggregate ranking of our top Ph.D. applicants (based on the rankings of the individual admissions committee members); using the CPLEX solver, we found the Kemeny ranking more than 100 applicants in under a minute.

While enabling the use of computationally demanding voting rules such as the Kemeny rule is valuable, I believe that, in the near future, computer scientists (specifically, the computational social choice community) will make much larger contributions to the theory and practice of voting. Real-world organizations often need to make not just a single decision, but rather decisions on a number of interrelated issues. In our dining example, the agents need to decide not only on a restaurant, but also on the time of the dinner; and an agent’s preferred restaurant may depend on the time of the dinner. For example, an agent may prefer not to start a heavy Brazilian steakhouse meal shortly before going to bed.

In some sense, the “correct” way of handling this is to make the alternatives combinations of a time and a cuisine, so that an agent can say: “I prefer an early Brazilian meal to a late Chinese meal to…” However, this straightforward approach rapidly becomes impractical as more issues are combined, because the number of al-