Calculating the Smith set

[Bruce Anderson]

This message combines and superceeds two messages that I had previously sent 
(one on 21 Apr 1996, and one on 22 Apr 1996) but were never posted.

On Apr 20,  4:55pm, Steve Eppley wrote:
> Subject: Re: Calculating the Smith set?
> [The EM list is again having troubles.  Four of my posts bounced back 
> to me with "unknown mailer error 14".  I'm attempting to repost them.]
> 
> Steve E wrote [a Smith algorithm]:
> >>    Find the candidate(s) with the fewest pairwise defeats.  (These
> >>    candidate(s) are guaranteed to be in the Smith set.)  Create 
> >>    a list named Smith with just these candidate(s).
> >>  
> >>    for each candidate Ci in the (growing) Smith list
> >>       for each candidate Cj
> >>          if Ci did not pairwise-beat Cj
> >>             if Cj is not yet in the Smith list
> >>                append Cj to the Smith list
> >>             endif
> >>          endif
> >>       endfor
> >>    endfor
>  
> Bruce A replied:
> >It may not work--the line "append Cj to the Smith list" is too vague.
> 
> It wasn't vague to me, but this appears to be another instance of 
> Eppley's First Law of Communication: "The worst judge of how a 
> message will be interpreted is its author."
> 
> To a programmer, "list" and "append" have meanings which may not be 
> apparent to everyone.  Lists are ordered and have a first element 
> and a last element.  When a new element is appended to a list, it 
> is appended at the end and becomes the new last element.  
> 
> Another property of lists is that the pointer (a.k.a. address) to a
> list's first element can always be obtained.  Another property is
> that given a pointer to an element of a list there is a way to find
> the pointer to the next element.  (Attempting to find the pointer to
> the next element after the last element returns a special "null"
> pointer.)  So lists can be traversed from first to last.
> 
> If there was any vagueness, I think it would be in the line: 
>    "for each candidate Ci in the (growing) Smith list" 
> I'm implying that the candidates would be traversed from the first
> candidate of the list, in list order, until the "null" pointer is 
> returned by the attempt to find the next candidate.
> 
> When coded in a standard programming language instead of pseudocode,
> there will be no vagueness.
> 
> --Steve
> 
>-- End of excerpt from Steve Eppley

It turns out that the line I that didn't understand indeed was:
    for each candidate Ci in the (growing) Smith list
I took it to mean:
    for each candidate Ci in the current Smith list (note, this list will grow)
instead of:
    for each candidate Ci that is now in, or ever will be in, the Smith list

I think that, to understand the algorithm, one does need to know how "lists" and 
"pointers" work.  As I now understand "dynamic lists" and "pointers," your 
algorithm works and is of order N^2.  Accordingly, I withdraw my objections to 
that algorithm.  The algorithm also works (and may or may not be more efficient) 
if it is changed to:

    Find the candidate(s) with the fewest pairwise defeats.  (These
    candidate(s) are guaranteed to be in the Smith set.)  Create 
    a list named Smith with just these candidate(s).

    for each candidate Ci (ever) in the (dynamically growing) Smith list
       for each candidate Cj on the ballot
          if Cj is not in the current Smith list
             if Ci did not pairwise-beat Cj             
                append Cj to the (end of the current) Smith list
             endif
          endif
       endfor
    endfor
    
    The Smith set is the set of candidates on the final Smith list.

I do not know whether either or both of these algorithms are either more or less 
efficient than my (unproven) algorithm; but, as you said, they are going to be 
so quick that increasing the efficiency here is not likely to be important.  My 
unproven algorithm is:

START
Let n be the number of candidates.
Let LIST be empty.
If n = 1, add the one candidate to LIST and go to #1.
Do for i from 0 to (n-2):
   If there are 1 or more candidates with exactly i pairwise losses, then:
      Add all candidates with exactly i pairwise losses to LIST.
      Let m be the current size of LIST.
      If the total number of pairwise wins by all of the current members of   
         LIST is greater than or equal to m(n-m), and the total number of    
         pairwise losses by all of the current members of LIST is less than or 
         equal to m(m-1)/2, go to #1.
   End if.
End do.
LIST = {all candidates}
#1
Smith set = LIST.
STOP

Bruce