[EM] Re: Counting Time

[Paul Kislanko]

Forest Simmons wrote (Thursday, January 20, 2005)

> Here's a quick way to find the Condorcet Winner if there is one:
> 
> Use Rob LeGrand's ballot by ballot approval idea, but instead 
> of ballot by 
> ballot, use voter by voter.
> 
> For fairness, either randomize the order of polling the 
> voters or else 
> poll them twice, once from left to right, and once from right 
> to left, so 
> that each voter gets to vote twice.

 This is an example of how terminology can confuse me.

In what way is "voter by voter" different from "ballot by ballot"? Until I
read this I would have considered those phrases synonymous.

But, Mike Ossippoff was kind enough to provide me the other day a very
efficient way to find the CW if there is one, and more generally how to find
the Smith Set which will have one member if there's a CW.

1. For each ballot, for each pair of candidates {X, Y} count defeat.X =
defeat.X if the voter ranked Y better than X, defeat.Y = defeat.Y +1 if the
voter ranked X better than Y. If equal rankings are allowed, leave both
defeat.X and defeat.Y at their current values if on this ballot the voter
specified X=Y. 

2. Sort the candidates by defeat.candidate in ascending order. The candidate
with the lowest number of these pairwise-by-voter defeats are in the Smith
Set, and if no alternative pairwise-defeats (according to the
pairwise-matrix SUM over all ballots) then the that identifies the CW.

If there's not a CW you can continue to construct the Smith Set by the
simple rule "all X with defeat.X equal to or higher than the most recent
addition to the Smith Set and have a pairwise-win over the most recent
addition to the Smith Set are also in the Smith Set", and iterate until no
remaining candidate has a pairwise win over any of the previously identified
candidates.

This is very fast, as it can almost be done as a byproduct of constructing
the pairwise matrix. The key is you have to "do over ballots" to count
pairwise defeats. You cannot get that information from the pairwise matrix.