Finding the probable best candidate?

[Rob LeGrand]

Forest wrote:
> > 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

Very interesting!  Has anyone come up with an objective measure of
manipulability?  Nanson itself has an average SU much worse than Schulze or
even Ranked Pairs, and Baldwin (Borda-elimination) is even worse.  I wonder
whether Inverse Nanson would really beat Schulze on SU.  Worth a try, though .
. .

> 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 bottom and
> 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.

I see.  Your sink sort is what I've heard called bubble sort, and your bubble
sort I've heard called insertion sort.  I'd never seen an O(n log n) insertion
sort before, but the scheme you describe certainly makes sense.  I'd guess that
the number of actual swaps would still be O(n^2), though.

=====
Rob LeGrand
honky98 at aggies.org
http://www.aggies.org/honky98/

__________________________________________________
Do You Yahoo!?
Yahoo! Sports - Coverage of the 2002 Olympic Games
http://sports.yahoo.com