[EM] Need IRV examples; voting show

[Forest Simmons]

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