Finding the probable best candidate?

[Forest Simmons]

On Wed, 20 Feb 2002, Rob LeGrand wrote:

> Forest wrote:
> > In three way races Black, Ranked Pairs, and SSD all give the same answer
> > if there are no truncations, so none has any possible advantage over the
> > others in three way races without truncations.
> 

Oops!

> What about the election
> 
> 9:A>B>C
> 8:B>C>A
> 6:C>A>B
> 
> B wins under Black but A wins under Schulze and Ranked Pairs (plus Baldwin,
> Dodgson, Nanson and Minmax).

A wins under Borda Seeded Bubble Sort as well. 

> 
> > And (as I said before) the only reason I proposed Bubble Sorted Borda was
> > to find a simple method that would beat Black along the same lines as
> > Black.
> 
> Unfortunately, at least according to my simulations so far, BSBS is much worse
> at SU given sincere votes than BSSE or Black. 


I knew that, but that's part of the inevitable tradeoff.  The higher the
SU in this class of methods, the less likely that the votes will be
sincere.

My guess is ...

SU:        Borda > Black > BSSE > BSBS > Inverse Nanson > Schulze

Likelihood of sincere
ballots  : Borda < Black < BSSE < BSBS < Inverse Nanson < Schulze

Black has SU to spare, but it is still too manipulable in my opinion.

> But it's not bad; it's about on
> par with Schulze and is better than Ranked Pairs.  By the way, I think the sort
> BSBS uses is actually called an insertion sort, not a bubble sort.

Usually in insertion sort the new guy is tested against the middle of the
previously sorted guys.  Bubble sort starts the new guy at the bottomn an
lets him work up one place at a time.  Insertion sort is efficient on the
order of n*log(n) comparisons, while bubble sort requires about n*n/2
comparisons.

Sink sort is bubble sort in reverse.

It was surprising to me at first that sink sort and bubble sort don't
always give the same order.

You wouldn't expect insertion sort to give the same order because it skips
over some of the comparisons, assuming the transitive consistency that is
lacking in Condorcet ties.


> 
> > After experience with all of these four (and other closely related) 
> > methods I believe that Inverse Nanson (an iterated form of Borda Runoff)
> > is the best of these four methods based on Borda.
> 
> What is Inverse Nanson again?  How is it different from regular Nanson (or
> Baldwin)?  Is it monotonic?
> 

Sets aside the Borda winner, then sets aside the Borda winner of the
remaining, etc. down to until one candidate is left.  That candidate is
the first to be eliminated.

This first eliminated candidate will always be in the "reverse smith set."

The process is repeated among the uneliminated candidates, until there is
only one uneliminated candidate, the Inverse Nanson winner, which will
always be a member of the smith set.

I think it is monotone, but I haven't proven it.

Forest