[EM] Round Robins

[Jobst Heitzig]

Dear Alex!

You wrote:
> Naming something after a theorist is
> fine in academic circles, 

There is disagreement about this since it leads too often to the wrong
person getting the credit...

> Then somebody wrote:
>> I'm not so sure, Jan, since many Condorcet-efficient methods do not
>>  require all (n-1)*n/2 pairwise comparisons to be carried out. For 
>> example, ROWS is Condorcet-efficient and only requires n-1
>> comparisons, which is by far less.
> 
> What is ROWS?

That was me. ROWS is "Random Order Winner Stays":
1. Sort all candidates into a random order.
2. Compare the first two and drop the defeated one. Compare the winner
of that comparison to the next candidate and again drop the defeated
one. Elect the winner of the last pairwise comparison. This method is
monotonic and Smith-efficient and requires only n-1 pairwise
comparisons. No method can find the Beats-All-Winner with fewer comparisons.

Of course, ROWS is not a good method, since it's not clone-proof, for
example. But like ROACC, we can modify it to meet clone-proofness by
using a more sophisticated order in step 1. For example, this order can
be from bottom to top on a random ballot (as in RBCC), which I would
call RBWS. Or the order could be from least to most approved (as in
TACC), which I would call TAWS. Or by processing X before Y when on the
first randomly drawn ballot on which the approval cutoff divides X and
Y, Y but not X is approved (as in RBACC), which I would call RBAWS. All
these methods are clone-proof, monotonic, and Smith-efficient, and need
only n-1 pairwise comparisons.

Yours, Jobst