[EM] finding the beat path winner with just one pass through the ranked pairs

[Ross Hyman]

One can resolve ties and find second and third place winners, etc, by doing additional passes through the ranked pairs.

Ties can be resolved by passing through the ranked pairs again, this time eliminating candidates that have not won.  

Second, third, etc, place winners can be found by passing through the ranked pairs again with higher ranked winners classed as losers.

Example 
B>D, C>D
A>B, A>C
D>A
B>C

affirm B>D,C>D
A(W):A(W)
B(W):B(W)
C(W):C(W)
D(L):B(W),C(W),D(L)

affirm A>B,A>C
A(W):A(W)
B(L):A(W),B(L)
C(L):A(W),C(L)
D(L):A(W),B(L),C(L),D(L)

A is the first place winner.  To find the second place winner restart with:
A(L):A(L)
B(W):B(W)
C(W):C(W)
D(W):D(W)

affirm B>D,C>D
A(L):A(L)
B(W):B(W)
C(W):C(W)
D(L):B(W),C(W),D(L)

affirm A>B,A>C
A(L):A(L)
B(W):A(L),B(W)
C(W):A(L),C(W)
D(L):A(L),B(W),C(W),D(L)

affirm D>A
A(L):A(L),B(W),C(W),D(L)
B(W):A(L),B(W),C(W),D(L)
C(W):A(L),B(W),C(W),D(L)
D(L):A(L),B(W),C(W),D(L)

affirming B>C does not change the sets.
B and C are tied.  To resolve the tie for second place, restart with D eliminated.

A>B, A>C
B>C

A(L):A(L)
B(W):B(W)
C(W):C(W)

affirm A>B,A>C
A(L):A(L)
B(W):A(L),B(W)
C(W):A(L),C(W)

affirm B>C
A(L):A(L)
B(W):A(L),B(W)
C(L):A(L),B(W),C(L)
B is the second place winner.




--- On Fri, 12/9/11, Ross Hyman <rahyman at sbcglobal.net> wrote:

> From: Ross Hyman <rahyman at sbcglobal.net>
> Subject: finding the beat path winner with just one pass through the ranked pairs
> To: election-methods at lists.electorama.com
> Date: Friday, December 9, 2011, 4:36 AM
> I tried to design a method to find
> the beat path winner and to resolve beat path ties all in
> just one pass through the ranked pairs.  But Markus
> demonstrated that my tie resolver was not monotonic.  
> 
> So here, I believe, is a way to get the beat path winner(s)
> with just one pass through the ranked pairs.  Beat path
> ties remain ties.  Now a winner is only reclassified as
> a loser when there is at least one non-reciprocal winner in
> its set.
> 
> Candidates are classed in two categories: Winners and
> Losers.  Initially, all candidates are Winners. 
> Every candidate has an associated Set of candidates that
> includes itself and those candidates that have defeated
> it.  Every candidate initially has a set composed of
> itself and no other candidates.
> 
> Affirm each group of equally ranked pairs in order, from
> highest to lowest.   The count can be ended
> before all pairs have been affirmed if only one Winner
> remains.  Affirming is composed of two steps: Combining
> sets and Reclassifying candidates.    
> 
> Affirming Step 1: Combining
> When A > B is affirmed, the set for candidate A is
> added
> to every set that includes candidate B (not just candidate
> B’s set).  The Combining step is performed for all
> pairs of the same rank before moving on to the Reclassifying
> step.
> 
> Affirming Step 2: Reclassifying
> Winning candidate C is reclassified as a loser if there is
> at least one winner in C’s set that does not have C in its
> set.  
> 
> Example
> C>D
> A>C and B>C
> D>A and D>B
> A>B
> 
> affirm C>D
> A(W): A(W)
> B(W): B(W)
> C(W): C(W)
> D(L):C(W), D(L)
> D was reclassified as a Loser since C(W) is in its set. 
> 
> affirm  A>C and B > C
> A(W): A(W)
> B(W): B(W)
> C(L): A(W), B(W), C(L)
> D(L): A(W), B(W), C(L), D(L)
> C was reclassified as a Loser since A(W) and B(W) are in
> its set. 
> 
> affirm D > A and D > B
> A(W): A(W), B(W)*, C(L), D(L)
> B(W): A(W)*, B(W), C(L), D(L)
> C(L): A(W), B(W), C(L), D(L)
> D(L): A(W), B(W), C(L), D(L)
> A and B remain winners. A is in B's set and B is in A's
> set.
> 
> 
> affirming A > B has no effect. A and B are tied. 
> Same as beat path.
> 
>