[EM] Need IRV examples; voting show

[Markus Schulze]

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
(matt at tidalwave.net).

Markus Schulze

----
For more information about this list (subscribe, unsubscribe, FAQ, etc), 
please see http://www.eskimo.com/~robla/em