Condorcet tally shortcut?

[Steve Eppley]

It might be worthwhile to search for shortcuts in Condorcet tallies.
Maybe it's not necessary to calculate every pairing, as suggested in
Tom Round's draft of constitutional language.  

How about this iterative procedure, which appears to converge on the 
"beats all" candidate if there is one, or the one with smallest 
largest opposition if there isn't a "beats all":

--BEGIN--

Initialize a one-dimensional array LargestOpposition[i] to all zeros.
(I'll abbreviate this array as LO[i] below.)

Initialize the elements of the two-dimensional pair matrix P[i,j] to 
zero.

Pick two candidates X and Y at random (or using top two plurality, 
which might or might not converge sooner).

Repeat the following...

   Count all the ballots' X vs. Y preferences to find P[X,Y] and 
   P[Y,X].

   if P[X,Y] > [Y,X]
   then                                  ; X pair-beat Y
      LO[Y] := max(LO[Y], P[X,Y])           ; update LO[]
   else                                  ; Y pair-beat X
      LO[X] := max(LO[X], P[Y,X])           ; update LO[]
   endif

   if LO[X] < LO[Y]
   then
      BestYet := X
      Pick a new Y which hasn't yet been compared vs. X.  (If it 
         doesn't cost much overhead, pick one with small LO.)
   else
      BestYet := Y
      Pick a new X which hasn't yet been compared vs. Y.  (If it 
         doesn't cost much overhead, pick one with small LO.)
   endif

... until the BestYet has been paired against every candidate.

If there are candidate(s) i with LO[i] = LO[BestYet]
   ; Finish checking possible ties:
   For each candidate i with LO[i] = LO[BestYet]
      Repeat...
         Compare i with another candidate j not yet compared with i
      ... until LO[i] > LO[BestYet] or i has been fully compared.
   EndFor
Endif

--END--

An example:

   45:ABC
   10:BAC
   10:BCA
   35:CBA

   Pick two candidates:  A & B

   Count the A vs B preferences:  [A,B] = 45 and [B,A] = 55
   Update LO[A] = 55.  (A's worst defeat yet)
   BestYet = B.

            A    B    C
      A         45    ?
      B    55L        ?
      C     ?    ?
          ---- ---- ----
      LO:  55+   0    0

   Pick another candidate to compare against BestYet:  
      Only C is uncompared vs. B, so C is picked.

   Count the B vs C preferences:  [B,C] = 65 and [C,B] = 35
   Update LO[C] = 65.  (C's worst defeat yet)
   BestYet = B.

            A    B    C
      A         45    ?
      B    55L       65L
      C     ?   35
          ---- ---- ----
      LO:  55+   0   65+

   Since BestYet has been compared with all candidates, the 
   iterations cease.  (BestYet is B.)

   There is no need to compare A or C further, since LO[A] > LO[B] 
   and LO[C] > LO[B].  B is elected.

Note that if the first pair had been chosen by top two plurality,
the A vs. C pair would have been needlessly tallied.  Spatial
analysis may suggest a more optimal approach to picking the "next"
candidate than plurality.  The choice of "next pick" algorithm must
also take into account the labor overhead needed to calculate the
next pick.

Any comments on whether or not this alleged shortcut would succeed
at speeding up a manual tally, and whether there are circumstances
where it could make for *more* labor than an exhaustive pairwise tally?

I'm not sure whether there's a shortcut for calculating the Smith
set.  The algorithms we posted used as a "seed" the candidate with
fewest pairwise losses, and assumed these counts had already been
determined by an exhaustive tally.  Maybe with a little thought one
could use a procedure similar to the above shortcut, but instead of
tracking LO[] one could track the number of each candidates' pair-
losses.  That should produce a "best yet" which would be the one 
with fewest losses, a seed for the old Smith set algorithms.

If that works for Smith, it should work for Copeland tallies too.

---Steve     (Steve Eppley    seppley at alumni.caltech.edu)