Dear Forest, you wrote (31 Dec 2002): > Determining the Kemeny order from ranked preference ballots suffers the > "combinatorial explosion" because there is no way of getting around one by > one testing of most of the N! permutations of candidates in order to see > which of these permutations minimizes the average distance to the ballot > orders. > > Distance is measured by the number of "neighbor swaps" required to convert > one order into another. > > So the Kemeny order is computationally intractable for large number of > candidates. In other words, it's the large number of candidates, rather > than the large number of voters, that makes the Kemeny order prohibitively > difficult.
In graph theory and in combinatorial optimization, the calculation of the Kemeny order is called "Linear Ordering Problem". You will find a giantic list of references when you use this term. You wrote (31 Dec 2002): > If the method gives a complete ranking as output, and if two subsets of > ballots produce the same ranking, then the output based on the union of > the two subsets should agree with the two partial results. This is the so-called "Reinforcement Criterion". You wrote (31 Dec 2002): > In summary, the Kemeny order is an example of a Condorcet order that is > order consistent with subsets that unanimously agree on the order, which > is what Blake was looking for, if I remember correctly. To be more concrete: The Kemeny-Young method is the unique preferential single-winner method that simultaneously meets Anonymity, Neutrality, Pareto, Reinforcement, and Local Independence from Irrelevant Alternatives. This has been proven by Young and Levenglick in 1978. You wrote (31 Dec 2002): > Despite the intractability of the method for large numbers of candidates, > it seems like an ideal method for some situations. One application could > be in choosing between several orders that have been found by other means. As far as I remember correctly, this has also been proposed by Matt ([EMAIL PROTECTED]). Markus Schulze ---- For more information about this list (subscribe, unsubscribe, FAQ, etc), please see http://www.eskimo.com/~robla/em
