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

[Ross Hyman]

I think it is possible to do the social ordering also with just one pass through the ranked pairs (although with multiple passes through the candidates.)  

Candidates are assigned a numerical rank.  The lower the numerical rank, the more preferred the candidate. Initially all candidates are assigned rank 1.  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.  Affirming is composed of two steps:  Combining sets and Reranking 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 Reranking step.

Affirming Step 2: Reranking
Each candidate C is reranked to one more than the numerical rank of candidate in its set with the largest numerical rank that does not contain C in its set.  More than one pass might be necessary to rerank all candidates. 

Example
C>D
A>C and B>C
D>A and D>B
A>B
 
affirm C>D
A(1): A(1)
B(1): B(1)
C(1): C(1)
D(2):C(1), D(2)
D was reranked to 2 since C(1) is in its set and C doesn't have D in its set. 

affirm  A>C and B > C
A(1): A(1)
B(1): B(1)
C(2): A(1), B(1), C(2)
D(3): A(1), B(1), C(2), D(3)
C was reranked to 2 since A(1) and B(1) are in its set and neither have C in their sets. Then D is reranked to 3 since C(2) is in its set and C doesn't have D in its set.

affirm D > A and D > B
A(1): A(1),B(1),C(2),D(3)
B(1): A(1),B(1),C(2),D(3)
C(2): A(1),B(1),C(2),D(3)
D(3): A(1),B(1),C(2),D(3)
No candidate is reranked since there is no candidate, C, with a candidate in its set that does not contain C in its set.  The count ends since all sets are complete so no changes can occur.  


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

> From: Ross Hyman <rahyman at sbcglobal.net>
> Subject: Re: 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, 11:03 AM
> 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.
> > 
> >
>