[EM] Re: Election-methods Digest, Vol 4, Issue 13

[Matthew Dempsky]

On Mon, 2004-10-11 at 20:45, Gervase Lam wrote:

> Kemeny can be basically described as follows:
> 
> (1) Divide each number in the Result Matrix by the number of ballots cast.
> (2) Find a ranking (e.g. C>B>A) that creates a pairwise matrix that 
> matches the Result Matrix the closest.  This ranking is the Kemeny Ranking.
> 
> [...example elided...]

It seems similar in concept to finding the line of best fit, which I'll
note tries to minimize the sum of squared differences rather than simply
the sum of absolute differences.  Has that alternative been considered? 
Also, the method doesn't seem to scale very well.  Unless there's some
simpler trick to determining the closest Result Matrix than brute force,
it's an O(N!) algorithm at best.  3 options (6 permutations) might be
feasible, but 7 options would cause 5,040 permutations and 10 options
would cause 3,628,800 permutations.  (Having never been old enough to
vote before, I have to guess at the range of candidates running for
president.)  Assuming changing to a system other than Plurality were to
encourage parties to have multiple candidates participate or more third
party participation, I could only expect these numbers to continue to
grow.

Finally, what about considering rankings such as A>B=C or A=B>C?  Also,
what about relations that can't be expressed in that limited notation
such as (simultaneously) A>B>C and A>D>E>C (i.e. B is indifferent from D
and E, but D is preferred to E).  I think any irreflexive,
anti-symmetric, transitive relation on the set of candidates would be
valid.

On that note, is there any reason (other than to avoid confusing
voters), to restrict votes to total orderings rather than partial
orderings?
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: This is a digitally signed message part
URL: <http://lists.electorama.com/pipermail/election-methods-electorama.com/attachments/20041013/a984acd1/attachment-0003.pgp>