[EM] Round Robins

[Dave Ketchum]

Agreed you do not need (n-1)*n/2 pairwise comparisons BUT, seems to me 
ROWS went too far:
      It will happily and efficiently return the CW if there is one.
      It does not know if there is a cycle, though the winner of the n-1 
comparisons will, at least, be a cycle member.

Easiest I can think of is another n-1 comparisons to see if the apparent 
winner is CW or only a cycle member and, if a member, keep going til you 
have the complete cycle.

DWK

On Mon, 14 Mar 2005 00:21:02 +0100 Jobst Heitzig wrote:

> 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

-- 
  davek at clarityconnect.com    people.clarityconnect.com/webpages3/davek
  Dave Ketchum   108 Halstead Ave, Owego, NY  13827-1708   607-687-5026
            Do to no one what you would not want done to you.
                  If you want peace, work for justice.