[EM] New Condorcet/RP variant

[Paul Crowley]

I'd like to propose another MAM/MMV/CIVS variant.  I think this one is
conceptually simpler than any of those three and has neat tiebreaking.
 The tiebreaking rule is "where all greater preferences have already
been decided and two equal preferences contradict each other, choose
the one that does best on the preferences below it".  However, the
formal expression of this rule is actually somewhat cleaner, though it
may read strangely to those more used to such rules being described
directly in terms of feasable algorithms.

Consider a potential ordering of the candidates, and show the
preference matrix with the candidates in that order.  For example,
consider the preference matrix at the bottom of this page:

http://www5.cs.cornell.edu/cgi-bin/andru/civs/results?id=E_4dcecf4df0550b93

The upper triangle of the preference matrix shows the numbers of votes
affirmed by that order for each pair, and the lower triangle shows the
numbers of votes contradicted; for example, the fact that the ordering
ranks Clark above Edwards confirms 39 votes, and contradicts 35.  The
"sorted preference list" for a given ordering is a list of all the
numbers in this upper triangle, in sorted order.  Duplicates are of
course preserved, so every list has n(n-1)/2 elements where n is the
number of candidates.

Lexicographic sorting imposes a total ordering on sorted preference
lists; the result of the election is the ordering whose sorted
preference list comes highest in this lexicographic sorted order.

In the extremely rare instance that two or more orderings have exactly
the same multiset of numbers in the upper triangle of their preference
matrix, one such maximally good ordering is chosen fairly at random. 
This is the only instance where the procedure is nondeterministic.  (I
take it that it's obvious no fully deterministic procedure can satisfy
universality, anonymity, and neutrality)

In a public election where all the numbers can be expected to differ,
this makes the same decision as MAM/MMV/CIVS, but where there are ties
I think this is the fairest and cleanest way to break them.

I've proven that this system satisfies monotonicity and the Smith
Criterion (ie it will never rank a non-member of the Smith set above a
member of the Smith set); I'm working on other proofs.  The proofs
come out quite short and neat, especially the latter one, which gives
me confidence that this method has nice properties.  It's immediately
obvious it satisfies anonymity, neutrality, and homogeneity.

Efficient implementation involves trying different possibilities where
there are ties and backtracking.  If there are many ties it could
potentially be very slow, but for any normal election it should be as
efficient as any system needs to be.

I look forward to hearing what list members think...
-- 
  __
\/ o\ Paul Crowley
/\__/ www.ciphergoth.org