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

[Ross Hyman]

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.