In a voting (or rank aggregation) setting, each voter ranks all the alternatives (this ranking is called a vote), and subsequently these rankings are aggregated into a single ranking. The mapping from vote vectors to aggregate rankings is called the voting rule. Two important voting rules are the Kemeny rule, which minimizes the number of times that the aggregate ranking disagrees with a vote on the ranking of a pair of alternatives; and the Slater rule, which minimizes the number of times that the aggregate ranking disagrees with the majority of votes on the ranking of a pair of alternatives. Unfortunately, both of these rules are NP-hard to execute. I will talk about various computational techniques for executing these rules nonetheless, including bounds for use in search and a powerful preprocessing technique.

(Joint work with Andrew Davenport and Jayant Kalagnanam at IBM Research.)