Dear Markus, thanks for filling us in on the terminology and historical references.
On Wed, 1 Jan 2003, Markus Schulze wrote: > 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 > > ---- For more information about this list (subscribe, unsubscribe, FAQ, etc), please see http://www.eskimo.com/~robla/em
