Re: [EM] finding the beat path winner with just one pass through the ranked pairs
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 wrote: > From: Ross Hyman > Subject: Re: finding the beat path winner with just one pass through the > ranked pairs > To: election-methods@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 > wrote: > > > From: Ross Hyman > > Subject: finding the beat path winner with just one > pass through the ranked pairs > > To: election-methods@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
Re: [EM] finding the beat path winner with just one pass through the ranked pairs
On 7/22/64 2:59 PM, Rob LeGrand wrote: Markus wrote: the runtime to calculate the strongest path from every candidate to every other candidate is O(C^3). However, the runtime to sort O(C^2) pairwise defeats is already O(C^4). So you cannot get a faster algorithm by sorting the pairwise defeats. Can't you sort O(C^2) items in O(C^2 log C) time if you use a O(n log n) algorithm such as heapsort? Yes, this is correct. In practice quicksort is faster than heapsort (though not asymptotically). The strongest path algorithm is solved in O(C^3) using the Floyd-Warshall algorithm, applied to a different commutative semiring (max, min) than the usual (min, +). However, faster algorithms are known for solving the same problem (all-pairs shortest path). For example, there is a paper by Melhorn and Priebe that shows how to solve it in O(C^2 log C) expected time. I don' t know if these faster algorithms work on all commutative semirings, though. -- Andrew Election-Methods mailing list - see http://electorama.com/em for list info
Re: [EM] finding the beat path winner with just one pass through the ranked pairs
Markus wrote: > the runtime to calculate the strongest path from > every candidate to every other candidate is O(C^3). > However, the runtime to sort O(C^2) pairwise defeats > is already O(C^4). So you cannot get a faster > algorithm by sorting the pairwise defeats. Can't you sort O(C^2) items in O(C^2 log C) time if you use a O(n log n) algorithm such as heapsort? -- Rob LeGrand r...@approvalvoting.org Citizens for Approval Voting http://www.approvalvoting.org/ Election-Methods mailing list - see http://electorama.com/em for list info
Re: [EM] finding the beat path winner with just one pass through the ranked pairs
Dear Ross, the runtime to calculate the strongest path from every candidate to every other candidate is O(C^3). However, the runtime to sort O(C^2) pairwise defeats is already O(C^4). So you cannot get a faster algorithm by sorting the pairwise defeats. Markus Schulze Election-Methods mailing list - see http://electorama.com/em for list info
Re: [EM] finding the beat path winner with just one pass through the ranked pairs
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 wrote: > From: Ross Hyman > Subject: finding the beat path winner with just one pass through the ranked > pairs > To: election-methods@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. > > Election-Methods mailing list - see http://electorama.com/em for list info
[EM] finding the beat path winner with just one pass through the ranked pairs
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. Election-Methods mailing list - see http://electorama.com/em for list info
