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
-- [EMAIL PROTECTED] 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.
---- Election-methods mailing list - see http://electorama.com/em for list info
