Computing Slater Rankings Using Similarities Among Candidatesby Vincent Conitzer, Electroic Commerce 2006 (Search google.com or citeseerx.ist.psu.edu or scholar.google.com to find the full text of this article.)
As Dr. Connitzer wisely reminds us, the Slater index and Kemeny index are different but related. Let's say every voter gives us their preferences or rankings. Maybe the faculty in a department gives us their ranking of preferences for incoming graduate students. How do we get a ranking for every alternative. A Slater index gives us a ranking for the set where the least number of pairwise elections would be wrong.
We know from Arrow theory that one cannot find a reasonable algorithm to combine the rankings. One of the problems is that a mechanism might be disturbed by an irrelevant alternative. Assume that A wins an election against B, we throw in a candidate Q which everyone dislikes compared to A and B. Then, adding Q or deleting to the list of alternatives should not change whether A or B would win.
The Slater index just adds that ranking a blech factor of negative one with 40% preferring that to the more preferred A above B. If it rated V above Q, that would also be a blech factor negative one, even though only twenty percent would like that bad ranking. A Kemeny index looks at how many people dislike a combination. In the above case, the ranking would get a blech factor of 60% and the second a blech factor of 80%. The goal of both the Slater or Kemeny methods is to reduce the "blech" factor for the number of bad comparisons.
Unfortunately, finding the best ranking in either categorization is NP complete to evaluate. That is they are NP complete to find out what the best ranking would be.
Dr. Connitzer found a good way to compute the best ranking, by finding groups of candidates that can be treated the same for all other candidates, "similar" candidates. Example: A B C D E F G H I J are running.
A defeats E A defeats F B defeats E B defeats F C defeats E C defeats F D defeats E D defeats F E defeats G F defeats G E defeats H F defeats H E defeats I F defeats I E defeats J F defeats JDr. Conitzer's would find that E and F are similar. He finds a hierarchy structure of sets and subsets thereof where each level in the hierarchy is a similarity set.
So what? If we have thirty candidates--they could be alternatives in a referendum, with ten issues and 191 voters, his algorithm can find the ranking instantaneously, while other algorithms take fourty seconds or so. And it finds a solution when other cannot.
Now this doesn't handle millions of voters--should we use some sort of approximation?
Improved Bounds for Computing Kemeny RankingsVincent Conitzer, Andrew Davenport, Jayant Kalagnanam.
Assume there is an election between two alternatives, A and B. The voters can only tell which is better or more correct with a probability of slightly above 50%. Each voter votes for the one that seems the best to them. We saw that if one simply takes the majority, there is a very high likelihood--in reasonable sized electorates, of getting the correct answer or best alternative. This is Condorcet's theorem.
But what if there are dozens of alternatives. It turns out that the Kemeny method would give us the best answer, and each voter had an imperfect idea of what was the best decision. And other voting systems correspond to other models, which is a different paper and a later Thoughtful Thursday.
Of course, there is no reliable way to solve large instances of these. Dr. Connitzer raised the issue of approximations to the Kemeny method--but is that what people were promised. We have seen very close elections, and certainly to have the result be an approximation that could be wrong. Dr. Connitzer developed algorithms to compute the Kemeny method. I won't give the detailed description because I doubt that the readers are interested and if they are, his article describes it far better than I could. But three idea of operations research/computer science are important
An interesting idea would be that after an election, one could have a competition to determine the optimal Kemeny ranking. Different groups of computing scientists could produce a ranking and its Kemeny distance. (It is very easy to verify the Kemeny distance of a given ranking.) The ranking with the minimum Kemeny distance would be the winner. Thus, an agrieved group who narrily lost an election could pay for supercomputer time to try and find a better ranking that hopefully would get what they wanted. One could have some sort of prize for the team of operations researchers and programmers that found a winner.
As I believe I mentioned, if there are thousands of alternatives, e. g. tax codes with slightly different structures, each voter would vote on a subset of alternatives. Drs. Kenyon-Mathieu and Schudy spoke about this in their article on "How to Rank with Few Errors" where they said "In statistics and psychology, one motivation is ranking by paired comparisons: here, you wish to sort some set by some objective but you do not have access to the objective, only a way to compare a pair and see which is better; for example, determining people's preferences for types of food" or perhaps preference for tax code. (I will Thoughtful Thursday this material here.) These would be combined in the same manner and described here as if each voter gave a full preference order.