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 CD AC and BC DA and DB AB affirm CD 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 AC 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 rahy...@sbcglobal.net wrote: From: Ross Hyman rahy...@sbcglobal.net 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 BD, CD AB, AC DA BC affirm BD,CD A(W):A(W) B(W):B(W) C(W):C(W) D(L):B(W),C(W),D(L) affirm AB,AC 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 BD,CD A(L):A(L) B(W):B(W) C(W):C(W) D(L):B(W),C(W),D(L) affirm AB,AC 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 DA 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 BC does not change the sets. B and C are tied. To resolve the tie for second place, restart with D eliminated. AB, AC BC A(L):A(L) B(W):B(W) C(W):C(W) affirm AB,AC A(L):A(L) B(W):A(L),B(W) C(W):A(L),C(W) affirm BC 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 rahy...@sbcglobal.net wrote: From: Ross Hyman rahy...@sbcglobal.net 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
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 BD, CD AB, AC DA BC affirm BD,CD A(W):A(W) B(W):B(W) C(W):C(W) D(L):B(W),C(W),D(L) affirm AB,AC 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 BD,CD A(L):A(L) B(W):B(W) C(W):C(W) D(L):B(W),C(W),D(L) affirm AB,AC 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 DA 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 BC does not change the sets. B and C are tied. To resolve the tie for second place, restart with D eliminated. AB, AC BC A(L):A(L) B(W):B(W) C(W):C(W) affirm AB,AC A(L):A(L) B(W):A(L),B(W) C(W):A(L),C(W) affirm BC 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 rahy...@sbcglobal.net wrote: From: Ross Hyman rahy...@sbcglobal.net 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 CD AC and BC DA and DB AB affirm CD 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 AC 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
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
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
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
